Alle Kombinationen von Zahlenreihe ohne Doppelungen

[-horn-]

Moien,

Ich mal wieder mit ner kombinatorikfrage.

Ich habe nun eine variable zahlenreihe von n stellen, zb
1, 2, 3, 4
Die in einem array steckten

Die will ich nun so kombinieren, dass alle kombinationen erzielt werden, aber nur von den angezeigten ziffern und ohne doppelung.

Zb
2,3,4,1
3,4,1,2
4,1,2,3
4,3,2,1
3,2,1,4
2,1,4,3
1,4,3,2
2,1,4,3
Etc

Ich raffe nur noch nicht, wie i h das machen soll, da ich kein muster erkenne.

Danke im voraus

 

[Ebenius]

Sicher nicht der optimale Code. Aber er läuft.

public static int[][] kombiniere(int[] input) {
  if (input.length == 1) {
    // done
    return new int[][] { input };
  }

  final List<int[]> results = new LinkedList<int[]>();
  int[] tempArray = input.clone();
  for (int i = 0; i < input.length; i++) {
    tempArray[0] = input[i];
    for (int[] childs : kombiniere(removeFromArray(input, i))) {
      System.arraycopy(childs, 0, tempArray, 1, childs.length);
      results.add(tempArray.clone());
    }
  }

  return results.toArray(new int[results.size()][]);
}

private static int[] removeFromArray(int[] array, int index) {
  final int[] newArray = new int[array.length - 1];
  System.arraycopy(array, 0, newArray, 0, index);
  System.arraycopy(array, index + 1, newArray, index, newArray.length
        - index);
  return newArray;
}

[ edit ]

2,1,4,3
1,4,3,2
2,1,4,3

Ich gehe davon aus, das war ein Versehen und genau diese Doppelungen sollen nicht vorkommen.

Ebenius

 

[Ebenius]

Ach ja: Das ist mein Test-Code:

/**
 * Test main method.
 * 
 * @param args ignored
 */
public static void main(String[] args) {
  final int[][] testInputs =
        { { 1 }, { 1, 2 }, { 1, 2, 3 }, { 2, 3, 5, 7, 11, } };
  for (int[] input : testInputs) {
    final int[][] results = kombiniere(input);
    System.out.println(input.length
          + " Eingangswerte: "
          + results.length
          + " Ausgabewerte!");
    System.out.println("-------------------------------------------------");
    for (int[] kombi : results) {
      for (int v : kombi) {
        System.out.print(v);
        System.out.print(", ");
      }
      System.out.println();
    }
    System.out.println();
  }
}

1 Eingangswerte: 1 Ausgabewerte!
-------------------------------------------------
1,

2 Eingangswerte: 2 Ausgabewerte!
-------------------------------------------------
1, 2,
2, 1,

3 Eingangswerte: 6 Ausgabewerte!
-------------------------------------------------
1, 2, 3,
1, 3, 2,
2, 1, 3,
2, 3, 1,
3, 1, 2,
3, 2, 1,

5 Eingangswerte: 120 Ausgabewerte!
-------------------------------------------------
2, 3, 5, 7, 11,
2, 3, 5, 11, 7,
2, 3, 7, 5, 11,
2, 3, 7, 11, 5,
2, 3, 11, 5, 7,
2, 3, 11, 7, 5,
2, 5, 3, 7, 11,
2, 5, 3, 11, 7,
2, 5, 7, 3, 11,
2, 5, 7, 11, 3,
2, 5, 11, 3, 7,
2, 5, 11, 7, 3,
2, 7, 3, 5, 11,
2, 7, 3, 11, 5,
2, 7, 5, 3, 11,
2, 7, 5, 11, 3,
2, 7, 11, 3, 5,
2, 7, 11, 5, 3,
2, 11, 3, 5, 7,
2, 11, 3, 7, 5,
2, 11, 5, 3, 7,
2, 11, 5, 7, 3,
2, 11, 7, 3, 5,
2, 11, 7, 5, 3,
3, 2, 5, 7, 11,
3, 2, 5, 11, 7,
3, 2, 7, 5, 11,
3, 2, 7, 11, 5,
3, 2, 11, 5, 7,
3, 2, 11, 7, 5,
3, 5, 2, 7, 11,
3, 5, 2, 11, 7,
3, 5, 7, 2, 11,
3, 5, 7, 11, 2,
3, 5, 11, 2, 7,
3, 5, 11, 7, 2,
3, 7, 2, 5, 11,
3, 7, 2, 11, 5,
3, 7, 5, 2, 11,
3, 7, 5, 11, 2,
3, 7, 11, 2, 5,
3, 7, 11, 5, 2,
3, 11, 2, 5, 7,
3, 11, 2, 7, 5,
3, 11, 5, 2, 7,
3, 11, 5, 7, 2,
3, 11, 7, 2, 5,
3, 11, 7, 5, 2,
5, 2, 3, 7, 11,
5, 2, 3, 11, 7,
5, 2, 7, 3, 11,
5, 2, 7, 11, 3,
5, 2, 11, 3, 7,
5, 2, 11, 7, 3,
5, 3, 2, 7, 11,
5, 3, 2, 11, 7,
5, 3, 7, 2, 11,
5, 3, 7, 11, 2,
5, 3, 11, 2, 7,
5, 3, 11, 7, 2,
5, 7, 2, 3, 11,
5, 7, 2, 11, 3,
5, 7, 3, 2, 11,
5, 7, 3, 11, 2,
5, 7, 11, 2, 3,
5, 7, 11, 3, 2,
5, 11, 2, 3, 7,
5, 11, 2, 7, 3,
5, 11, 3, 2, 7,
5, 11, 3, 7, 2,
5, 11, 7, 2, 3,
5, 11, 7, 3, 2,
7, 2, 3, 5, 11,
7, 2, 3, 11, 5,
7, 2, 5, 3, 11,
7, 2, 5, 11, 3,
7, 2, 11, 3, 5,
7, 2, 11, 5, 3,
7, 3, 2, 5, 11,
7, 3, 2, 11, 5,
7, 3, 5, 2, 11,
7, 3, 5, 11, 2,
7, 3, 11, 2, 5,
7, 3, 11, 5, 2,
7, 5, 2, 3, 11,
7, 5, 2, 11, 3,
7, 5, 3, 2, 11,
7, 5, 3, 11, 2,
7, 5, 11, 2, 3,
7, 5, 11, 3, 2,
7, 11, 2, 3, 5,
7, 11, 2, 5, 3,
7, 11, 3, 2, 5,
7, 11, 3, 5, 2,
7, 11, 5, 2, 3,
7, 11, 5, 3, 2,
11, 2, 3, 5, 7,
11, 2, 3, 7, 5,
11, 2, 5, 3, 7,
11, 2, 5, 7, 3,
11, 2, 7, 3, 5,
11, 2, 7, 5, 3,
11, 3, 2, 5, 7,
11, 3, 2, 7, 5,
11, 3, 5, 2, 7,
11, 3, 5, 7, 2,
11, 3, 7, 2, 5,
11, 3, 7, 5, 2,
11, 5, 2, 3, 7,
11, 5, 2, 7, 3,
11, 5, 3, 2, 7,
11, 5, 3, 7, 2,
11, 5, 7, 2, 3,
11, 5, 7, 3, 2,
11, 7, 2, 3, 5,
11, 7, 2, 5, 3,
11, 7, 3, 2, 5,
11, 7, 3, 5, 2,
11, 7, 5, 2, 3,
11, 7, 5, 3, 2,

Ebenius

 

[-horn-]

moien Ebenius und schonmal danke

[ edit ]

2,1,4,3
1,4,3,2
2,1,4,3

Ich gehe davon aus, das war ein Versehen und genau diese Doppelungen sollen nicht vorkommen.

Ebenius

jap, das sollte nicht sein. weder innerhalb der zahlenreihe als auch die zahlenreihen selbst soll es zu keiner wiederholung kommen.


ich muss mich erstmal durch deinen code fuchsen und nachvollziehen, was der tut , aber ich kann dir schon sagen, dass bei { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} schluss ist und ein out.of.memory kommt. das wäre für mein anliegen unprakitisch, da ich zwar nicht weiss, wie viele stellen ich brauche, aber 10 sind es mindestens.
da ich noch nicht weiss, ob das nun am int und der beschränkung liegt oder sonst woran (da ich noch nicht alles nachvollzogen habe), frage ich schonmal hier zurück .

aber bis zu 10 stellen läuft das echt prima!

Andreas

 

[Ebenius]

@OutOfMemoryError: Das sind ja auch 10! (10 Fakultät) also 3.628.800 (in Worten drei komma 6 Million) int[]-Arrays die da gespeichert werden sollen. Da bekommst Du zu Recht einen OutOfMemoryError, wenn Du die VM nicht mit mehr Speicher startest.

[ edit ] Ich hatte Dich so verstanden, dass Du die Ergebnisse gespeichert brauchst. Wenn Du's nur ausgeben willst, dann geht das Programm natürlich auch ein ganzes Stück sparsamer und einfacher.

Ebenius

 

[-horn-]

@OutOfMemoryError: Das sind ja auch 10! (10 Fakultät) also 3.628.800 (in Worten drei komma 6 Million) int[]-Arrays die da gespeichert werden sollen. Da bekommst Du zu Recht einen OutOfMemoryError, wenn Du die VM nicht mit mehr Speicher startest.

Ebenius

jap, hatte ich auch ausgerechnet, nur wusste ich noch nicht, dass die alle gespeichert werden. ich brauch die nicht permanent, wenn ich die eine zahlereihe habe würde ich die aufgabe dafür schnell abarbeiten lassen und danach brauch ich die nicht mehr und danach kann die nächste reihe dran, usw. für einen späteren zugriff auf ein riesen array habe ich auch keine verwendung .

grüße, Andreas

 

[Ebenius]

In dem Fall ist's einfacher:

/**
 * Test main method.
 * 
 * @param args ignored
 */
public static void main(String[] args) {

  final int[][] testInputs =
        { { 1 }, { 1, 2 }, { 1, 2, 3 }, { 2, 3, 5, 7, 11, } };
  for (int[] input : testInputs) {
    System.out.print("Eingangswerte: ");
    print(input);
    System.out.println("-------------------------------------------------");
    kombiniere2(input, 0);
    System.out.println();
  }
}

private static void print(int[] array) {
  for (int i = 0; i < array.length - 1; i++) {
    System.out.print(array[i]);
    System.out.print(", ");
  }
  System.out.println(array[array.length - 1]);
}

private static void kombiniere2(int[] array, int splitIndex) {
  if (array.length == splitIndex + 1) {
    // done
    print(array);
    return;
  }

  final int[] clonedTail = array.clone();
  for (int i = splitIndex; i < array.length; i++) {
    System.arraycopy(array, splitIndex, clonedTail, splitIndex,
          array.length - splitIndex - 1);
    
    final int tmp = clonedTail[splitIndex];
    clonedTail[splitIndex] = clonedTail[i];
    clonedTail[i] = tmp;
    
    kombiniere2(clonedTail, splitIndex + 1);
  }
}