生成列表所有可能排列的算法是什么？

Java版本

/**
 * @param uniqueList
 * @param permutationSize
 * @param permutation
 * @param only            Only show the permutation of permutationSize,
 *                        else show all permutation of less than or equal to permutationSize.
 */
public static void my_permutationOf(List<Integer> uniqueList, int permutationSize, List<Integer> permutation, boolean only) {
    if (permutation == null) {
        assert 0 < permutationSize && permutationSize <= uniqueList.size();
        permutation = new ArrayList<>(permutationSize);
        if (!only) {
            System.out.println(Arrays.toString(permutation.toArray()));
        }
    }
    for (int i : uniqueList) {
        if (permutation.contains(i)) {
            continue;
        }
        permutation.add(i);
        if (!only) {
            System.out.println(Arrays.toString(permutation.toArray()));
        } else if (permutation.size() == permutationSize) {
            System.out.println(Arrays.toString(permutation.toArray()));
        }
        if (permutation.size() < permutationSize) {
            my_permutationOf(uniqueList, permutationSize, permutation, only);
        }
        permutation.remove(permutation.size() - 1);
    }
}

public static void main(String[] args) throws Exception { 
    my_permutationOf(new ArrayList<Integer>() {
        {
            add(1);
            add(2);
            add(3);

        }
    }, 3, null, true);
}

输出：

  [1, 2, 3]
  [1, 3, 2]
  [2, 1, 3]
  [2, 3, 1]
  [3, 1, 2]
  [3, 2, 1]

这是一个排列的Java版本。

public class Permutation {

    static void permute(String str) {
        permute(str.toCharArray(), 0, str.length());
    }

    static void permute(char [] str, int low, int high) {
        if (low == high) {
            System.out.println(str);
            return;
        }

        for (int i=low; i<high; i++) {
            swap(str, i, low);
            permute(str, low+1, high);
            swap(str, low, i);
        }

    }

    static void swap(char [] array, int i, int j) {
        char t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}

以下是Python代码，用于打印列表的所有可能排列：

def next_perm(arr):
    # Find non-increasing suffix
    i = len(arr) - 1
    while i > 0 and arr[i - 1] >= arr[i]:
        i -= 1
    if i <= 0:
        return False

    # Find successor to pivot
    j = len(arr) - 1
    while arr[j] <= arr[i - 1]:
        j -= 1
    arr[i - 1], arr[j] = arr[j], arr[i - 1]

    # Reverse suffix
    arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
    print arr
    return True

def all_perm(arr):
    a = next_perm(arr)
    while a:
        a = next_perm(arr)
    arr = raw_input()
    arr.split(' ')
    arr = map(int, arr)
    arr.sort()
    print arr
    all_perm(arr)

我曾使用过一种字典序算法来获取所有可能的排列，但递归算法更有效。你可以在这里找到递归算法的代码： Python递归排列

以下是用Python实现的另一种方法，它不像@cdiggins的算法那样就地执行，但我认为更容易理解。

def permute(num):
    if len(num) == 2:
        # get the permutations of the last 2 numbers by swapping them
        yield num
        num[0], num[1] = num[1], num[0]
        yield num
    else:
        for i in range(0, len(num)):
            # fix the first number and get the permutations of the rest of numbers
            for perm in permute(num[0:i] + num[i+1:len(num)]):
                yield [num[i]] + perm

for p in permute([1, 2, 3, 4]):
    print p

#include <stdio.h>
#include <conio.h>
#include <malloc.h>

                //PROTOTYPES

int fact(int);                  //For finding the factorial
void swap(int*,int*);           //Swapping 2 given numbers
void sort(int*,int);            //Sorting the list from the specified path
int imax(int*,int,int);         //Finding the value of imax
int jsmall(int*,int);           //Gives position of element greater than ith but smaller than rest (ahead of imax)
void perm();                    //All the important tasks are done in this function


int n;                         //Global variable for input OR number of digits

void main()
{
int c=0;

printf("Enter the number : ");
scanf("%d",&c);
perm(c);
getch();
}

void perm(int c){
int *p;                     //Pointer for allocating separate memory to every single entered digit like arrays
int i, d;               
int sum=0;
int j, k;
long f;

n = 0;

while(c != 0)               //this one is for calculating the number of digits in the entered number
{
    sum = (sum * 10) + (c % 10);
    n++;                            //as i told at the start of loop
    c = c / 10;
}

f = fact(n);                        //It gives the factorial value of any number

p = (int*) malloc(n*sizeof(int));                //Dynamically allocation of array of n elements

for(i=0; sum != 0 ; i++)
{
    *(p+i) = sum % 10;                               //Giving values in dynamic array like 1234....n separately
    sum = sum / 10;
}

sort(p,-1);                                         //For sorting the dynamic array "p"

for(c=0 ; c<f/2 ; c++) {                        //Most important loop which prints 2 numbers per loop, so it goes upto 1/2 of fact(n)

    for(k=0 ; k<n ; k++)
        printf("%d",p[k]);                       //Loop for printing one of permutations
    printf("\n");

    i = d = 0;
    i = imax(p,i,d);                            //provides the max i as per algo (i am restricted to this only)
    j = i;
    j = jsmall(p,j);                            //provides smallest i val as per algo
    swap(&p[i],&p[j]);

    for(k=0 ; k<n ; k++)
        printf("%d",p[k]);
    printf("\n");

    i = d = 0;
    i = imax(p,i,d);
    j = i;
    j = jsmall(p,j);
    swap(&p[i],&p[j]);

    sort(p,i);
}
free(p);                                        //Deallocating memory
}

int fact (int a)
{
long f=1;
while(a!=0)
{
    f = f*a;
    a--;
}
return f;
}


void swap(int *p1,int *p2)
{
int temp;
temp = *p1;
*p1 = *p2;
*p2 = temp;
return;
}


void sort(int*p,int t)
{
int i,temp,j;
for(i=t+1 ; i<n-1 ; i++)
{
    for(j=i+1 ; j<n ; j++)
    {
        if(*(p+i) > *(p+j))
        {
            temp = *(p+i);
            *(p+i) = *(p+j);
            *(p+j) = temp;
        }
    }
}
}


int imax(int *p, int i , int d)
{
    while(i<n-1 && d<n-1)
{
    if(*(p+d) < *(p+d+1))
    {   
        i = d;
        d++;
    }
    else
        d++;
}
return i;
}


int jsmall(int *p, int j)
{
int i,small = 32767,k = j;
for (i=j+1 ; i<n ; i++)
{
    if (p[i]<small && p[i]>p[k])
    {     
       small = p[i];
       j = i;
    }
}
return j;
}

void permutate(char[] x, int i, int n){
    x=x.clone();
    if (i==n){
        System.out.print(x);
        System.out.print(" ");
        counter++;}
    else
    {
        for (int j=i; j<=n;j++){
     //   System.out.print(temp); System.out.print(" ");    //Debugger
        swap (x,i,j);
      //  System.out.print(temp); System.out.print(" "+"i="+i+" j="+j+"\n");// Debugger
        permutate(x,i+1,n);
    //    swap (temp,i,j);
    }
    }
}

void swap (char[] x, int a, int b){
char temp = x[a];
x[a]=x[b];
x[b]=temp;
}

我基于研究创建了这个。permutate(qwe, 0, qwe.length-1)。你需要知道的是，你可以选择使用回溯或不使用回溯。

这是一个玩具级的 Ruby 方法，类似于 #permutation.to_a，但可能更容易理解。它的速度非常慢，但只有五行。

def permute(ary)
  return [ary] if ary.size <= 1
  ary.collect_concat.with_index do |e, i|
    rest = ary.dup.tap {|a| a.delete_at(i) }
    permute(rest).collect {|a| a.unshift(e) }
  end
end

    def permutazione(n: List[Int]): List[List[Int]] = permutationeAcc(n, Nil)



def permutationeAcc(n: List[Int], acc: List[Int]): List[List[Int]] = {

    var result: List[List[Int]] = Nil
    for (i ← n if (!(acc contains (i))))
        if (acc.size == n.size-1)
            result = (i :: acc) :: result
        else
            result = result ::: permutationeAcc(n, i :: acc)
    result
}

public array function permutateArray(arr){

    if (not isArray(arguments.arr) ) {
        return ['The ARR argument passed to the permutateArray function is not of type array.'];    
    }

    var len = arrayLen(arguments.arr);
    var perms = [];
    var rest = [];
    var restPerms = [];
    var rpLen = 0;
    var next = [];

    //for one or less item there is only one permutation 
    if (len <= 1) {
        return arguments.arr;
    }

    for (var i=1; i <= len; i++) {
        // copy the original array so as not to change it and then remove the picked (current) element
        rest = arraySlice(arguments.arr, 1);
        arrayDeleteAt(rest, i);

         // recursively get the permutation of the rest of the elements
         restPerms = permutateArray(rest);
         rpLen = arrayLen(restPerms);

        // Now concat each permutation to the current (picked) array, and append the concatenated array to the end result
        for (var j=1; j <= rpLen; j++) {
            // for each array returned, we need to make a fresh copy of the picked(current) element array so as to not change the original array
            next = arraySlice(arguments.arr, i, 1);
            arrayAppend(next, restPerms[j], true);
            arrayAppend(perms, next);
        }
     }

    return perms;
}

如果要在递归中解决排列问题，就必须使用某种语言（方言）的实现开创了这个想法。因此，为了完整起见，在Scheme中可以采用以下一种方法。

(define (permof wd)
  (cond ((null? wd) '())
        ((null? (cdr wd)) (list wd))
        (else
         (let splice ([l '()] [m (car wd)] [r (cdr wd)])
           (append
            (map (lambda (x) (cons m x)) (permof (append l r)))
            (if (null? r)
                '()
                (splice (cons m l) (car r) (cdr r))))))))

调用(permof (list "foo" "bar" "baz"))，我们将得到：

'(("foo" "bar" "baz")
  ("foo" "baz" "bar")
  ("bar" "foo" "baz")
  ("bar" "baz" "foo")
  ("baz" "bar" "foo")
  ("baz" "foo" "bar"))