list 生成列表所有可能排列的算法？

Algorithm to generate all possible permutations of a list?

提问by fent

Say I have a list of n elements, I know there are n! possible ways to order these elements. What is an algorithm to generate all possible orderings of this list? Example, I have list [a, b, c]. The algorithm would return [[a, b, c], [a, c, b,], [b, a, c], [b, c, a], [c, a, b], [c, b, a]].

假设我有一个包含 n 个元素的列表，我知道有 n 个！对这些元素进行排序的可能方法。生成此列表所有可能排序的算法是什么？例如，我有列表 [a, b, c]。该算法将返回 [[a, b, c], [a, c, b,], [b, a, c], [b, c, a], [c, a, b], [c, b ， 一种]]。

I'm reading this here http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

我在这里读这个 http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

But Wikipedia has never been good at explaining. I don't understand much of it.

但维基百科从来不擅长解释。我不太明白。

采纳答案by WhirlWind

Basically, for each item from left to right, all the permutations of the remaining items are generated (and each one is added with the current elements). This can be done recursively (or iteratively if you like pain) until the last item is reached at which point there is only one possible order.

基本上，对于从左到右的每个项目，生成剩余项目的所有排列（并且每个都与当前元素相加）。这可以递归地完成（或者如果你喜欢痛苦，则迭代地完成）直到到达最后一个项目，此时只有一个可能的顺序。

So with the list [1,2,3,4] all the permutations that start with 1 are generated, then all the permutations that start with 2, then 3 then 4.

因此，使用列表 [1,2,3,4] 生成所有以 1 开头的排列，然后生成所有以 2 开头的排列，然后是 3 然后是 4。

This effectively reduces the problem from one of finding permutations of a list of four items to a list of three items. After reducing to 2 and then 1 item lists, all of them will be found.
Example showing process permutations using 3 coloured balls:
(from https://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svg- https://commons.wikimedia.org/wiki/File:Permutations_RGB.svg)

这有效地将问题从查找四项列表的排列之一减少到三项列表。减少到 2 项和 1 项列表后，将全部找到。
使用 3 个彩色球显示过程排列的示例：（
来自https://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svg- https://commons.wikimedia.org/wiki/File:Permutations_RGB。 svg)

回答by cdiggins

Here is an algorithm in Python that works by in place on an array:

这是 Python 中的一个算法，它在数组上就地工作：

def permute(xs, low=0):
    if low + 1 >= len(xs):
        yield xs
    else:
        for p in permute(xs, low + 1):
            yield p        
        for i in range(low + 1, len(xs)):        
            xs[low], xs[i] = xs[i], xs[low]
            for p in permute(xs, low + 1):
                yield p        
            xs[low], xs[i] = xs[i], xs[low]

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

You can try the code out for yourself here: http://repl.it/J9v

您可以在这里自己尝试代码：http: //repl.it/J9v

回答by Peter Breuer

Wikipedia's answer for "lexicographic order" seems perfectly explicit in cookbook style to me. It cites a 14th century origin for the algorithm!

维基百科对“词典顺序”的回答对我来说在食谱风格中似乎非常明确。它引用了该算法的 14 世纪起源！

I've just written a quick implementation in Java of Wikipedia's algorithm as a check and it was no trouble. But what you have in your Q as an example is NOT "list all permutations", but "a LIST of all permutations", so wikipedia won't be a lot of help to you. You need a language in which lists of permutations are feasibly constructed. And believe me, lists a few billion long are not usually handled in imperative languages. You really want a non-strict functional programming language, in which lists are a first-class object, to get out stuff while not bringing the machine close to heat death of the Universe.

我刚刚用 Java 编写了一个维基百科算法的快速实现作为检查，这没有问题。但是您在 Q 中的示例不是“列出所有排列”，而是“所有排列的列表”，因此维基百科不会对您有很大帮助。您需要一种可以在其中构建排列列表的语言。相信我，数十亿长的列表通常不会用命令式语言处理。你真的想要一种非严格的函数式编程语言，其中列表是一流的对象，在不让机器接近宇宙热死的情况下取出东西。

That's easy. In standard Haskell or any modern FP language:

这很容易。在标准 Haskell 或任何现代 FP 语言中：

-- perms of a list
perms :: [a] -> [ [a] ]
perms (a:as) = [bs ++ a:cs | perm <- perms as, (bs,cs) <- splits perm]
perms []     = [ [] ]

and

和

-- ways of splitting a list into two parts
splits :: [a] -> [ ([a],[a]) ]
splits []     = [ ([],[]) ]
splits (a:as) = ([],a:as) : [(a:bs,cs) | (bs,cs) <- splits as]

回答by Alexander Galkin

There is already plenty of good solutions here, but I would like to share how I solved this problem on my own and hope that this might be helpful for somebody who would also like to derive his own solution.

这里已经有很多好的解决方案，但我想分享我是如何自己解决这个问题的，并希望这可能对那些也想得出自己的解决方案的人有所帮助。

After some pondering about the problem I have come up with two following conclusions:

经过一番思考这个问题，我得出了以下两个结论：

1. For the list Lof size nthere will be equal number of solutions starting with L₁, L₂... L_nelements of the list. Since in total there are n!permutations of the list of size n, we get n! / n = (n-1)!permutations in each group.
2. The list of 2 elements has only 2 permutations => [a,b]and [b,a].

1. 对于L大小列表，n将从列表的L ₁、L ₂... L _n元素开始的解决方案数量相同。由于总共有n!size 列表的排列n，我们n! / n = (n-1)!在每个组中得到排列。
2. 2 个元素的列表只有 2 个排列 =>[a,b]和[b,a]。

Using these two simple ideas I have derived the following algorithm:

使用这两个简单的想法，我得出了以下算法：

permute array
    if array is of size 2
       return first and second element as new array
       return second and first element as new array
    else
        for each element in array
            new subarray = array with excluded element
            return element + permute subarray

Here is how I implemented this in C#:

这是我在 C# 中实现的方法：

public IEnumerable<List<T>> Permutate<T>(List<T> input)
{
    if (input.Count == 2) // this are permutations of array of size 2
    {
        yield return new List<T>(input);
        yield return new List<T> {input[1], input[0]}; 
    }
    else
    {
        foreach(T elem in input) // going through array
        {
            var rlist = new List<T>(input); // creating subarray = array
            rlist.Remove(elem); // removing element
            foreach(List<T> retlist in Permutate(rlist))
            {
                retlist.Insert(0,elem); // inserting the element at pos 0
                yield return retlist;
            }

        }
    }
}

回答by dinadineke

As WhirlWind said, you start at the beginning.

正如 WhirlWind 所说，您从头开始。

You swap cursor with each remaining value, including cursor itself, these are all new instances (I used an int[]and array.clone()in the example).

您将光标与每个剩余值交换，包括光标本身，这些都是新实例（我在示例中使用了int[]和array.clone()）。

Then perform permutations on all these different lists, making sure the cursor is one to the right.

然后对所有这些不同的列表执行排列，确保光标位于右侧。

When there are no more remaining values (cursor is at the end), print the list. This is the stop condition.

当没有更多剩余值时（光标在末尾），打印列表。这是停止条件。

public void permutate(int[] list, int pointer) {
    if (pointer == list.length) {
        //stop-condition: print or process number
        return;
    }
    for (int i = pointer; i < list.length; i++) {
        int[] permutation = (int[])list.clone();.
        permutation[pointer] = list[i];
        permutation[i] = list[pointer];
        permutate(permutation, pointer + 1);
    }
}

回答by Hui Zhou

Recursive always takes some mental effort to maintain. And for big numbers, factorial is easily huge and stack overflow will easily be a problem.

递归总是需要一些精神上的努力来维护。对于大数字，阶乘很容易变大，堆栈溢出很容易成为问题。

For small numbers (3 or 4, which is mostly encountered), multiple loops are quite simple and straight forward. It is unfortunate answers with loops didn't get voted up.

对于小数字（3 或 4，这是最常见的），多个循环非常简单和直接。不幸的是，循环的答案没有被投票通过。

Let's start with enumeration (rather than permutation). Simply read the code as pseudo perl code.

让我们从枚举（而不是排列）开始。只需将代码阅读为伪 perl 代码。

$foreach $i1 in @list
    $foreach $i2 in @list 
        $foreach $i3 in @list
            print "$i1, $i2, $i3\n"

Enumeration is more often encountered than permutation, but if permutation is needed, just add the conditions:

枚举比排列更常见，但如果需要排列，只需添加条件：

$foreach $i1 in @list
    $foreach $i2 in @list 
        $if $i2==$i1
            next
        $foreach $i3 in @list
            $if $i3==$i1 or $i3==$i2
                next
            print "$i1, $i2, $i3\n"

Now if you really need general method potentially for big lists, we can use radix method. First, consider the enumeration problem:

现在，如果您确实需要可能用于大列表的通用方法，我们可以使用基数方法。首先考虑枚举问题：

$n=@list
my @radix
$for $i=0:$n
    $radix[$i]=0
$while 1
    my @temp
    $for $i=0:$n
        push @temp, $list[$radix[$i]]
    print join(", ", @temp), "\n"
    $call radix_increment

subcode: radix_increment
    $i=0
    $while 1
        $radix[$i]++
        $if $radix[$i]==$n
            $radix[$i]=0
            $i++
        $else
            last
    $if $i>=$n
        last

Radix increment is essentially number counting (in the base of number of list elements).

基数增量本质上是数字计数（以列表元素的数量为基础）。

Now if you need permutaion, just add the checks inside the loop:

现在，如果您需要排列，只需在循环内添加检查：

subcode: check_permutation
    my @check
    my $flag_dup=0
    $for $i=0:$n
        $check[$radix[$i]]++
        $if $check[$radix[$i]]>1
            $flag_dup=1
            last
    $if $flag_dup
        next

Edit: The above code should work, but for permutation, radix_increment could be wasteful. So if time is a practical concern, we have to change radix_increment into permute_inc:

编辑：上面的代码应该可以工作，但对于排列，radix_increment 可能是浪费的。因此，如果时间是一个实际问题，我们必须将 radix_increment 更改为 permute_inc：

subcode: permute_init
    $for $i=0:$n
        $radix[$i]=$i

subcode: permute_inc                                       
    $max=-1                                                
    $for $i=$n:0                                           
        $if $max<$radix[$i]                                
            $max=$radix[$i]                                
        $else                                              
            $for $j=$n:0                                   
                $if $radix[$j]>$radix[$i]                  
                    $call swap, $radix[$i], $radix[$j]     
                    break                                  
            $j=$i+1                                        
            $k=$n-1                                        
            $while $j<$k                                   
                $call swap, $radix[$j], $radix[$k]         
                $j++                                       
                $k--                                       
            break                                          
    $if $i<0                                               
        break                                              

Of course now this code is logically more complex, I'll leave for reader's exercise.

当然，现在这段代码在逻辑上更加复杂，我将留给读者练习。

回答by Sazzad Hissain Khan

// C program to print all permutations with duplicates allowed
#include <stdio.h>
#include <string.h>

/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */

void permute(char *a, int l, int r)
{
   int i;
   if (l == r)
     printf("%s\n", a);
   else
   {
       for (i = l; i <= r; i++)
       {
          swap((a+l), (a+i));
          permute(a, l+1, r);
          swap((a+l), (a+i)); //backtrack
       }
   }
}

/* Driver program to test above functions */
int main()
{
    char str[] = "ABC";
    int n = strlen(str);
    permute(str, 0, n-1);
    return 0;
}

Reference: Geeksforgeeks.org

参考：Geeksforgeeks.org

回答by Jhankar Mahbub

If anyone wonders how to be done in permutation in javascript.

如果有人想知道如何在 javascript 中进行排列。

Idea/pseudocode

想法/伪代码

1. pick one element at a time
2. permute rest of the element and then add the picked element to the all of the permutation

1. 一次选择一个元素
2. 置换元素的其余部分，然后将选取的元素添加到所有置换中

for example. 'a'+ permute(bc). permute of bc would be bc & cb. Now add these two will give abc, acb. similarly, pick b + permute (ac) will provice bac, bca...and keep going.

例如。'a'+ 置换（bc）。bc 的置换将是 bc & cb。现在添加这两个将得到 abc，acb。类似地，pick b + permute (ac) 将提供 bac、bca ......并继续前进。

now look at the code

现在看代码

function permutations(arr){

   var len = arr.length, 
       perms = [],
       rest,
       picked,
       restPerms,
       next;

    //for one or less item there is only one permutation 
    if (len <= 1)
        return [arr];

    for (var i=0; i<len; i++)
    {
        //copy original array to avoid changing it while picking elements
        rest = Object.create(arr);

        //splice removed element change array original array(copied array)
        //[1,2,3,4].splice(2,1) will return [3] and remaining array = [1,2,4]
        picked = rest.splice(i, 1);

        //get the permutation of the rest of the elements
        restPerms = permutations(rest);

       // Now concat like a+permute(bc) for each
       for (var j=0; j<restPerms.length; j++)
       {
           next = picked.concat(restPerms[j]);
           perms.push(next);
       }
    }

   return perms;
}

Take your time to understand this. I got this code from (pertumation in JavaScript)

花点时间了解这一点。我从（JavaScript 中的 pertumation）得到了这段代码

回答by zhywu

Another one in Python, it's not in place as @cdiggins's, but I think it's easier to understand

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

回答by FreakPirate

I was thinking of writing a code for getting the permutations of any given integer of any size, i.e., providing a number 4567 we get all possible permutations till 7654...So i worked on it and found an algorithm and finally implemented it, Here is the code written in "c". You can simply copy it and run on any open source compilers. But some flaws are waiting to be debugged. Please appreciate.

我正在考虑编写一个代码来获取任何大小的任何给定整数的排列，即，提供一个数字 4567 我们得到所有可能的排列直到 7654 ......所以我研究它并找到了一个算法并最终实现了它，这里是用“c”编写的代码。您可以简单地复制它并在任何开源编译器上运行。但有些缺陷正在等待调试。请欣赏。

Code:

代码：

#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;
}