Problem mit For-Schleifen (Logik)

[JoeJoe]

Hallihallo Leute,
ich habe ein kleines Problem mit meiner Hausaufgabe.
Da weder google noch die Forensuche etwas ausgespuckt hat, poste ich es mal hier.

Ich soll für eine Klasse alle möglichen Sitzordnungen ausgeben.
Idealisierterweise hat die Klasse 8 Schüler und 8 Plätze.

Meinen Überlegungen zufolge sollten das jetzt 8! = 40.320 Möglichkeiten sein.

Mein Problem ist jetzt der Ansatz. Ich habe es mit 8 verschachtelten For-Schleifen versucht, das wären aber ja 8^8 = 16777216. Nicht sehr sinnvoll, da der Fabian dann eventuell zweimal irgendwo sitzt und der Peter nirgendwo.

Wie kann ich jetzt mit möglichst kleinem Rechenaufwand (Die 16777216 durchgehen und alle Fälle ausschließen wo ein Wert zweimal vorkommt, ist also definitiv keine Option) ein paar For-Schleifen durchgehen, wobei jede zwar einen Wert von 0-7 annehmen kann, aber keine den Wert einer anderen? Muss ich das eventuell rekursiv lösen?

Die Syntax ist nicht mein Problem, mit der kenne ich mich denke ich ganz gut aus. Ich habe nur gerade eine kleine Logikblokade und würde mich daher über Anregungen sehr freuen.

Liebe Grüße und vielen Dank im voraus

Joejoe

 

[Joose]

Genau das geht in die Richtung Permutation, daher sollt der Ansatz "8!" schon richtig sein.

Auf dieses spezielle Problem bezogen sind deine 8-Schleifen vielleicht passend (würden sich aber die Anforderungen ändern müsstest du auch den Code anpassen - nur so als Hinweis).
Bei diesen 8 Schleifen musst du aber beachten das nicht jede 8x durchläuft! Sondern nur die äußerste läuft 8x durch, die nächste 7x, die nächste 6x usw. dann passiert es auch nicht das eine Person plötzlich 2x wo sitzt.

Ich würde hier eine Liste mit den 8 Namen vorschlagen, sowie eine rekursive Methode.

Hier mal etwas Code

public static void moeglichkeitAusgeben(ArrayList<String> students, String variant) {
    for (String student : students) {
        String nextVariant = variant + " | " +  student;
        ArrayList<String> otherStudents = getOtherStudents(student, students);
        if (otherStudents.size() > 0) {
            moeglichkeitAusgeben(otherStudents, nextVariant);
        } else {
            System.out.println(nextVariant);
        }
    }	        
}

 

[JoeJoe]

Ja genau. Die Idee mit der ArrayList ist mir heute Morgen auch gekommen. Danke für den Hinweis! Wobei ich deine getOtherStudents Funktion noch nicht ganz verstehe. Ich werde es mal iterativ versuchen und danach rekursiv, auf meine eigene Art und Weise

 

[Dompteur]

getOtherStudents(student, students) liefert dir die Liste, der in der nächsten Rekursions-Stufe zu behandelnden Studenten.
Es wird dazu eine neue ArrayList angelegt und alle Einträge aus students werden dort eingetragen - außer dem, der im Paramter student übergeben wird.