Permutation ohne Wiederholung

[stekoe2000]

<?
$gruppen = 9;

for($i = 1; $i <= $gruppen; $i++)
{
    for($j = 1; $j <= $gruppen; $j++)
    {
        if($i != $j)
        {
            $array[$i][$j] = "$i$j";
        }
        else 
        {
            $array[$i][$j] = "00";
        }
    }
}

array_unique($array);

for($i = 1; $i <= $gruppen; $i++)
{
    for($j = 1; $j <= $gruppen; $j++)
    {
        if($array[$i][$j+$i] != NULL)
        {
            $out[] = $array[$i][$j+$i];
            echo $array[$i][$j+$i]."  ";
        }
    }
    echo "<br />";
}
?>

Daraus erhalte ich dann meine gewollte Dreiecksmatrix:

 n  n  n  n  n  n  n  n
=======================
12 13 14 15 16 17 18 19 
23 24 25 26 27 28 29 
34 35 36 37 38 39 
45 46 47 48 49 
56 57 58 59 
67 68 69 
78 79 
89

Wie ihr seht, ist in der Matrix die Permutation aus den Zahlen 1 bis 9 zu finden (ohne Wiederholung). Mein Problem ist nun, das ich eine n x n Matrix brauche (in diesem Falle, wie ich gerade sehe 6x6), die in den Zeilen und Spalten Permutation ohne Wiederholung haben soll.

Da ich mit meinem Mathestudium noch nicht so weit bin, finde ich zur Zeit noch keinen Ansatz, wie ich das machen könnte.

// Edit: Mist, ich dachte ich hätte das richtige Forum erwischt ...

[frodenius]

hm wie wärs mit einer linearen speicherung in nem eindimensionalen array?
und die anzahl der kombinationen (!) ist n über k. also hier 9 über 2.

[stekoe2000]

Guten Abend, danke für die Antwort. Kombinatorik, okay, 9 über 2, auch gut *g, aber es geht um folgendes Problem:

Ich habe x Gruppen in welchen y Personen sind. Weiter gibt es 3 "Arbeitsschichten", welche mit jeweils 2 Gruppen besetzt werden sollen.

Jede Gruppe soll jeweils in einem bestimmten Zyklus mindestens 1 mal jede Schicht gehabt haben, jedoch alle die gleiche anzahl der Schichten, also wenn Gruppe 1 - 9 mal Schicht 1 hatte, sollen alle anderen Gruppen ebenfalls 9 mal Schicht 2 gehabt haben.

Ich hab das Gefühl, dass das nicht dynamisch zu machen ist, bzw zu komplex, da zu viele Faktoren mit einspielen, jede Gruppe mal mit jedem und die selbe Anzahl von geleisteten Schichten...

Da das aber kein wirkliches PHP Problem ist, hatte ich es im "Brainstorming" Forum gepostet, ist aber jetzt hierher verschoben...

Für 7 Gruppen habe ich es mal händisch gemacht (3h):

    // mögliche Variationen:
    // Bem.: $gruppe[] = array(1. Schicht, 2. Schicht, 3. Schicht);

    $gruppe = array();
    $gruppe[] = array("1/2","3/4","5/6");    
    $gruppe[] = array("4/7","1/5","2/3");    
    $gruppe[] = array("3/6","2/7","1/4");    
    $gruppe[] = array("1/7","3/5","2/6");    
    $gruppe[] = array("2/4","1/6","5/7");    
    $gruppe[] = array("6/7","4/5","1/3");    
    $gruppe[] = array("2/5","3/7","4/6");    
    $gruppe[] = array("3/7","4/6","2/5");    
    $gruppe[] = array("4/5","1/3","6/7");    
    $gruppe[] = array("1/6","5/7","2/4");    
    $gruppe[] = array("3/5","2/6","1/7");    
    $gruppe[] = array("2/7","1/4","3/6");        
    $gruppe[] = array("1/5","2/3","4/7");        
    $gruppe[] = array("3/4","5/6","1/2");        
    $gruppe[] = array("5/6","1/2","3/4");    
    $gruppe[] = array("2/3","4/7","1/5");    
    $gruppe[] = array("1/4","3/6","2/7");    
    $gruppe[] = array("2/6","1/7","3/5");    
    $gruppe[] = array("5/7","2/4","1/6");    
    $gruppe[] = array("1/3","6/7","4/5");
    $gruppe[] = array("4/6","2/5","3/7"); 

[Nescire]

Also mir ist gerade nicht ganz klar ob du eine Mathematische oder eine Informatik Lösung suchst.
Also als Informatiker würde ich am simpelsten es so sehen.
Ich habe eine Liste mit "n" Gruppen. (Die anzahl der Personen in den Gruppen ist irrelevant.) Diese Speicher ich in eine Liste. Ich definiere ein Objekt für jede Schicht.
Schicht1, Schicht2 und Schicht3. Die Objekte Enthalten nun 2 Pointer jeweils auf 2 Stellen in der Liste.
Schicht1 auf 1 und 2, Schicht2 auf 3 und 4, Schicht3 auf 5 und 6.
So nun schiebe ich die Liste immer schritt für schritt durch insgesamt n-1 mal.
1 2 3 4 5 6 7 8
8 1 2 3 4 5 6 7
7 8 1 2 3 4 5 6
6 7 8 1 2 3 4 5
5 6 7 8 1 2 3 4
4 5 6 7 8 1 2 3
3 4 5 6 7 8 1 2
2 3 4 5 6 7 8 1

Somit hat jede Gruppe jede Schicht zwar 2 mal absolviert, dies war allerdings ja auch nicht ausgeschlossen.

[stekoe2000]

Danke für die Antwort, dieses System hatte ich auch schon, leider, es wird die Bedingung nicht erfüllt, dass jede Gruppe mal mit jeder Gruppe gemischt die Schicht übernimmt: Auch mal Gruppen 8 u. 3, etc

[Nescire]

oh ok klar vergessen dann mach es doch einfach so das du anstelle das durchschieben durchstauschst.
Ähnlich wie beim Bubblesort.
Also wen du eine Reihe hast 1 2 3 4 5 6

1 2 3 4 5 6
2 1 3 4 5 6
2 3 1 4 5 6
2 3 4 1 5 6
2 3 4 5 1 6
2 3 4 5 6 1
3 2 4 5 6 1
3 4 2 5 6 1
usw.
also immer die position der xten zahl mit der pos n+1 tauschen
Sag mir wenn ich wieder eine Bedingung übersehen habe.

Argh vergiss die Idee sobald es mehr Gruppen als benötigt gibt klappt das auch nicht mehr.

Ok ein schritt weiter gedacht, müßte gehen wenn man das ganze von hinten aufrollt also die nte zahl von hinten nach vorne durchschiebt. die muss solange gemacht werden bis die ursprüngliche reinfolge wieder gegeben ist.

[stekoe2000]

Danke nochmal. Ich glaube aber, dass ich (wir) da kein System entdecken werde(n), so dass alle Möglichkeiten durchlaufen werden um ein "intelligentes" Gruppensystem zu erzeugen.

Wenn ich es händisch mache, scheint es auch irgendwie willkürlich, wobei es ja dann auch nen Algorithmus geben muss ... ich versuch weiter und wenn ich was finden sollte, werde ich es hier posten, danke und sry wegen deiner investierten Zeit

[Nescire]

würde ja gern mal wissen wo nun noch der fehler in meiner lösung sein soll...

[stekoe2000]

So .. soweit ich das jetzt nachvollziehen konnte, meintest du, dass folgendes rauskommen wird:

1 2 | 3 4 | 5 6
1 3 | 2 4 | 5 6
1 3 | 4 2 | 5 6
1 3 | 4 5 | 2 6
1 3 | 4 5 | 6 2
1 4 | 3 5 | 6 2
1 4 | 5 3 | 6 2
1 4 | 5 6 | 3 2
1 4 | 5 6 | 2 3
1 5 | 4 6 | 2 3
1 5 | 6 4 | 2 3
1 5 | 6 2 | 4 3
1 5 | 6 2 | 3 4
1 6 | 5 2 | 3 4
1 6 | 2 5 | 3 4
1 6 | 2 3 | 5 4
1 6 | 2 3 | 4 5
1 2 | 6 3 | 4 5
1 2 | 3 6 | 4 5
1 2 | 3 4 | 6 5
1 2 | 3 4 | 5 6 => Anfang
2 1 | 3 4 | 5 6
2 3 | 1 4 | 5 6
2 3 | 4 1 | 5 6
2 3 | 4 5 | 1 6
2 3 | 4 5 | 6 1

wobei man jetzt sieht, dass die Kombination 1/3 4 mal nacheinander die 1. schicht bekäme .. das ist ebenfalls nicht gewollt ... wie gesagt, ich schau mal weiter

[Nescire]

also du solltest mal üben probleme genauer zu konkretisieren, senn du keine doppeleinträge willst, speicher die ergebnisse zwischen und lösch doppelte raus.
Zudem habe ich weiter unten in meinem post geschrieben das man von hinten anfangen sollte und ich verstehe auch nicht wieso du mit der 2 anfängst.