Permutation

[Tauboga]

Kann mir bitte jemand erklären was eigentich die Funktion getNext ()
macht und wie sie es schafft (nach welcher Logik, Methodik welchem Verfahren) die Indizes der Arrays so zu vertauschen, dass alle Anordnungsmöglichkeiten auch wirklich berücksichtigt werden?

Grüße

import java.math.BigInteger;

public class PermutationGenerator {

  private int[] a;
  private BigInteger numLeft;
  private BigInteger total;

  public PermutationGenerator (int n) 
  {
    if (n < 1) 
    {
      throw new IllegalArgumentException ("Min 1");
    }
    a = new int[n];
    total = getFactorial (n);
    reset ();
   }

  public void reset () 
  {
    for (int i = 0; i < a.length; i++) 
    {
      a[i] = i;
    }
    numLeft = new BigInteger (total.toString ());
  }

  public BigInteger getNumLeft () {
    return numLeft;
  }

  public BigInteger getTotal () {
    return total;
  }

  public boolean hasMore () {
    return numLeft.compareTo (BigInteger.ZERO) == 1;
  }

  private static BigInteger getFactorial (int n) {
    BigInteger fact = BigInteger.ONE;
    for (int i = n; i > 1; i--) {
      fact = fact.multiply (new BigInteger (Integer.toString (i)));
    }
    return fact;
  }

  public int[] getNext () {

    if (numLeft.equals (total)) {

      numLeft = numLeft.subtract (BigInteger.ONE);

      return a;
    }

    int temp;

    // Find largest index j with a[j] < a[j+1]

    int j = a.length - 2;
    //System.out.print ("j " + j+ "\t");
    while (a[j] > a[j+1]) {

      --j;

    }

    // Find index k such that a[k] is smallest integer
    // greater than a[j] to the right of a[j]

    int k = a.length - 1;
    //System.out.print ("k " + k + "\t");
    while (a[j] > a[k]) {
      k--;

    }

    // Interchange a[j] and a[k]

    temp = a[k];
    a[k] = a[j];
    a[j] = temp;

    int r = a.length - 1;
    int s = j + 1;

    while (r > s) {
      temp = a[s];
      a[s] = a[r];
      a[r] = temp;
      r--;
      s++;

      }

    numLeft = numLeft.subtract (BigInteger.ONE);

    return a;

  }

 public static void main(String[] args)
  {
  int[] indices;
  String[] elements = {"A","B","C"};
  PermutationGenerator x = new PermutationGenerator (elements.length);
  StringBuffer permutation;
  while (x.hasMore ()) {
  permutation = new StringBuffer ();
  indices = x.getNext ();
  for (int i = 0; i < indices.length; i++)  //indices.length 3    i= 0,1,2
  {

      System.out.print (indices[i] + "\t");
  }
  for (int i = 0; i < indices.length; i++) 
  {
    permutation.append (elements[indices[i]]);
  }
  System.out.println (permutation.toString ());

}

}
}

/*
Ergebnis
0 1 2 ABC
0 2 1 ACB
1 0 2 BAC
1 2 0 BCA
2 0 1 CAB
2 1 0 CBA
*/

[CengizS]

Siehe auch hier: http://forum.javacore.de/viewtopic.php?t=1608

Danke für das Doppelpost ...

[Tauboga]

Hallo Cengiz!
Du hast Recht das war nicht so toll, hoffe kannst dieses Mal (letztes Mal)
ein Auge zudrücken(Budefa affet sana yanlis yapmak istemem).

Grüße
image

[Sgt Nukem]

Budefa affet sana yanlis yapmak istemem

ROFLMAO