Zahlen in Array anordnen

member42

Aktives Mitglied
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.
 

mihe7

Top Contributor
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.
 

mihe7

Top Contributor
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.
 

httpdigest

Top Contributor
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
 
K

kneitzel

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

member42

Aktives Mitglied
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.
 
K

kneitzel

Gast
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
L die 3 größten Zahlen im Array Allgemeine Java-Themen 1
D Integer-Array variabler Größe mit Zahlen befüllen (Schleifen) Allgemeine Java-Themen 0
B Zahlen manuell eingeben und in Array Speichern Allgemeine Java-Themen 2
J Array ohne vorher festgelegte Länge oder Wie wandle ich Zahlen in Zahlen mit anderen Basen um? Allgemeine Java-Themen 6
J Zahlenkombination aus int-array, mit absteigenden Zahlen Allgemeine Java-Themen 6
F Array mit Zahlen drin sortieren Allgemeine Java-Themen 2
berserkerdq2 Versteht jemand, was diese beiden Zahlen bei dem IJVM Code zu bedeuten haben? Allgemeine Java-Themen 10
A Potenzmenge der Zahlen von 1 bis n Allgemeine Java-Themen 20
Monokuma String List nach Zahlen und Worten sortieren Allgemeine Java-Themen 9
G Java Editor Löschen doppelter Zahlen einer Liste Allgemeine Java-Themen 2
A String auf Zahlen überprüfen Allgemeine Java-Themen 5
J Zahlen Abstand zur Null bestimmen Allgemeine Java-Themen 11
R Methoden Was fehlt mir bzw. muss ich bei der Methode countHarshabNumbers ändern damit ich die Harshad Zahlen im Intervall [51, 79] zählen kann? Allgemeine Java-Themen 19
O Variablen Addition von Double-Werten ergibt seltsame 0.9999999 Zahlen Allgemeine Java-Themen 2
B Zufällig zwischen vorgegebenen Zahlen auswählen Allgemeine Java-Themen 6
P Rechnen mit sehr kleinen Zahlen Allgemeine Java-Themen 5
D Erste Schritte Arrays vergleichen und die zahlen die nur einmal vorkommen ausgeben Allgemeine Java-Themen 5
D Erste Schritte Fehler mit negativen und 0 Zahlen im String Allgemeine Java-Themen 6
T Tesseract OCR mit Zahlen Allgemeine Java-Themen 1
F Zahlen zu Bits Allgemeine Java-Themen 3
S Überprüfen, ob 5 Zahlen nebeneinander liegen Allgemeine Java-Themen 5
R Große Zahlen in Worten abkürzen Allgemeine Java-Themen 10
B Arrays mit Text und Zahlen füllen Allgemeine Java-Themen 3
G Aus JTextField Zahlen auslesen und random generieren Allgemeine Java-Themen 10
D Operatoren Logischer Rightshift von negativen Zahlen auf Bit-Ebene Allgemeine Java-Themen 7
L 2-Dimensionaler String: Zahlen verschieben Allgemeine Java-Themen 10
M Algorithmus zum Zahlen einteilen Allgemeine Java-Themen 8
H Fibonacci-Zahlen Allgemeine Java-Themen 5
E mit extrem langen Zahlen (als Zeichneketten) arbeiten Allgemeine Java-Themen 4
M Probleme beim rechnen, bei Zahlen mit führenden Nullen. Allgemeine Java-Themen 7
L Filewriter schreibt Zahlen in Textdatei Allgemeine Java-Themen 2
T Methoden Zahlen austauschen Allgemeine Java-Themen 8
Z Zahlen aus Bild auslesen Allgemeine Java-Themen 1
M ungerade zahlen auf 4 zahlen aufteilen Allgemeine Java-Themen 2
F Funktionsplotter komplexe Zahlen: geeignetes 3D-Koordinatensystem Allgemeine Java-Themen 16
B Zahlen ausgeben hilfe! Allgemeine Java-Themen 8
S Zahlen aus (String mit zahlen) immer wieder neu auslesen Allgemeine Java-Themen 5
N Bin to Dez und umgekehrt mit sehr großen Zahlen Allgemeine Java-Themen 2
T Modulo-Operator versagt bei zu großen Zahlen? Allgemeine Java-Themen 14
AssELAss String mit Zahlen mit Tausendertrennzeichen versehen Allgemeine Java-Themen 14
D Code bitte mit 19 stelligen Zahlen kompatibel machen Allgemeine Java-Themen 5
U (Java) Happy Numbers in Anlehnung an den Sieb des Eratosthenes (Glueckliche Zahlen) Allgemeine Java-Themen 1
Cayton Bruchrechner stürzt bei eingabe negativer Zahlen ab Allgemeine Java-Themen 4
N Zahl mit bestimmter Länge und nur bestimmten Zahlen generieren lassen Allgemeine Java-Themen 7
P Datentypen String-Daten zu Byte-Zahlen konvertieren - Komme nicht weiter nach vielem versuchen :-/ Allgemeine Java-Themen 7
I Java-Programm: Zahlen in Worte Allgemeine Java-Themen 22
H String auf Zahlen prüfen Allgemeine Java-Themen 4
V iText Textfelder mit Zahlen! Allgemeine Java-Themen 2
M Rechnen mit kleinen Zahlen langsamer!? Allgemeine Java-Themen 11
R Modulo mit negativen Zahlen Allgemeine Java-Themen 8
Luk10 Römische Zahlen in Java Allgemeine Java-Themen 7
R Codehinweise: Algorithmus Größenvergleich von n Zahlen Allgemeine Java-Themen 5
GianaSisters ArrayList mit Zahlen Allgemeine Java-Themen 10
B User-Input aus Zahlen und Operatoren - beste Umsetzung? Allgemeine Java-Themen 8
S Fixe Zahlen vergleichen Allgemeine Java-Themen 4
D JTable -> 1Spalte nur zahlen Allgemeine Java-Themen 2
N Zahlen in Strings einer ArrayList sortieren Allgemeine Java-Themen 14
T Apache POI Export EXCEL - [Zahlen-Werte] Allgemeine Java-Themen 1
ModellbahnerTT Button mit Zahlen beschriften Allgemeine Java-Themen 1
P große double Zahlen und modulo Allgemeine Java-Themen 8
R Runden von Zahlen Allgemeine Java-Themen 3
J Zahlen Rechtsbuendig in File schreiben Allgemeine Java-Themen 3
W POI - Formatierung für Zahlen Allgemeine Java-Themen 4
MQue Zahlen mit Border Allgemeine Java-Themen 2
T ungerade zahlen berechnen Allgemeine Java-Themen 3
N Zahlen mit Nachkommastellen aus Textfeldern einlesen Allgemeine Java-Themen 6
P Algoritmus für 3er-Paare von n Zahlen Allgemeine Java-Themen 12
A Fibonacci-Zahlen & kopfgesteuerte Schleifen & Strukt Allgemeine Java-Themen 8
J Suche regex-Pattern fuer Liste von Zahlen zwischen 0-100 Allgemeine Java-Themen 6
G die mittlere von 5 Zahlen nur mit if und else finden Allgemeine Java-Themen 48
M Rechnen mit sehr kleinen Zahlen Allgemeine Java-Themen 8
MQue Zahlen an alysieren Allgemeine Java-Themen 6
ARadauer Random keine Zahlen doppelt Allgemeine Java-Themen 4
V FileWriter und Zahlen (Kein Problem, nur Verständnisfrage) Allgemeine Java-Themen 4
G Strings die Zahlen enthalten sinnvoll sortieren (A2 < A10 Allgemeine Java-Themen 4
F 3 Zahlen "vereinfachen" Allgemeine Java-Themen 5
C double Zahlen mit drei NachkommaStellen in String umwandeln Allgemeine Java-Themen 2
A testen ob Primzahl dauert bei größeren zahlen extrem lange Allgemeine Java-Themen 8
E Hex- Zahlen in Datei Allgemeine Java-Themen 4
G Umrechnen von grossen Zahlen ins Hex-System Allgemeine Java-Themen 3
S Zahlen sortieren Allgemeine Java-Themen 3
D Zahlen innerhalb eines Strings auslesen Allgemeine Java-Themen 3
P rechnen mit extrem grossen zahlen Allgemeine Java-Themen 2
X Logische Operatoren auf binären Zahlen Allgemeine Java-Themen 2
M Hilfe: Lotto: die 6 häufigsten generierten zahlen ausgeben Allgemeine Java-Themen 13
O String auf zahlen prüfen (java 1.3) Allgemeine Java-Themen 4
G Methode, die Buchstaben in Zahlen umwandelt? Allgemeine Java-Themen 13
S Integer-Zahlen in Excel-Sheet schreiben Allgemeine Java-Themen 10
M Lange Zahlen in Java Allgemeine Java-Themen 4
C zahlen einlesen Allgemeine Java-Themen 2
thE_29 Wie hex Zahlen darstellen Allgemeine Java-Themen 3
G Zahlen vergleichen Allgemeine Java-Themen 5
S Rechnen mit float Zahlen Allgemeine Java-Themen 2
H Kann keine Zahlen von Buchstaben unterscheiden Allgemeine Java-Themen 4
LucasGlockner Effizienter byte-Zugriff auf ein long[]-Array Allgemeine Java-Themen 8
8u3631984 Frage Performance bei Linked List und Array List Allgemeine Java-Themen 5
M Queue mit einem Array implemetieren Allgemeine Java-Themen 16
M Array Rang eines Elements Allgemeine Java-Themen 4
TheSepp Java bestimmtes Array auf den Wert 0 setzen Allgemeine Java-Themen 32
TheSepp Wie kann man Leerzeichen aus einer Array liste entfernen? Allgemeine Java-Themen 10

Ähnliche Java Themen

Neue Themen


Oben