Hallo,
Hier mal ein ganz anderes Problem.
Ich moechte mit 15 Teilnehmer ein Skatturnier veranstalten.
Dabei spielen immer 3 Leute an einem Tisch und jeder soll gegen jeden spielen ohne 2 mal auf einen der anderen zu treffen.
Idealerweise findet man dann 35 3er Tische, aber wie ?
Etwas abstarkter formuliert:
ich mochte aus den Zahlen 1-15 35 "3er Gruppen" bilden wobei jede Zahl 7 mal vorkommt und die Schnittmenge von 2 3er Gruppen nie groesser 1 ist.
Hi,
also ich hab es mal praktisch versucht, siehe Anhang,
geht nur scheinbar nicht auf, also das C noch gegen F und I und anschliesend noch gegen L und O spielen muss ist klar aber hat A nicht schon gegen alle gespielt?
Kopfkratz
Gruß Ulf
Hi,
Danke - ich habs nun so in Perl geschafft:
my @allTables = ();
my $idx = 0;
foreach my $i ( 1..15) {
my $js = $i + 1;
foreach my $j ($js..15) {
my $ks = $j + 1;
foreach my $k ($ks..15) {
$allTables[$idx][0] = $i;
$allTables[$idx][1] = $j;
$allTables[$idx][2] = $k;
$idx++;
}
}
}
my $entries = $idx - 1;
my @newTable = ();
my $newIdx = 0;
for my $i ( 0..$entries ) {
my $doit = 1;
if ($newIdx > 0) {
for my $j ( 0..($newIdx-1) ) {
my $match = 0;
foreach my $k(0..2) {
foreach my $l(0..2) {
if ($newTable[$j][$k] == $allTables[$i][$l] ) {
$match ++;
}
}
}
if ($match > 1) {
$doit = 0;
last;
}
}
}
if ($doit) {
$newTable[$newIdx][0] = $allTables[$i][0];
$newTable[$newIdx][1] = $allTables[$i][1];
$newTable[$newIdx][2] = $allTables[$i][2];
print "$allTables[$i][0] $allTables[$i][1] $allTables[$i][2]\n";
$newIdx++;
}
}
print "Found $newIdx\n";Eine weitere straight-forward Lösung in Perl:
#!/usr/bin/perl
use strict;
use warnings;
use constant MAX=>15;
my @pair=();
my $num=0;
my @count;
@count[1 .. MAX]=map 0,1..MAX;
for (my $i=1; $i<=MAX; $i++) {
for (my $j=$i+1; $j<=MAX; $j++) {
next if exists $pair[$i][$j];
for (my $k=$j+1; $k<=MAX; $k++) {
next if exists $pair[$i][$k];
next if exists $pair[$j][$k];
$num++;
$count[$i]++;
$count[$j]++;
$count[$k]++;
print "$num: $i,$j,$k\n";
$pair[$i][$j]=1;
$pair[$i][$k]=1;
$pair[$j][$k]=1;
last; # exists $pair[$i][$j]
}
}
}
print join(' ',@count[1..MAX]),"\n";Für 15 funktioniert das spannenderweise, aber für andere gültige Turniere (4 Runden mit 9 Spielern, 10 Runden mit 21 Spielern, 13 Runden mit 27 Spielern) geht es dagegen nicht auf: Es bleiben immer Spieler übrig, die keine gültige 3er-Kombination mehr ergeben.
Die spannende Frage ist: Gibt es dafür eine allgemeine, einfache Lösung, oder kommt man nicht an einem backtracking-Algorithmus vorbei?
Gruß,
Udo
Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!