Opened by Gast at 2005-05-19 18:12
Um es etwas zu verdeutlichen, möchte ich ein Beispiel anführen:
Nehmen wir an, an einer Schule gäbe es 10 unterschiedliche Fächer. In diesen zehn Fächern sollen an fünf Tagen Prüfungen statt finden, also zwei pro Tag. Die Prüfungen finden gleichzeitug statt. Gesucht sind nun alle möglichen Kombinationen.
Es handelt sich offensichtlich nicht um eine einfache Permutation der Fächer, da man ja immer die zwei Fächer pro Tag nicht unterscheiden kann, d. h. die Tageskombinationen von zwei Fächern sind zweielementige Teilmengen der Menge der Fächer {E,SP,WR,F,M,C,G,L,D,KU}:
{E,SP} {WR,F} {M,C} {G,L} {D,KU} ist gleichbedeutend mit
{SP,E} {WR,F} {M,C} {G,L} {D,KU}
Auf die Reihenfolge, in der die Teilmengen folgen, kommt es jedoch an, denn sie legt ja den Prüfungsplan fest.
Ich bin kein Mathe-Ass, aber wenn ich mich nicht irre müsste es (2 aus 10) mal (2 aus 8) mal (2 aus 6) mal (2 aus 4) = 113400 solche Anordnungen geben.
Ziel wäre es jetzt, diese mit Hilfe eines Perl-Scripts zu generieren. Ich hätte mir überlegt, dass man zuerst alle möglichen zweier-Teilmengen (ohne Wiederholungen) der Fächer bildet, was nicht weiter schwer ist. Betrachtet man z. B. die Menge {1,2,3,4,5}:
12 21 31 41 51
13 23 32 42 52
14 24 34 43 53
15 25 35 45 54
Wenn man also aufsteigend vorgeht (zuerst 12, dann 13, 14, 15, 21 usw.), kann man z. B. bei der ersten Stelle 4 sicher sein, dass alle Teilmengen mit einer zweiten Stelle kleiner 4 (41, 42, 43) schon mal dran waren (14, 24, 34).
Man erhält dann E-SP E-WR E-F E-M usw. Und nun hätte ich mir gedacht, dass man diese Elemente mit Permutation und der Länge 5 anordnet. Man müsste nur darauf achten, dass sich die Fächer nicht wiederholen, also wenn am ersten Tag z. B. die Kombination E-SP steht, dann darf nachher nicht E-WR kommen, oder SP-WR.
Ich habe ziemlich lange rumprobiert, kriegs aber nicht hin. Vielleicht ist auch mein Ansatz falsch. Was fällt euch denn dazu ein?
Nehmen wir an, an einer Schule gäbe es 10 unterschiedliche Fächer. In diesen zehn Fächern sollen an fünf Tagen Prüfungen statt finden, also zwei pro Tag. Die Prüfungen finden gleichzeitug statt. Gesucht sind nun alle möglichen Kombinationen.
Es handelt sich offensichtlich nicht um eine einfache Permutation der Fächer, da man ja immer die zwei Fächer pro Tag nicht unterscheiden kann, d. h. die Tageskombinationen von zwei Fächern sind zweielementige Teilmengen der Menge der Fächer {E,SP,WR,F,M,C,G,L,D,KU}:
{E,SP} {WR,F} {M,C} {G,L} {D,KU} ist gleichbedeutend mit
{SP,E} {WR,F} {M,C} {G,L} {D,KU}
Auf die Reihenfolge, in der die Teilmengen folgen, kommt es jedoch an, denn sie legt ja den Prüfungsplan fest.
Ich bin kein Mathe-Ass, aber wenn ich mich nicht irre müsste es (2 aus 10) mal (2 aus 8) mal (2 aus 6) mal (2 aus 4) = 113400 solche Anordnungen geben.
Ziel wäre es jetzt, diese mit Hilfe eines Perl-Scripts zu generieren. Ich hätte mir überlegt, dass man zuerst alle möglichen zweier-Teilmengen (ohne Wiederholungen) der Fächer bildet, was nicht weiter schwer ist. Betrachtet man z. B. die Menge {1,2,3,4,5}:
12 21 31 41 51
13 23 32 42 52
14 24 34 43 53
15 25 35 45 54
Wenn man also aufsteigend vorgeht (zuerst 12, dann 13, 14, 15, 21 usw.), kann man z. B. bei der ersten Stelle 4 sicher sein, dass alle Teilmengen mit einer zweiten Stelle kleiner 4 (41, 42, 43) schon mal dran waren (14, 24, 34).
Code: (dl
)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
my @liste = (E,SP,WR,F,M,C,G,L,D,KU);
my @d = ZweiausX(\@liste);
sub ZweiausX {
my $ref = shift;
my $X = @{$ref};
my @data = ();
for ($i=0;$i<$X-1;$i++) {
for ($j=$i+1;$j<$X;$j++) {
push(@data, ${$ref}[$i]."-".${$ref}[$j]);
}
}
return @data;
}
Man erhält dann E-SP E-WR E-F E-M usw. Und nun hätte ich mir gedacht, dass man diese Elemente mit Permutation und der Länge 5 anordnet. Man müsste nur darauf achten, dass sich die Fächer nicht wiederholen, also wenn am ersten Tag z. B. die Kombination E-SP steht, dann darf nachher nicht E-WR kommen, oder SP-WR.
Ich habe ziemlich lange rumprobiert, kriegs aber nicht hin. Vielleicht ist auch mein Ansatz falsch. Was fällt euch denn dazu ein?