Fettes Problem mit vierdimensionalen Array-Variationen

[jwiejava]

Hallo Community,

ich habe folgendes vierdimensionales (!!) Array in meiner Klasse:

	public static final int[][][][] temp = new int[][][][] {
		{{ {12, 22}, {55, 66} }},								
		{{ {10, 11}, {78, 24}}},						
		{{ {16, 29}, {51, 33} }},						
		{{ {22, 36}, {40, 10}, {34, 27}}}, 				
		{{ {60, 23}, {54, 18}, {41, 26}}}	
	};

Zur Erklärung: Es geht eigentlich um die 5 Listen mit sog. Kandidaten für Koordinaten (deswegen 2-Dimensional) und diese Koordinaten sind in ein Array gepackt welches eine Koordinatenliste darstellen soll. Drumherum habe ich dann die anderen zwei Dimensionen gelegt, um alle 5 Listen in einem Array unterzubringen. Man hätte es zwar auch in einer ArrayList oder Hashmap lösen können, doch so fand ich es übersichtlicher & einfacher, da ich ja die Werte auch fest/statisch eintrage.

Nun gut ... alle verwirrt? Dann zu meiner eigentlichen Frage:
Nun muss ich mir eine Funktion à la

public static ArrayList<int[][][][]> alleVariationen(int[][][][] basis)

basteln. Diese Funktion gibt alle Kombinationen des oben genannten Arrays in einer ArrayList oder Hashmap zurück (der Datentyp ist derzeit mein geringstes Problem). Dazu ist noch zu sagen, dass die Oben genannten Listen (von links=1 nach rechts=ende) sortiert sind. Für dieses Array müssten also insgesamt 144 verschiedene vierdimensionale Arrays generiert werden, durch eben das Vertausch einzelner Listeneinträge.

So, schön und gut. Aber irgendwie kann ich nicht beginnen diese Methode abzufassen. Denn aus irgendeinem Grund (vielleicht weil ich hier mit vierdimensionalen Arrays durch die Gegend werfe ) ist mein Kopf so ein bisschen überlastet.

Ich hoffe, dass mir jemand ein paar hilfreiche Tipps geben kann und ich diese Methode fertig bekomme!
Gruß,
jwiejava

 

[XHelp]

Also die Struktur ist mehr als... unschön. Da bist du besser dran, wenn du dir dafür eigene Klassen machst.
Aber generell zu deiner Frage:
Du kannst dir eine Methode schreiben, die dir alle Variationen eines 1d-Arrays liefert. Dann brauchst du noch jede Menge Schleifen drumherum und schon gehst du über deine gesamtes Array.
Oder war die Frage anders?
Gruß,
vwievendetta

 

[jwiejava]

Oh, wie ich sehe findet mein Benutzername Anklang: jwiejava ... vwievendetta ;-)

Du kannst dir eine Methode schreiben, die dir alle Variationen eines 1d-Arrays liefert.

Also dieses Array beispielsweise "{12, 22}" darf in sich nicht mehr verändert werden (sind ja x und y).

Dann brauchst du noch jede Menge Schleifen drumherum und schon gehst du über deine gesamtes Array.

Ich schreibe eine Methode, die mir "{ {12, 22}, {55, 66} }" in Variationen an gibt (also "{ {12, 22}, {55, 66} }" und "{ {55, 66}, {12, 22} }") und dann kommen da Schleifen drum? Aber wie wusele ich das so zusammen, dass am Ende auch wirklich jede Variation nur einmal da ist? Ich habe da ein bisschen Sorge, dass mir das auseinanderdriftet!

Da bist du besser dran, wenn du dir dafür eigene Klassen machst.

Wie könnte soetwas aussehen? Denn das ist ja nicht gerade einfach ...

Gruß,
jwiejava

 

[XHelp]

public class Varianten {
  private List<Point> liste;
....
}

Dann brauchst du nur noch eine

List<Varianten>

.

 

[jwiejava]

Ich habe mal etwas gebastelt ...

public class Varianten {

	public static final int[][][][] temp = new int[][][][] {
		{{ {12, 22}, {55, 66} }},								
		{{ {10, 11}, {78, 24}}},						
		{{ {16, 29}, {51, 33} }},						
		{{ {22, 36}, {40, 10}, {34, 27}}}, 				
		{{ {60, 23}, {54, 18}, {41, 26}}}	
	};
	
	public static ArrayList<int[][][][]> alleVariationen(int[][][][] basis) {
		ArrayList<int[][][][]> alles = new ArrayList<int[][][][]>();
		
		int durchlaeufe = 0;
		for (int i = 0; i < basis.length; i++) {
			for (int j = 0; j < basis[i].length; j++) {
				for (int j2 = 0; j2 < basis[i][j].length; j2++) {
					durchlaeufe++;
				}
			}
		}
		durchlaeufe = durchlaeufe*durchlaeufe;
		System.out.println("Durchlaeufe=" + durchlaeufe);
		
		for (int i = 0; i < durchlaeufe; i++) {
			int[][][][] temp = new int[basis.length][1][][];	
			int reihe = 0;
			int elementNachEins = 1;
			
			for (int j = 0; j < temp.length; j++) {
				for (int j2 = 0; j2 < temp[j].length; j2++) {
					temp[j][j2] = new int[basis[j][j2].length][];
					
					if (reihe == j) {
						for (int k = 0; k < temp[j][j2].length; k++) {
							temp[j][j2][k] = basis[j][j2][elementNachEins];
							elementNachEins++;
						}
					} else {
						// nur kopieren
						temp[j][j2] = basis[j][j2];
					}
					reihe++;
				}
			}
			
			alles.add(temp);
			break;
		}
		return alles;
	}
	
	public static void ausgabe(int[][][][] array) {
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				for (int j2 = 0; j2 < array[i][j].length; j2++) {
					System.out.print(Arrays.toString(array[i][j][j2]));
					if (j2 < array[i][j].length-1) 
						System.out.print(", ");
				}
				System.out.println();
			}
		}
	}
	
	public static void main(String[] args) {
		ArrayList<int[][][][]> a = alleVariationen(temp);
		System.out.println(a.size());
		for (int i = 0; i < a.size(); i++) {
			System.out.println("----------------------------------");
			ausgabe(a.get(i));
			System.out.println("----------------------------------");
		}
		ausgabe(temp);
	}
	
}

 

[XHelp]

Funktioniert das jetzt oder ist das "wo ist der Fehler im rechten Bild"?

 

[jwiejava]

Hallo,

ich habe die Taktik gewechselt. Ich sehe mir jetzt jede der 5 Listen (die 5 ist überigends variabel) einzeln an und bestimme dann zu jeder Liste ersteinmal die verschiedenen Variationen. Dann wenn alle Variationen fest stehen, dann werden daraus die einzelnen Varianten des vierdimensionalen Arrays konstruiert. Probleme habe ich derzeit bei der Erstellung der Varianten, wie macht man das?
Hier der bisherige Code:

	private static void alleVarianten(int[][] basis, ArrayList<int[][]> speicher) {
		ArrayList<int[]> basisAlsAL = new ArrayList<int[]>();
		for (int i = 0; i < basis.length; i++) basisAlsAL.add(basis[i]);
		
		for (int i = 0; i < basisAlsAL.size()*basisAlsAL.size(); i++) {
			ArrayList<int[]> dieseVariante = new ArrayList<int[]>();
			
			
			
			
			speicher.add(dieseVariante.toArray(new int[dieseVariante.size()][]));
		}
	}
	
	public static ArrayList<int[][][][]> alleVariationen(int[][][][] basis) {
		ArrayList<ArrayList<int[][]>> alleListen = new ArrayList<ArrayList<int[][]>>();
		
		// Erstelle die Listen mit dem Basiselement
		for (int i = 0; i < basis.length; i++) {
			ArrayList<int[][]> temp = new ArrayList<int[][]>();
			temp.add(basis[i][0]);
			alleListen.add(temp);
		}
		
		// Erstelle Variationen von dem Basiselement
		for (int i = 0; i < alleListen.size(); i++) {
			ArrayList<int[][]> aktuelle = alleListen.get(i);
			int[][] basisElement = aktuelle.get(0);
			alleVarianten(basisElement, aktuelle);
		}
		
		// Aus den verianten alle Moeglichkeiten konstruieren
	
		return null;
	}

Gruß,
jwiejava

 

[Marco13]

Ähmja. Dieser Array ist Murks. (Punkt). "Ich finde das praktisch" ändert da nichts dran.

Schau vielleicht auch mal hier: http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html#post646341

 

[Final_Striker]

Also ich finde dein Ansatz ist Quatsch. Schreibe und benutze Klassen. Um Koordinaten zu speichern bietet dir Java schon ein fertige Klasse Point an.

 

[Landei]

Schließe mich meinen beiden Vorrednern an. Wir sind hier ein Java-Forum, aber dein Code rangiert strukturell irgendwo zwischen COBOL und Perl...

 

[jwiejava]

Hallo zusammen,

mein letzer Ansatz ging dann in diese Richtung:

	public static ArrayList<ArrayList<Point>> points = 
		new ArrayList<ArrayList<Point>>();
	
	static {
		ArrayList<Point> temp = null;
		// die eins
		temp = new ArrayList<Point>();
		temp.add(new Point(12, 22));
		temp.add(new Point(55, 66));
		points.add(temp);
		
		// die zwei
		temp = new ArrayList<Point>();
		temp.add(new Point(10, 11));
		temp.add(new Point(78, 24));
		points.add(temp);
		
		// die drei
		temp = new ArrayList<Point>();
		temp.add(new Point(22, 36));
		temp.add(new Point(40, 10));
		temp.add(new Point(34, 27));
		points.add(temp);
	}
	
	
	public static HashMap<Integer, ArrayList<ArrayList<Point>>> alleVarianten(
			ArrayList<ArrayList<Point>> b) {
		HashMap<Integer, ArrayList<ArrayList<Point>>> h = 
			new HashMap<Integer, ArrayList<ArrayList<Point>>>();
		
		// TODO: ...
		return h;
	}

Aber ich kapituliere nun aufgrund der Komplexität des Problems und dem ganzen Chaos ...
Gruß,
jwiejava

 

[LoR]

Jetzt nochmal von vorne:
Kannst du dein Problem vielleicht erstmal etwas genauer erläutern? D.h. beschreib dein Problem erstmal detailliert so das man die ganze Sache auch mal vollständig versteht.

U.a.
Welche Daten stehen dir zur Verfügung?
Wie müssen die Koordinaten (theoretisch) aufeinander gemapped werden?
Was ist das Ziel?
Was möchtest du damit machen?

Wenn deine Beschreibung einigermaßen verständlich und vollständig ausfällt wird sich auch sicherlich eine passende Lösung finden lassen .

 

[Antoras]

Programmiere Objektorientiert:

method allVariations(CoordinateList c) {
  Variation v;
  // use v
}

class Variation {
  CoordinateList l;
  int i;
}

class CoordinateList {
  List<Coordinate> coordinates;
}

class Coordinate {
  Point p;
}

Wie deine Daten jetzt aber genau in Verbindung stehen hab ich aber auch nicht verstanden...

 

[jwiejava]

Okay ... reset ... noch mal von vorne:

Also, es geht darum, dass man eine Menge an Listen hat, die Koordinaten beinhalten. Diese Koordinaten sind sog. Kandidaten. Und diese Liste an Kandidaten sind sortiert. D.h. das erste Element wird im Gegensatz zu dem zweiten, dritten ... bevorzug ausgewäht. Schematisch sieht das so aus:

[
    [[Koordinate 1], [Koordinate 2]], //=Liste 1 mit sortierten Kandidatenkoordinaten
    [[Koordinate 5], [Koordinate 3], [Koordinate 4]], //=Liste 2
    [[Koordinate 7], [Koordinate 6]] //=Liste 3
]

Dabei ist die Anzahl an Listen (hier sind es drei) variabel sowie die Anzahl der Koordinaten (hier: 2, 3, 2) variabel.

So, und nun ergibt diese Menge an Listen ein bestimmtes Ergebnis, wenn ich diese Menge an Listen in mein Programm packe. Nun möchte ich Brute-Force anwenden. D.h. ich generiere mir alle Möglichen Kombinationen der Menge an Listen und packe jede Kombination in mein Programm und schaue mir das Ergebnis an. Und dann kann ich mir am Ende ein Diagramm zeichnen, wo ich dann sehen kann, welche Kombination von allen möglichen Kombinationen das beste Ergebnis ergibt.

Es ist so ein bisschen wie Passwortknacken per Brute-Force. Also ich generiere alle möglichen Zeichenketten und probiere dann alles aus und sehe dann am Ende, welche Zeichenkette die wirksamste ist (=also den Zugang gewährt). Dazu muss ich aber noch sagen, dass ich keinen Passwortknacker schreibe ... ;-)

Hab ich das verständlich erklärt?

Gruß,
jwiejava

 

[Marco13]

Also ausgehend von

[
    [[Koordinate 1], [Koordinate 2]], //=Liste 1 mit sortierten Kandidatenkoordinaten
    [[Koordinate 5], [Koordinate 3], [Koordinate 4]], //=Liste 2
    [[Koordinate 7], [Koordinate 6]] //=Liste 3
]

würde jede Kombination, von der du redest, genau EINE Koordinate aus JEDER der Listen enthalten, z.B.
1,5,7
1,5,6
1,3,7
1,3,6
...

Das ist dann auch wieder nur "zählen", allerdings mit einer "variablen Basis"....

 

[jwiejava]

Nein, die Listen bleiben erhalten und die Koordinaten dürfen nicht die Listen wechseln. Es sollen aber die Positionen der Koordinaten in einer Liste wechseln und dann soll man halt wieder die Gesamtmenge bekommen, sodass man am Ende viele viele Gesamtmengen hat mit getauschten Listenpositionen.

 

[Antoras]

Hört sich nach Permutation an.

 

[Marco13]

Hört sich nach chaotischem Geschwafel an, wenn du mich fragst. Ich bin raus.