Thread Gibt es für Zeile x einer Matrix andere Zeilen die ein Subset dieser Zeile sind? (11 answers)
Opened by leo11 at 2010-10-19 15:06

leo11
 2010-10-19 15:06
#142047 #142047
User since
2008-08-14
250 Artikel
BenutzerIn
[default_avatar]
Hi.

Gegeben ist eine Matrix bestehend aus 0,1 und -. Darin möchte ich für jede Zeile prüfen, ob es andere Zeilen gibt, die eine Teilmenge dieser Zeile sind. Mit etwas Hilfe hab ich diese Lösung hinbekommen:
Code (perl): (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;

my @all = (<DATA>);
my @all_cp = @all;

foreach my $row (@all) {
    chomp $row;

    my @target_line = split ' ', $row;
    print "\nTarget:\t\t$row\n";

    foreach my $line (@all_cp) {
        chomp $line;
        my @line_to_comp = split ' ', $line;
        next if $line_to_comp[0] eq $target_line[0]; # do not compare the same line with each other
        my ($digits, $dashes) = (0,0);

        for my $index ( 1 .. $#target_line ) { # ignore column 0
            # both are digits and they are equal
            if ( 2 == grep( { /^\d/ } $target_line[$index], $line_to_comp[$index] )
                 and $target_line[$index] == $line_to_comp[$index]
               ) {
                $digits++;

            } elsif ( $line_to_comp[$index] eq "-" ) {
                $dashes++;
            } else {
                last;
            }
        }
        if ( $dashes != (scalar @target_line - 1) and ($digits + $dashes) == (scalar @target_line - 1)) { # -1 because of column 0
            print "Subset:\t\t$line\n";
        } else {
            # print "Not a subset:\t$line\n";
        }
    }
}
__DATA__
row18 - 0 0 1 0 0 - - - 0 0 - - - - - - - - - - - - - - - -
row19 - 0 0 0 - - - - 1 0 0 - - - - - - - - - - - - - - - -
row20 - 0 0 - - - - 1 - 0 0 - - - - - - - - - - - - - - - -
row21 - 0 0 - - - - - - 0 0 - - - - 1 0 0 - - - - - - - - -
row22 - 0 0 - - - - - - 0 0 - - - - 0 - - - 1 - - - - - - -
row23 - 0 0 - - - - - - 0 0 - - - - - - - - - 1 - - - - - -
row24 - 0 0 - - - - - - 0 0 - - - - - - - - - - 1 0 0 - - -
row25 - 0 0 - - - - - - 0 0 - - - - - - - - - - 0 - - - 1 -
row26 - 0 0 - - - - - - 0 0 - - - - - - - - - - - - - - - 1
row27 - 0 0 - - - - - - 1 0 0 - - - - - - - - - - - - - - -
row28 - 0 0 - - - - - - 0 - - - - 1 - - - - - - - - - - - -
row29 - 0 0 - - - - - - - - - 1 - - - - - - - - - - - - - -
row30 1 0 0 - 1 - - - - 0 0 - - - - - - 1 - - - - - - - - -
row31 1 0 0 - 1 - - - - 0 0 - - - - - - - - - - - 1 - - - -
row32 1 0 0 - 1 - - - - 0 0 - - - - - - 1 - - - - 1 - - - -
row33 1 0 0 - - - 1 - - 0 0 - - - - - - - - - - - - - - - -
row34 1 0 0 - - - - - - 0 0 - - - - - - - 1 - - - - - - - -
row35 1 0 0 - - - - - - 0 0 - - - - - - - - - - - - - 1 - -
row36 1 0 0 - - - - - - 0 0 - - - - - - 1 - - - - 1 - - - -
row37 1 0 0 - 1 - - - - - 1 - - - - - - 1 - - - - - - - - -
row38 1 0 0 - 1 - - - - - 1 - - - - - - - - - - - 1 - - - -
row39 1 0 0 - 1 - - - - - 1 - - - - - - 1 - - - - 1 - - - -
row40 1 0 0 - - - 1 - - - 1 - - - - - - - - - - - - - - - -
row41 1 0 0 - - - - - - - 1 - - - - - - - 1 - - - - - - - -
row42 1 0 0 - - - - - - - 1 - - - - - - - - - - - - - 1 - -
row43 1 0 0 - - - - - - - 1 - - - - - - 1 - - - - 1 - - - -
row44 1 0 0 - - - - - - - - 1 - 1 - - - - - - - - - - - - -
row45 - 1 - - - - - - - 1 0 0 - - - - - - - - - - - - - - -
row46 - 1 - - - - - - - 0 - - - - 1 - - - - - - - - - - - -
row47 - 1 - - - - - - - - - - 1 - - - - - - - - - - - - - -
row48 - - 1 - - - - - - 1 0 0 - - - - - - - - - - - - - - -
row49 - - 1 - - - - - - 0 - - - - 1 - - - - - - - - - - - -
row50 - - 1 - - - - - - - - - 1 - - - - - - - - - - - - - -
row51 - 1 0 - - - - - - - - - 0 - - - - - - - - - - - - - -
row52 - 0 1 - - - - - - - - - 0 - - - - - - - - - - - - - -
row53 - 1 0 - - - - - - - - - - - 0 - - - - - - - - - - - -
row54 - 0 1 - - - - - - - - - - - 0 - - - - - - - - - - - -
row55 - 1 0 - - - - - - 0 0 - - - - - - - - - - - - - - - -
row56 - 0 1 - - - - - - 0 0 - - - - - - - - - - - - - - - -


Nur mal aus Interesse: Ist das eine gute Aufgabe für eine rekursive Lösung mit einem 2D Array? Ggf. wie würde die aussehen?

View full thread Gibt es für Zeile x einer Matrix andere Zeilen die ein Subset dieser Zeile sind?