Zahlen in Array anordnen

Bitte aktiviere JavaScript!
Hallo,

ich habe z.B 2 Zahlen und ein 4*4 Array und möchte die Anzahl der Anordnungsmöglichkeiten der Zahlen im Array finden. Das müssten dann 16 * 15 = 240
verschiedene Anordungen sein, ich bekomme aber als Anzahl 256 zurück. Kann wer einen Tipp geben woran das liegt?


Java:
static class Test {

    public Test() {
       int anzahl = anordnen(feld, zahlen.length - 1);
       System.out.println(anzahl); // 256
    }

    int zahlen[] = {1, 2};
    int[][] feld = {{0, 0, 0, 0},
            {0, 0, 0, 0},
            {0, 0, 0, 0},
            {0, 0, 0, 0}};
    int anzahl = 0;

    int[][] kopiereFeld(int[][] feld) {
        int[][] tmp = new int[feld.length][feld.length];

        for(int i = 0; i < feld.length; i++) {
            tmp[i] = feld[i].clone();
        }
        return tmp;
    }

    int anordnen(int feld[][], int n) {

        if(n == -1)  return anzahl;

        for(int i = 0; i < feld.length; i++) {
            for(int j = 0; j < feld.length; j++) {

                int z = zahlen[n];
                int kopie[][] = kopiereFeld(feld);

                if(kopie[i][j] == 0) {
                    kopie[i][j] = z;
                    anordnen(kopie, n - 1);
                    anzahl++;
                }

            }
        }
        return anzahl;
    }
}
Danke im Vorraus.
 
A

Anzeige


Vielleicht hilft dir dieser Kurs hier weiter: (hier klicken)
Zu Beginn sind feld und damit auch kopie mit 0en gefüllt. Die Bedingung kopie[i][j] == 0 if ist also immer true, d. h. für jede der 16*16 Iterationen wird anzahl erhöht, macht 256.
 
Und rein mathematisch (Kombinatorik): 16 Felder mit entweder Zahl_1 oder Zahl_2 macht 16^2 = 256
16 Felder mit entweder Zahl_1 oder Zahl_2 macht 2^16 = 65536 :)

Ihm geht es um die Frage, wie viele Möglichkeiten es gibt, 2 von 16 Felder mit je einer Zahl zu belegen. D. h. für die erste Zahl stehen 16 Möglichkeiten zur Verfügung, für die zweite nur noch 15, macht 240.
 
Die Anzahl der Möglichkeiten, zwei von 16 Feldern unabhängig voneinander mit entweder der Zahl 1 oder 2 zu belegen, ist:

16 * 15 * 2 = 480

Grund: Gäbe es nur eine mögliche Zahl, die wir verwenden könnten, dann wäre die Anzahl der Möglichkeiten, das erste der 16 Felder mit dieser einen Zahl zu füllen, genau 16. Für das zweite Feld hätten wir noch 15 Möglichkeiten, dieselbe Zahl noch auf die 15 restlichen Felder zu verteilen.
Da es aber 2 Zahlen gibt, die wir auf je zwei der 16 Felder verteilen können, verdoppelt sich hier die Anzahl der Kombinationen.

Rechenbeispiel für 2 von 4 Feldern mit entweder 1 oder 2 belegt:
0011,0101,1001,0012,0102,1002,0110,1010,0120,1020,1100,1200,
0021,0201,2001,0022,0202,2002,0210,2010,0220,2020,2100,2200
= 4 * 3 * 2 = 24
 
Aber der Fehler im Code ist auch noch zu finden.

Wann zählst Du Anzahl hoch? Anzahl wird hochgesetzt bei jeder Ziffer, die Du setzt:
Die Schleife geht ja alle Felder durch, für jedes Feld, das noch leer ist, rufst Du zum einen Rekursiv auf mit einer Kopie, in der das aktuelle Feld gesetzt wurde und dann Anzahl hoch gezählt. Also wenn wir nur das erste Verteilen betrachten, dann hast Du da 15 Möglichkeiten, aber Anzahl ist 16.

Also das Zählen musst Du Dir überlegen. Auch die Art und weise ist unüblich. Eine Variable außerhalb der Rekursion hoch zu zählen ist nicht das, was man normalerweise macht! Und Du hast eine Rückgabe, die du in dem Rekursiven Aufruf nicht nutzt. Also auch ganz schlecht.

Wenn die Abbruchbedingung erfüllt ist, dann hast Du eine Lösung aufgestellt in dem Feld, oder? Also da könnte man return 1 sagen.

Bei der Rekursion: Beim füllen der einzelnen Felder hast Du noch keine komplette Lösung, also ein Anzahl++ kann da nur falsch sein. Aber die Lösung ist die Summe der Lösungen, die durch die Rekursion erkannt wurden. Also muss da eine lokale Variable anzahl sein und in der schleife addierst Du die Anzahl der Lösungen, die durch den rekursiven Aufruf gefunden wurden.

Das wäre in Umgangssprache ein Weg, die Rekursion zu bauen.
 
Danke, es funktioniert jetzt hatte da einen ziemlichen Denkfehler.:)
Ich hatte das nicht genau geschrieben, es zählen nur Anordnungen wo z.B die 1 und 2 jeweils genau einmal vorkommen, also müsste das mit 240 Anordnungen(wie om Programm jetzt zurückgeben) auch stimmen.

Java:
int anordnen(int feld[][], int n) {

        if(n == -1) {
            ausgeben(feld);
            anzahl++;
            return anzahl;
        }

        for(int i = 0; i < feld.length; i++) {
            for(int j = 0; j < feld.length; j++) {

                int z = zahlen[n];
                int kopie[][] = kopiereFeld(feld);

                if(kopie[i][j] == 0) {
                    kopie[i][j] = z;
                    anordnen(kopie,n - 1);
                }

            }
        }
        return anzahl;
    }
}

Also das Zählen musst Du Dir überlegen. Auch die Art und weise ist unüblich. Eine Variable außerhalb der Rekursion hoch zu zählen ist nicht das, was man normalerweise macht! Und Du hast eine Rückgabe, die du in dem Rekursiven Aufruf nicht nutzt. Also auch ganz schlecht.
Warum ist das so unüblich? Habe das schon öfter so gesehen, um die Anzahl der Lösungen zu bestimmen.
 
Also für das Wieso gibt es mehrere Punkte, die ich sehe:
a) Eine Kapselung. Die Funktion soll etwas berechnen. Das Ergebnis interessiert. Informationen, die sonst nicht weiter von Interesse sind, sollte man nicht zwangsläufig außerhalb speichern.
b) Lesbarkeit. Was ist denn die Rückgabe der Funktion? Anscheinend nicht ganz durchdacht, wenn das größtenteils ignoriert wird.

Was ist die Rückgabe bei Deiner Funktion? Das ist ja kein sinnvolles Ergebnis aus meiner Sicht, da Du Zwischenergebnisse zurück gibst.

Ich würde einen Code wie folgt besser finden (Ungetestet im Forum geschrieben):
Java:
// Besserer Name - "anzahl" besagt nichts!
  int permutationenBestimmen(int feld[][], int n) {

        if(n == -1) {
            // Ausgeben bei einer Funktion, die etwas berechnet halte ich für unüblich, aber ok.
            ausgeben(feld);
            return 1;
        }

        int anzahl = 0;
        for(int i = 0; i < feld.length; i++) {
            for(int j = 0; j < feld.length; j++) {

                int z = zahlen[n];
                int kopie[][] = kopiereFeld(feld);

                if(kopie[i][j] == 0) {
                    kopie[i][j] = z;
                    anzahl += anordnen(kopie,n - 1);
                }
            }
        }
        return anzahl;
    }
Hier ist jetzt kein anzahl außerhalb notwendig und es wird aufsummiert.

Das ist dann auch die übliche Rekursion bei Berechnungen. n! = n*(n-1)! mit 1! = 1 - da wird dann auch mit der Rückgabe der Rekursiven Funktion gerechnet.
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben