etwas kompliziertere Permutation, Prüfungsszenario (Allgemeines zu Perl)

[thread]7004[/thread]

etwas kompliziertere Permutation, Prüfungsszenario

Gast Gast

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).

Code: (dl )

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?

Ishka

2005-05-19 19:26

User since
2003-08-04
771 Artikel
HausmeisterIn

Ich würde in der Reihenfolge der Erzeugung so vorgehen, wie bei der Berechnung, wieviele es sind:

(2 aus 10) mal (2 aus 8) mal (2 aus 6) mal (2 aus 4) = 113400

dh. ersteinmal über alle zweielementigen Teilmengen iterieren und in jedem Schleifendurchlauf alle Kombinationen aus den Restlichen 8 Elementen erzeugen, dann so weiter, so erhälst du automatisch jedes Element nur einmal.

Ich hoffe, du weißt, was ich meine, ansonsten frag einfach nochmal nach.

sub z{if(@_){1while$x[$k=rand 10];t($t=$x[$k]=1)}print map"$z[$x[$_]]$_".($_%3?
"":"\n"),1..9}sub t{$j=0;$x[$_+1]==$t&&($j+=2**$_)for 0..8;z,die"Gewinner $z[$t]
"if grep$_==($j&$_),7,56,73,84,146,273,292,448;z,die"Gleichstand\n"if@x>9&&!grep
!$_,@x}@x=4;@z=qw{. [ (};z$^T&1;while(<>){next if$_>9||$x[$_];t$t=$x[$_]=2;z 1}

Dredd

2005-05-19 21:04

User since
2005-05-19
3 Artikel
BenutzerIn
[default_avatar]

Sorry, da musst du mir genauer erklären, wie du es meinst ...

Taulmarill

2005-05-19 21:31

User since
2004-02-19
1750 Artikel
BenutzerIn

user image

solche permutationsgeschichten lassen sich eigendlich immer mit rekursion lösen (auch wenn ich zugeben muss, dass diese hier besonders verzwickt war)

Code: (dl )

use strict;
use warnings;
use Data::Dumper;

my @menge = 1 .. 4;
my @iter  = rec(@menge);

print Dumper \@iter;

sub rec {
    return () unless ( @_ > 1 );
    my $first = shift;
    map {
        my ( $second, $rest ) = @$_;
        [ [ $first, $second ], $rest ? @$rest : () ]
    } map {
        my @tmp        = @_;
        my ( $second ) = splice @tmp, $_, 1;
        [ $second, rec(@tmp) ]
    } 0 .. @_ - 1
}

sollte eigendlich die anforderungen erfüllen, oder hab ich was übersehen?

$_=unpack"B*",~pack"H*",$_ and y&1|0& |#&&print"$_\n"for@.=qw BFA2F7C39139F45F78 0A28104594444504400 0A2F107D54447DE7800 0A2110453444450500 73CF1045138445F4800 0 F3EF2044E3D17DE 8A08A0451412411 F3CF207DF41C79E 820A20451412414 83E93C4513D17D2B

Dredd

2005-05-19 22:05

User since
2005-05-19
3 Artikel
BenutzerIn
[default_avatar]

Also wenn ich das richtig überblicke - OK, eigentlich steige ich in der Zeile "[ [ $first, $second ], $rest ? @$rest : () ]" nicht durch, aber ich habs ausprobiert ;) - dann erstellt dein Script Mengen. Hier braucht man aber 5-Tupel. (E-SP|WR-F|M-C|G-L|D-KU) ist was anderes als (WR-F|E-SP|M-C|G-L|D-KU), weil dann die Prüfungen an einem anderen Tag statt finden! Außerdem gibt es ungemein mehr Möglichkeiten. Ist etwas verzwickt, ein 5-Tupel aus Teilmengen, sozusagen.
Der eleganteste Weg geht wohl über Rekursion. Was wird in der einen Zeile gemacht?

kabel

2005-05-19 22:29

User since
2003-08-04
704 Artikel
BenutzerIn
[default_avatar]

Code (perl): (dl )

[ [ $first, $second ], $rest ? @$rest : () ]

das erzeugt ein anonymes array, welches als erstes element ein weiteres anonymes array hat ($first, $second). wenn $rest nicht 0 ist, dann wird $rest als arrayreferenz behandelt und dereferenziert. ansonsten wird die leere liste angefuegt.

-- stefan

pKai

2005-05-20 01:05

User since
2005-02-18
357 Artikel
BenutzerIn
[default_avatar]

Meine Lösung sieht von der Struktur ganz ähnlich aus wie das Code-Fragment im OP.

Ohne Beschränkung der Allgemeinheit seien die Namen unserer
Fächer die Zahlen 1 .. 2*n (n Tage Prüfungen à 2 Fächer).
Eine 2-Teilmenge von Fächern {i,j} wird durch das 2-Tupel (i,j) mit
i<j kanonisch dargestellt.

Code: (dl )

use strict;
use warnings;

my $n = shift;    # Anzahl Tage; -> 2*n Fächer
die "Anzahl Tage übergeben\n" unless $n > 0;
die "OMG, viel zu lang!\n" unless $n <= 10;

my $z;    # Zähler

# sub plan ist die rekursive Funktion
# Sie sammelt im ersten Arg das ein, was bereits verplant ist und 
# die restlichen Args sind noch freie Fächer (Nummern)
plan ([], 1 .. 2*$n);
print "$z verschiedene\n";

sub plan {
    my @p = @{shift @_};    # Das steht derzeit fest
    # Ausgeben, wenn nichts mehr zu verteilen ist.
    ++$z, return print join ('', map {$_&1 ? "$p[$_]}" : "{$p[$_],"} 0 .. $#p) . "\n" unless @_;
    # Aus den freien den ersten wählen.
    # Iterieren über die Positionen.
    foreach my $i (0 .. $#_-1) {
        # Aus den verbleibenen (größeren, wg Kanonizität) den
        # 2. wählen
        # Iterieren über restlichen (höheren) Indexnummern
        foreach my $j ($i+1 .. $#_) {
            # Rekursion mit den neu festgelegten gemerkt,
            # und dem verbleiben Rest zur Auswahl
            plan ([@p,$_[$i],$_[$j]], @_[0 .. $i-1], @_[$i+1 .. $j-1], @_[$j+1 .. $#_]);
        }
    }
}

I sense a soul in search of answers.

Taulmarill

2005-05-20 12:05

User since
2004-02-19
1750 Artikel
BenutzerIn

user image

Quote
(E-SP|WR-F|M-C|G-L|D-KU) ist was anderes als (WR-F|E-SP|M-C|G-L|D-KU)

dann kannst du doch einfach die ergebnisse aus meiner rekursion noch mal in einem zweiten schritt permutieren, das sollte kein problem sein.

Dredd

2005-05-20 13:26

User since
2005-05-19
3 Artikel
BenutzerIn
[default_avatar]

@pKai: Genau das ist es, Respekt! Ist ne sehr schöne Lösung, weil sie es gleich "in einem Schritt" macht und nicht, wie Taulmarill und ich vorgeschlagen haben, mit Hilfe eines zweiten Schritts, der die Teilmengen durchpermutiert. Der Rest ist kein Problem mehr. Vielen Dank an alle!

View all threads created 2005-05-19 18:12.