wake-up-neo.net

Permutationsalgorithmus ohne Rekursion? Java

Ich möchte alle Zahlenkombinationen ohne Wiederholung erhalten. Wie 0,1.2, 0.2.1, 1.2.0, 1.0.2, 2.0.1, 2.1.0 ... Ich habe versucht, eine Zahl zu finden einfaches Schema, konnte aber nicht. Ich habe eine Grafik/einen Baum dafür gezeichnet und dies schreit nach Rekursion ... Aber ich möchte dies ohne Rekursion tun, falls dies möglich ist.

Kann mir bitte jemand dabei helfen?

35
Andreas Hornig

Hier ist ein generischer Permutationszähler, den ich vor einem Jahr geschrieben habe. Es kann auch "Sub-Permutationen" erzeugen:

public class PermUtil <T> {
 private T[] arr;
 private int[] permSwappings;

 public PermUtil(T[] arr) {
  this(arr,arr.length);
 }

 public PermUtil(T[] arr, int permSize) {
  this.arr = arr.clone();
  this.permSwappings = new int[permSize];
  for(int i = 0;i < permSwappings.length;i++)
   permSwappings[i] = i;
 }

 public T[] next() {
  if (arr == null)
   return null;

  T[] res = Arrays.copyOf(arr, permSwappings.length);
  //Prepare next
  int i = permSwappings.length-1;
  while (i >= 0 && permSwappings[i] == arr.length - 1) {
   swap(i, permSwappings[i]); //Undo the swap represented by permSwappings[i]
   permSwappings[i] = i;
   i--;
  }

  if (i < 0)
   arr = null;
  else {   
   int prev = permSwappings[i];
   swap(i, prev);
   int next = prev + 1;
   permSwappings[i] = next;
   swap(i, next);
  }

  return res;
 }

 private void swap(int i, int j) {
  T tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
 }

}

Die Idee hinter meinem Algorithmus ist, dass jede Permutation als unique Sequenz von Swap-Befehlen ausgedrückt werden kann. Für <A, B, C> lässt zum Beispiel die Tauschsequenz 012 alle Elemente an Ort und Stelle, während 122 den Index 0 durch den Index 1 austauscht, dann 1 mit 2 tauscht und dann 2 mit 2 tauscht (dh, der Index bleibt erhalten) Platz). Dies führt zur Permutation BCA. 

Diese Darstellung ist isomorph zur Permutationsdarstellung (d.h. eine Eins-zu-Eins-Beziehung), und es ist sehr leicht, sie zu "erhöhen", wenn der Permutationsraum durchlaufen wird. Bei 4 Elementen beginnt es mit 0123 (ABCD) und endet mit 3333 (DABC).

16
Eyal Schneider

Sie sollten die Tatsache nutzen, dass, wenn Sie alle Permutationen von N-Nummern wünschen, N! Möglichkeiten. Also jede Zahl x von 1..N! kodiert eine solche Permutation. Hier ist ein Beispiel, das iterativ alle Permutationen eines Stiches ausgibt. 

private static void printPermutationsIterative(String string){
        int [] factorials = new int[string.length()+1];
        factorials[0] = 1;
        for (int i = 1; i<=string.length();i++) {
            factorials[i] = factorials[i-1] * i;
        }

        for (int i = 0; i < factorials[string.length()]; i++) {
            String onePermutation="";
            String temp = string;
            int positionCode = i;
            for (int position = string.length(); position > 0 ;position--){
                int selected = positionCode / factorials[position-1];
                onePermutation += temp.charAt(selected);
                positionCode = positionCode % factorials[position-1];
                temp = temp.substring(0,selected) + temp.substring(selected+1);
            }
            System.out.println(onePermutation);
        }
    }
12
Filip Nguyen

Es ist leicht, die rekursive Permutation zu schreiben, es erfordert jedoch den Export der Permutationen aus tief verschachtelten Schleifen. (Das ist eine interessante Übung.) Ich brauchte eine Version, die Strings für Anagramme permutierte. Ich habe eine Version geschrieben, die Iterable<String> implementiert, damit sie in foreach-Schleifen verwendet werden kann. Es kann leicht an andere Typen wie int[] oder sogar an einen generischen Typ <T[]> angepasst werden, indem der Konstruktor und der Typ des Attributs 'array' geändert werden.

import Java.util.Iterator;
import Java.util.NoSuchElementException;

/**
 * An implicit immutable collection of all permutations of a string with an 
 * iterator over the permutations.<p>  implements Iterable&ltString&gt
 * @see #StringPermutation(String)
 */
public class StringPermutation implements Iterable<String> {

    // could implement Collection<String> but it's immutable, so most methods are essentially vacuous

    protected final String string;

    /**
     * Creates an implicit Iterable collection of all permutations of a string
     * @param string  String to be permuted
     * @see Iterable
     * @see #iterator
     */
    public StringPermutation(String string) {
        this.string = string;
    }

    /**
     * Constructs and sequentially returns the permutation values 
     */
    @Override
    public Iterator<String> iterator() {

        return new Iterator<String>() {

            char[] array = string.toCharArray(); 
            int length = string.length();
            int[] index = (length == 0) ? null : new int[length];

            @Override
            public boolean hasNext() {
                return index != null;
            }

            @Override
            public String next() {

                if (index == null) throw new NoSuchElementException();

                for (int i = 1; i < length; ++i) {
                    char swap = array[i];
                    System.arraycopy(array, 0, array, 1, i);
                    array[0] = swap;
                    for (int j = 1 ; j < i; ++j) {
                        index[j] = 0;
                    }
                    if (++index[i] <= i) {
                        return  new String(array);
                    }
                    index[i] = 0;                    
                }
                index = null;
                return new String(array);
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException(); 
            }
        };
    }
}
11
dickf

Im Allgemeinen kann ein rekursiver Algorithmus durch die Verwendung von Stapel- oder Warteschlangendatenstrukturen immer auf einen iterativen Algorithmus reduziert werden.

Für dieses spezielle Problem kann es sinnvoller sein, den C++ - STL-Algorithmus std::next_permutation zu betrachten. Laut Thomas Guest auf wordaligned.org sieht die grundlegende Implementierung folgendermaßen aus:

template<typename Iter>
bool next_permutation(Iter first, Iter last)
{
    if (first == last)
        return false;
    Iter i = first;
    ++i;
    if (i == last)
        return false;
    i = last;
    --i;

    for(;;)
    {
        Iter ii = i;
        --i;
        if (*i < *ii)
        {
            Iter j = last;
            while (!(*i < *--j))
            {}
            std::iter_swap(i, j);
            std::reverse(ii, last);
            return true;
        }
        if (i == first)
        {
            std::reverse(first, last);
            return false;
        }
    }
}

Beachten Sie, dass es keine Rekursion verwendet und es relativ einfach ist, in eine andere C-ähnliche Sprache wie Java zu übersetzen. Vielleicht möchten Sie sich auch über std :: iter_swap , std :: reverse und bidirektionale Iteratoren informieren (was Iter in diesem Code darstellt).

8
bobbymcr

Hier sind die generischen und iterativen Permutations-, kpermutation- und Kombinationsgenerator-Klassen, die ich basierend auf den Implementierungen hier und hier geschrieben habe. Meine Klassen verwenden diese als innere Klassen. Sie implementieren auch Iterable Interface foreachable.

 List<String> objects = new ArrayList<String>();
    objects.add("A");
    objects.add("B");
    objects.add("C");

    Permutations<String> permutations = new Permutations<String>(objects);
    for (List<String> permutation : permutations) {
        System.out.println(permutation);
    }

    Combinations<String> combinations = new Combinations<String>(objects, 2);
    for (List<String> combination : combinations) {
        System.out.println(combination);
    }

    KPermutations<String> kPermutations = new KPermutations<String>(objects, 2);
    for (List<String> kPermutation : kPermutations) {
        System.out.println(kPermutation);
    }

Die Kombinationsklasse:

public class Combinations<T> implements Iterable<List<T>> {

    CombinationGenerator cGenerator;
    T[] elements;
    int[] indices;

    public Combinations(List<T> list, int n) {
        cGenerator = new CombinationGenerator(list.size(), n);
        elements = (T[]) list.toArray();
    }

    public Iterator<List<T>> iterator() {
        return new Iterator<List<T>>() {

            int pos = 0;

            public boolean hasNext() {
                return cGenerator.hasMore();
            }

            public List<T> next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                indices = cGenerator.getNext();
                List<T> combination = new ArrayList<T>();
                for (int i = 0; i < indices.length; i++) {
                    combination.add(elements[indices[i]]);
                }
                return combination;
            }

            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }

    private final class CombinationGenerator {

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

        //------------
        // Constructor
        //------------
        public CombinationGenerator(int n, int r) {
            if (n < 1) {
                throw new IllegalArgumentException("Set must have at least one element");
            }
            if (r > n) {
                throw new IllegalArgumentException("Subset length can not be greater than set length");
            }
            this.n = n;
            this.r = r;
            a = new int[r];
            BigInteger nFact = getFactorial(n);
            BigInteger rFact = getFactorial(r);
            BigInteger nminusrFact = getFactorial(n - r);
            total = nFact.divide(rFact.multiply(nminusrFact));
            reset();
        }

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

        //------------------------------------------------
        // Return number of combinations not yet generated
        //------------------------------------------------
        public BigInteger getNumLeft() {
            return numLeft;
        }

        //-----------------------------
        // Are there more combinations?
        //-----------------------------
        public boolean hasMore() {
            return numLeft.compareTo(BigInteger.ZERO) == 1;
        }

        //------------------------------------
        // Return total number of combinations
        //------------------------------------
        public BigInteger getTotal() {
            return total;
        }

        //------------------
        // Compute factorial
        //------------------
        private 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;
        }

        //--------------------------------------------------------
        // Generate next combination (algorithm from Rosen p. 286)
        //--------------------------------------------------------
        public int[] getNext() {

            if (numLeft.equals(total)) {
                numLeft = numLeft.subtract(BigInteger.ONE);
                return a;
            }

            int i = r - 1;
            while (a[i] == n - r + i) {
                i--;
            }
            a[i] = a[i] + 1;
            for (int j = i + 1; j < r; j++) {
                a[j] = a[i] + j - i;
            }

            numLeft = numLeft.subtract(BigInteger.ONE);
            return a;

        }
    }
}

Die Permutationsklasse: 

public class Permutations<T> implements Iterable<List<T>> {

    PermutationGenerator pGenerator;
    T[] elements;
    int[] indices;

    public Permutations(List<T> list) {
        pGenerator = new PermutationGenerator(list.size());
        elements = (T[]) list.toArray();
    }

    public Iterator<List<T>> iterator() {
        return new Iterator<List<T>>() {

            int pos = 0;

            public boolean hasNext() {
                return pGenerator.hasMore();
            }

            public List<T> next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                indices = pGenerator.getNext();
                List<T> permutation = new ArrayList<T>();
                for (int i = 0; i < indices.length; i++) {
                    permutation.add(elements[indices[i]]);
                }
                return permutation;
            }

            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }

    private final class PermutationGenerator {

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

        //-----------------------------------------------------------
        // Constructor. WARNING: Don't make n too large.
        // Recall that the number of permutations is n!
        // which can be very large, even when n is as small as 20 --
        // 20! = 2,432,902,008,176,640,000 and
        // 21! is too big to fit into a Java long, which is
        // why we use BigInteger instead.
        //----------------------------------------------------------
        public PermutationGenerator(int n) {
            if (n < 1) {
                throw new IllegalArgumentException("Set must have at least one element");
            }
            a = new int[n];
            total = getFactorial(n);
            reset();
        }

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

        //------------------------------------------------
        // Return number of permutations not yet generated
        //------------------------------------------------
        public BigInteger getNumLeft() {
            return numLeft;
        }

        //------------------------------------
        // Return total number of permutations
        //------------------------------------
        public BigInteger getTotal() {
            return total;
        }

        //-----------------------------
        // Are there more permutations?
        //-----------------------------
        public boolean hasMore() {
            return numLeft.compareTo(BigInteger.ZERO) == 1;
        }

        //------------------
        // Compute factorial
        //------------------
        private 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;
        }

        //--------------------------------------------------------
        // Generate next permutation (algorithm from Rosen p. 284)
        //--------------------------------------------------------
        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;
            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;
            while (a[j] > a[k]) {
                k--;
            }

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

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

            // Put tail end of permutation after jth position in increasing order

            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;

        }
    }
}

Und die KPermutations-Klasse, die eigentlich Permutations- und Kombinationsklassen verwendet:

public class KPermutations<T> implements Iterable<List<T>> {
    Combinations<T> combinations;

    public KPermutations(List<T> list, int k) {
        if (k<1){
            throw new IllegalArgumentException("Subset length k must me at least 1");
        }
        combinations = new Combinations<T>(list, k);
    }

    public Iterator<List<T>> iterator() {
        return new Iterator<List<T>>() {
            Iterator<List<T>> it = combinations.iterator();
            Permutations<T> permutations = new Permutations<T>(combinations.iterator().next());

            // Has more combinations but no more permutation for current combination
            public boolean hasNext() {
                if (combinations.iterator().hasNext() && !permutations.iterator().hasNext()){
                    permutations = new Permutations<T>(combinations.iterator().next());
                    return true;
                }
                //Has more permutation for current combination
                else if (permutations.iterator().hasNext()){
                    return true;
                }
                // No more combination and permutation
                return false;
            }

            public List<T> next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                return permutations.iterator().next();
            }

            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }


}
4
hrzafer

Hier habe ich eine Lösung in scala , die von Java aus verwendet werden kann, aber mit viel mehr Code auch in Java implementiert werden kann, um einen Iterator für die vereinfachte for-Schleife verwenden zu können: 

for (List<Integer> list: permutations) 
    doSomething (list);

Permutation tree

Um die vereinfachte for-Schleife zu ermöglichen, müssen wir Iterable implementieren. Das bedeutet, dass wir eine Methode bereitstellen müssen, die einen Iterator zurückgibt, der zufällig eine andere Schnittstelle ist. Das bedeutet, dass wir 3 Methoden implementieren müssen: hasNext (); Nächster (); und entferne (); 

import Java.util.*;

class PermutationIterator <T> implements Iterator <List <T>> {

    private int  current = 0;
    private final List <T> lilio;
    public final long last;

    public PermutationIterator (final List <T> llo) {
        lilio = llo;
        long product = 1;
        for (long p = 1; p <= llo.size (); ++p) 
            product *= p; 
        last = product;
    }

    public boolean hasNext () {
        return current != last;
    }

    public List <T> next () {
        ++current;
        return get (current - 1, lilio);
    }

    public void remove () {
        ++current;
    }

    private long fac (long l) 
    {
        for (long i = l - 1L; i > 1L; --i)
            l *= i; 
        return l;
    }
    /**
        new version, which produces permutations in increasing order:
    */
    private List <T> get (final long code, final List <T> list) {
        if (list.isEmpty ()) 
            return list;
        else
        {
            int len = list.size ();     // len = 4
            long max = fac (len);       // max = 24
            long divisor = max / len;   // divisor = 6
            int i = (int) (code / divisor); // i = 2
            List <T> second = new ArrayList <T> (list.size ());
            second.addAll (list);
            T el = second.remove (i);
            List <T> tt = new ArrayList <T> ();
            tt.add (el);
            tt.addAll (get (code - divisor * i, second));
            return tt;
        }
    }

    public List <T> get (final int code) 
    {
        return get (code, lilio);
    }
}

class PermutationIterable <T> implements Iterable <List <T>> {

    private List <T> lilio; 

    public PermutationIterable (List <T> llo) {
        lilio = llo;
    }

    public Iterator <List <T>> iterator () {
        return new PermutationIterator <T> (lilio);
    }

    private long invers (final List <T> pattern, final List <T> matcher)
    {
        if (pattern.isEmpty ())
            return 0L;
        T first = pattern.get (0);
        int idx = matcher.indexOf (first);
        long l = (pattern.size () - 1L) * idx;
        pattern.remove (0);
        matcher.remove (idx);
        return l + invers (pattern, matcher);
    }
    /**
      make a deep copy, since the called method will destroy the parameters
    */
    public long invers (final List <T> lt)
    {
        List <T> copy = new ArrayList <T> (lilio.size ());
        copy.addAll (lilio);
        return invers (lt, copy); 
    }   
}

class PermutationIteratorTest {

    public static List <Integer> genList (int... a) {
        List <Integer> li = new ArrayList <Integer> ();
        for (int i: a) 
            li.add (i);
        return li;
    }

    public static void main (String[] args) {
        List <Integer> il = new ArrayList <Integer> ();
        // autoboxing, add '0' to 'z' as Character: 
        for (int c = 0; c < 3; ++c)
        {
            il.add (c);
        }
        PermutationIterable <Integer> pi = new PermutationIterable <Integer> (il);
        for (List<Integer> li: pi)
            show (li);
        System.out.println ("-again-");
        // do it a second time: 
        for (List <Integer> li: pi)
            show (li);
        // test the inverse:
        System.out.println ("for (2,1,0) expecting 5 ?= " + pi.invers (genList (2, 1, 0)));
        System.out.println ("for (2,0,1) expecting 4 ?= " + pi.invers (genList (2, 0, 1)));
        System.out.println ("for (1,0,2) expecting 3 ?= " + pi.invers (genList (1, 2, 0)));
        System.out.println ("for (1,2,0) expecting 2 ?= " + pi.invers (genList (1, 0, 2)));
        System.out.println ("for (0,2,1) expecting 1 ?= " + pi.invers (genList (0, 2, 1)));
        System.out.println ("for (0,1,2) expecting 0 ?= " + pi.invers (genList (0, 1, 2)));
        Random r = new Random ();
        PermutationIterator <Integer> pitor = (PermutationIterator  <Integer>) pi.iterator ();
        for (int i = 0; i < 10; ++i)
        {
            int rnd = r.nextInt ((int) pitor.last); 
            List <Integer> rli = pitor.get (rnd);
            show (rli);
        }
    }

    public static void show (List <?> lo) {
        System.out.print ("(");
        for (Object o: lo)
            System.out.print (o);
        System.out.println (")");
    }
}

PermutationIterator enthält die zusätzliche, öffentliche Methode public List <T> get (final int code), die praktisch ist, wenn Sie eine bestimmte Permutation nach Index auswählen möchten, beispielsweise nach dem Zufallsprinzip. Sie kennen die Größe (zuletzt) ​​und können daher den gültigen Bereich nach Index permutieren. 

PermutationIterable enthält eine Methode 'invers', die das Gegenteil erzeugt: Der Index einer bestimmten Permutation. 

Intern arbeiten invers und get rekursiv, aber alle Permutationen werden nicht rekursiv erzeugt. Dies sollte auch für große Permutationen kein Problem sein. Beachten Sie, dass Sie für 21 Elemente die Länge von Longs überschreiten und 20 Rekursionsschritte kein Problem darstellen sollten.

3
user unknown

Die meisten Beispiele, die ich bisher gesehen habe, waren entweder zu kompliziert, nur mit Strings oder mit Swaps. Daher dachte ich, ich würde einen machen, der iterativ, intuitiv, generisch und Swap-frei ist.

public static <T> List<List<T>> permutations(List<T> es){

  List<List<T>> permutations = new ArrayList<List<T>>();

  if(es.isEmpty()){
    return permutations;
  }

  // We add the first element
  permutations.add(new ArrayList<T>(Arrays.asList(es.get(0))));

  // Then, for all elements e in es (except from the first)
  for (int i = 1, len = es.size(); i < len; i++) {
    T e = es.get(i);

    // We take remove each list l from 'permutations'
    for (int j = permutations.size() - 1; j >= 0; j--) {
      List<T> l = permutations.remove(j);

      // And adds a copy of l, with e inserted at index k for each position k in l
      for (int k = l.size(); k >= 0; k--) {
        ArrayList<T> ts2 = new ArrayList<>(l);
        ts2.add(k, e);
        permutations.add(ts2);
      }
    }
  }
  return permutations;
}

Beispiel: Wir wollen alle Permutationen von [a, b, c] 
Wir addieren a und erhalten [a] // [b, c] übrig
Wir nehmen a aus der Liste und fügen [a, b] und [b, a] // [c] hinzu
Wir entfernen [b, a] und Einsätze [b, a, c], [b, c, a], [c, b, a] und entfernen dann [a, b] und Einsätze [a , b, c], [a, c, b], [c, a, b] 

3
Mattias F

Sie können Factoradics (Sie können eine Implementierung hier sehen) oder den Knuths L-Algorithmus verwenden, der alle Permutationen generiert. Das Folgende ist eine Implementierung der späteren:

public class Perm {
    public static void main(String... args) {
        final int N = 5;
        int[] sequence = new int[N];
        for (int i = 0; i < N; i++) {
            sequence[i] = i + 1;
        }

        printSequence(sequence);
        permutations(sequence);
    }

    private static int factorial(int n) {
        int fact = 1;
        for (int i = 1; i <= n; i++) {
            fact *= i;
        }
        return fact;
    }

    private static void swap(int[] elements, int i, int j) {
        int temp = elements[i];
        elements[i] = elements[j];
        elements[j] = temp;
    }

    /**
     * Reverses the elements of an array (in place) from the start index to the end index 
     */
    private static void reverse(int[] array, int startIndex, int endIndex) {
        int size = endIndex + 1 - startIndex;
        int limit = startIndex + size / 2;
        for (int i = startIndex; i < limit; i++) {
            // swap(array, i, startIndex + (size - 1 - (i - startIndex)));
            swap(array, i, 2 * startIndex + size - 1 - i);
        }
    }

    private static void printSequence(int[] sequence) {
        for (int i = 0; i < sequence.length; i++) {
            System.out.printf("%d, ", sequence[i]);
        }
        System.out.println();
    }

    /**
     * Implements the Knuth's L-Algorithm permutation algorithm 
     * modifying the collection in place
     */
    private static void permutations(int[] sequence) {
        final int N = sequence.length;
        // There are n! permutations, but the first permutation is the array without 
        // modifications, so the number of permutations is n! - 1
        int numPermutations = factorial(N) - 1;

        // For every possible permutation 
        for (int n = 0; n < numPermutations; n++) {

            // Iterate the array from right to left in search 
            // of the first couple of elements that are in ascending order
            for (int i = N - 1; i >= 1; i--) {
                // If the elements i and i - 1 are in ascending order
                if (sequence[i - 1] < sequence[i]) {
                    // Then the index "i - 1" becomes our pivot index 
                    int pivotIndex = i - 1;

                    // Scan the elements at the right of the pivot (again, from right to left)
                    // in search of the first element that is bigger
                    // than the pivot and, if found, swap it
                    for (int j = N - 1; j > pivotIndex; j--) {
                        if (sequence[j] > sequence[pivotIndex]) {
                            swap(sequence, j, pivotIndex);
                            break;
                        }
                    }

                    // Now reverse the elements from the right of the pivot index
                    // (this Nice touch to the algorithm avoids the recursion)
                    reverse(sequence, pivotIndex + 1, N - 1);
                    break;
                }
            }

            printSequence(sequence);
        }
    }
}
2
higuaro
IEnumerable<IEnumerable<int>> generatePermutations(int length)
{
    if (length <= 0) throw new ArgumentException();

    var resultCollection = new List<IEnumerable<int>> { new [] { 0 } };

    for (var index = 1; index < length; index++)
    {
        var newResultCollection = new List<IEnumerable<int>>();
        foreach (var result in resultCollection)
        {
            for (var insertIndex = index; insertIndex >= 0; insertIndex--)
            {
                var list = new List<int>(result);
                list.Insert(insertIndex, index);
                newResultCollection.Add(list);
            }
        }
        resultCollection = newResultCollection;
    }

    return resultCollection;
}
1
Vladimir

Dies wurde natürlich schon vorher gemacht, und eine Lösung ist der Bells Permutation Algorithm . Sie finden eine Lösung hier , wo Sie eine rekursive Lösung in Prolog und dem nichtrekursiven Bell-Permutations-Algorithmus finden können in Pascal geschrieben.

Sie in Java umzuwandeln, bleibt dem Leser als Übung überlassen.

0
Anders

Dies ist eine einfache Java Funktion zum Drucken aller möglichen Permutationen (einschließlich der kleineren bis zur leeren Zeichenkette ""). Wenn Sie nur Permutationen mit der gleichen Länge drucken müssen, fügen Sie einfach die if-Anweisung vor der hinzu drucken.

Die Idee ist die gleiche wie Rekursion. Aber anstatt Methodenaufrufe zu stapeln. Wir verwenden eine Datenstruktur (in diesem Beispiel als Liste), um die Permutationen zu stapeln.

import Java.util.LinkedList;
import Java.util.List;


    public class Permutations {

        public void perm(String input) {
            List<String[]> buffer = new LinkedList<>();
            buffer.add(new String[]{input, ""});
            while (!buffer.isEmpty()) {
                String[] perm = buffer.remove(0);
                System.out.println(perm[1]);
                for (int i = 0; i < perm[0].length(); i++) {
                    buffer.add(new String[]{perm[0].substring(0, i) + perm[0].substring(i + 1), perm[1] + perm[0].charAt(i)});
                }
            }
        }

    }
0
Sleem