Alle Kombinationen ausgeben lassen!

[RBr2000]

Hi,

ich soll ein Programm schreiben, daß folgendes können soll:
Ich habe eine gewisse Anzahl von Stellen und für jede dieser Stelle eine Anzahl von Möglichkeiten.

Bsp: 3 Stellen, für die 1. Stelle 3 Möglichkeiten, für die 2. 2 und die 3. 1 . Das Programm soll jetzt alle Möglichkeiten ausgeben. Also für das Beispiel, wäre die Ausgabe

000
010
100
110
200
210

schon super.

Hat jemand ne Idee wie ich das am besten implementieren kann? Ich erwarte natürlich keine komplette Lösung, aber ein Ansatz wäre schon schön. Oder gibts da schon was in der Java API?

Vielen Dank,
Georg

 

[foobar]

Such mal nach Fisher-Yates-Shuffle
http://www.nist.gov/dads/HTML/fisherYatesShuffle.html

 

[moormaster]

Hi,

ich soll ein Programm schreiben, daß folgendes können soll:
Ich habe eine gewisse Anzahl von Stellen und für jede dieser Stelle eine Anzahl von Möglichkeiten.

Bsp: 3 Stellen, für die 1. Stelle 3 Möglichkeiten, für die 2. 2 und die 3. 1 . Das Programm soll jetzt alle Möglichkeiten ausgeben. Also für das Beispiel, wäre die Ausgabe

000
010
100
110
200
210

schon super.

Hat jemand ne Idee wie ich das am besten implementieren kann? Ich erwarte natürlich keine komplette Lösung, aber ein Ansatz wäre schon schön. Oder gibts da schon was in der Java API?

Vielen Dank,
Georg

Du könntest in einem 2 dimensionalen Array ablegen, welche Möglichkeiten es für welche Stelle gibt. Dann könnte man das ganze als Wort betrachten, wobei jede Stelle ein eigenes Alphabeth zugewiesen bekommt. Um nun alle diese Wörter aufzuzählen, könnte man diese Schrittweise "erhöhen", indem man ganz rechts anfängt und jeweils die nächste Möglichkeit einsetzt. Wenn in einer Stelle wieder die erste Möglichkeit eingesetzt wird, so muss auch die Stelle links daneben "erhöht" werden. Sobald die Stelle links wieder beim Ersten Element landet, weiss man, dass man wieder am Anfang ist.

z.B.

 public static int indexOf(String muster, int stelle)
 {
  if (stelle < 0 || stelle >= possibilities[stelle].length)
   return -1;

  for (int i=0;i<possibilities[stelle].length;i++)
  {
   if (possibilities[stelle][i].equals(muster))
    return i
  }

  return -1;   
 }

 ...
 
 public static void main(String[] args)
 {
  String possibilities[] = new int[3];

  // an 0. Stelle gibt es 3 Möglichkeiten
  possibilities[0] = new int[3];
  // an 1. Stelle 2
  possibilities[1] = new int[2];
  // an 2. ...
  possibilities[2] = new int[1];

  // Die genauen Möglichkeiten für jede Stelle festhalten
  possibilites[3][0] = "0";
  possibilites[3][1] = "1";
  possibilites[3][2] = "2";

  possibilites[2][0] = "0";
  possibilites[2][1] = "1";

  possibilites[3][0] = "0";

  // nun steht in possibilites[n][i], wodurch die i te Möglichkeit an der n ten Stelle dargestellt werden soll

  int current = new int[possibilites.length];

  // erste Möglichkeit setzen; an jede Stelle wird die 0. Möglichkeit für jede Stelle gesetzt
  for (int i=0;i<possibilities.length;i++)
   current[i] = possibilites[i][0];

  boolean atEnd = false;

  while (!atEnd)
  {
    // hier einsetzen, was mit den einzelnen Varianten von current passieren soll;
    //ausgabe; in einem array sammeln, etc...

    boolean increased = false;
    int s = current.length-1;
    
    // in der Stelle s jeweils die nächste Möglichkeit einsetzen
    while (!increased)
    {
      int newIndex = indexOf(current[s], s) + 1;

      if (newIndex > possibilities[s].length)
      {
       // wenn alle Möglichkeiten einmal durch sind zur nächsten Stelle gehen und dort ebenfalls den Wert ändern
       newIndex = 0;
       current[s] = possibilites[s][newIndex];
       s--
      }
      else
      {
       current[s] = possibilites[s][newIndex];
       increased = true;  // current um 1 "erhöht"
      }

      // wurden alle Möglichkeiten ausgegeben?
      if (s == -1)
       atEnd = true;
    }
  }
 }

 

[RBr2000]

Danke für die Antworten!
Hat mir sehr geholfen