Алгоритм генерации всех возможных перестановок списка?

Question

Скажем, у меня есть список из n элементов, я знаю, что есть n! Возможные способы заказа этих элементов. Что такое алгоритм для генерации всех возможных упорядочений этого списка? Например, у меня есть список [a, b, c]. Алгоритм возвращает [[a, b, c], [a, c, b,], [b, a, c], [b, c, a], [c, a, b], [c, b , а]].

Я читаю это здесь http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

Но Википедия никогда не умела объяснять. Я мало что понимаю.

Answer 1

Это рекурсивный код для Java, идея состоит в том, чтобы иметь префикс, который добавляет остальные символы:

public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str);
    }
}

Пример:

Input = "ABC"; Выход:

ABC ACB BAC BCA ТАКСИ CBA

Answer 2

Это производит их по одному, не составляя списка - тот же конечный результат, что и ответ Мариоса Чудари (или просто вызывая nextPermute C ++, как отвечает Андерс) Но это алгоритм Heap (нерекурсивная версия) перестроен и является классом для сохранения контекста. Используется как:

P5=new genPermutes_t(5); // P5.P is now [0,1,2,3,4]
while(!P5.isDone()) {
  // use P5.P here
  P5.next();
}

Код написан на C # без одобрения. Переменные взяты из псевдокода Heap, к которому также относятся комментарии:

public class genPermutes_t {
  public int[] P; // the current permuation

  private int n, i; // vars from the original algorithm
  private int[] c; // ditto

  public genPermutes_t(int count) {
    // init algorithm:
    n=count;
    i=0;
    c=new int[n];
    for(int j=0;j<n;j++) c[j]=0;

    // start current permutation as 0,1 ... n-1:
    P=new int[n];
    for(int j=0;j<n;j++) P[j]=j;
  }

  public bool isDone() {
    return i>=n; // condition on the original while loop
  }

  public void next() {
    // the part of the loop that spins until done or ready for next permute:
    while(i<n && c[i]>=i) {
      c[i]=0;
      i++;
    }
    // pulled from inside loop -- the part that makes next permute:
    if(i<n) { // if not done
      if(i%2==0) swap(0,i);
      else swap(c[i], i);
      // "print P" removed. User will simply examine it
      c[i]+=1;
      i=0;
    }
  }

  private void swap(int i1, int i2) {int tmp=P[i1]; P[i1]=P[i2]; P[i2]=tmp;}
}

Answer 3

Раствор Bourne shell - всего четыре строки (без теста для случая без параметров):

test $# -eq 1 && echo "$1" && exit
for i in $*; do
  $0 `echo "$*" | sed -e "s/$i//"` | sed -e "s/^/$i /"
done