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

Question

假设我有一个包含n个元素的列表，我知道有n!种可能的方式来排列这些元素。如何生成此列表所有可能的排列？例如，我有列表[a, b, c]。该算法将返回[[a, b, c]，[a, c, b]，[b, a, c]，[b, c, a]，[c, a, b]，[c, b, a]]。

我正在阅读这里：http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations，但维基百科从来没有擅长解释，我不太理解其中的大部分内容。

答案：可以使用递归算法来生成列表的所有排列。首先，选择一个元素作为第一个元素，并将其与列表中的其他元素交换。然后，对剩余的元素进行递归处理，直到只剩下一个元素时，生成一种排列。重复此过程，每次选择一个新的第一个元素。最终，将得到所有可能的排列组合。

- fent

---

我曾经在回答另一个问题时，详细讲解了如何生成排列。我认为您会感兴趣：https://dev59.com/-HI_5IYBdhLWcg3wJfgM#1506337 - Joren

这可以解决你的问题：http://en.wikipedia.org/wiki/Heap's_algorithm - Felix

我写了一篇博客文章，解释了如何生成几种不同类型的组合函数。https://www.axiomtutor.com/new-blog/2022/8/3/combinatorics-simulated-in-python-using-sympy - Addem

Answer 1

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

因此，对于列表[1,2,3,4]，将生成以1开头的所有排列，然后是以2、3和4开头的所有排列。

这有效地将问题从查找四个项目列表的排列问题减少为三个项目列表。在缩小到2和1项列表后，所有排列都将被找到。
以下是使用3个彩色球显示排列过程的示例：
（来自https://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svg - https://commons.wikimedia.org/wiki/File:Permutations_RGB.svg）

- WhirlWind

---

我一开始也考虑过这个，但是当前元素就无法放置在其后面的某些元素之间。因此，并非所有的排列组合都会被生成。 - fent

@LLer 抱歉，我更新了我的答案，从“folllowing”更改为“remaining”，以澄清。它仍然可以正常工作。通过编写代码并验证您获得4！不同的结果来检查它。 - WhirlWind

int permutations(int n, vector<int> a) { static int num_permutations=0; if (n==(a.size() - 1)) { for (int i=0; i<a.size(); i++) cout<<a[i]<<" "; cout<<"\n"; num_permutations++; } else { for (int i=n+1; i<=a.size(); i++) { permutations(n+1, a); if (i<a.size()) int temp=a[n], a[n]=a[i], a[i]=temp; } } return num_permutations; } int main(void) { vector<int> v; v.push_back(1); ... return permutations(0, v); } - Somesh

糟糕 - 不确定如何在注释中格式化代码...使用7测试了代码，得到了5040。感谢@WhirlWind的建议。 - Somesh

如果你可以有2个或3个红色#1球，而不仅仅是每种颜色只有1个，那么这个算法会改变吗？ - Alexander Mills

Answer 2

这里是一个使用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

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

- cdiggins

---

请问您能解释一下yield部分吗？我无法运行代码。先谢谢了。 - Agniswar Bakshi

Stack Overflow上的问题https://dev59.com/OHVD5IYBdhLWcg3wDXJ3指出，从2.6版本开始有一个标准库模块，并提供了一个6行函数解决方案来获取列表排列。 - Edward

@Agniswar 一眼看去，yield语句用于定义生成器，取代函数的返回值，以便向调用者提供结果而不破坏本地变量。与函数不同的是，每次调用函数时都会从新的变量集开始，而生成器将在离开时恢复执行。http://pythoncentral.io/python-generators-and-yield-keyword/ - MSS

当处理一系列相同条目的列表时，此解决方案将无法工作。 - KaiserKatze

谢谢分享。这很直观和高效，尽管输出结果不按字典顺序排序。 - Sam

Answer 3

这里已经有很多好的解决方案，但我想分享一下我自己是如何解决这个问题的，并希望这对于那些想要推导出自己的解决方案的人有所帮助。

在思考了一段时间之后，我得出了以下两个结论：

1. 对于大小为n的列表L，以L1、L2 ... Ln元素开头的解决方案数量相等。由于总共有n！个大小为n的列表排列，因此每组中有(n-1)!个排列。 2. 2个元素的列表只有2种排列=>[a,b]和[b,a]。

利用这两个简单的思路，我得出了以下算法：

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

这是我在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;
            }

        }
    }
}

- Alexander Galkin

Answer 4

对于“词典序”的维基百科回答对我来说似乎非常清晰简洁。它引用了一个14世纪的算法起源!

我刚用Java快速实现了维基百科算法进行检查，没什么麻烦。但是你在问题中举的例子不是“列出所有排列”，而是“所有排列的列表”，所以维基百科对你没有太大帮助。你需要一种可以可行地构建排列列表的语言。相信我，长度为几十亿的列表通常无法在命令式语言中处理。你真正想要的是一种非严格的函数式编程语言，其中列表是第一类对象，可以轻松地从中获取内容，而不会使计算机接近宇宙热寂。

这很容易。在标准的Haskell或任何现代的函数式编程语言中：

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

和

-- 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]

- Peter Breuer

Answer 5

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

你需要交换游标和每个剩余的值，包括游标本身，这些都是新的实例（在示例中使用了int[] 和 array.clone()）。

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

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

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

- dinadineke

Answer 6

递归总是需要一定的心理努力来维护。对于大数，阶乘很容易变得非常巨大，并且堆栈溢出将很容易成为一个问题。

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

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

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

枚举经常比排列出现得更多，但如果需要排列，只需添加条件：

$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"

如果您确实需要处理大型列表的通用方法，我们可以使用基数排序。首先考虑枚举问题：

$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

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

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

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

编辑：上面的代码应该可以工作，但是对于排列来说，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                                              

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

- Hui Zhou

Answer 7

我已经在ANSI C中编写了这个递归解决方案。每次执行Permutate函数都会提供一个不同的排列，直到所有排列都完成。全局变量也可以用于变量fact和count。

#include <stdio.h>
#define SIZE 4

void Rotate(int vec[], int size)
{
    int i, j, first;

    first = vec[0];
    for(j = 0, i = 1; i < size; i++, j++)
    {
        vec[j] = vec[i];
    }
    vec[j] = first;
}

int Permutate(int *start, int size, int *count)
{
    static int fact;

    if(size > 1)
    {
        if(Permutate(start + 1, size - 1, count))
        {
            Rotate(start, size);
        }
        fact *= size;
    }
    else
    {
        (*count)++;
        fact = 1;
    }

    return !(*count % fact);
}

void Show(int vec[], int size)
{
    int i;

    printf("%d", vec[0]);
    for(i = 1; i < size; i++)
    {
        printf(" %d", vec[i]);
    }
    putchar('\n');
}

int main()
{
    int vec[] = { 1, 2, 3, 4, 5, 6 }; /* Only the first SIZE items will be permutated */
    int count = 0;

    do
    {
        Show(vec, SIZE);
    } while(!Permutate(vec, SIZE, &count));

    putchar('\n');
    Show(vec, SIZE);
    printf("\nCount: %d\n\n", count);

    return 0;
}

- Horacio

Answer 8

如果有人想知道如何在JavaScript中进行排列，以下是一些想法/伪代码：

1. 逐个选择元素。 2. 对其余的元素进行排列，然后将所选元素添加到所有排列中。

例如，'a'+ permute(bc)。bc的排列是bc和cb。现在将这两个排列相加得到abc、acb。同样，选择b + permute(ac)会得到bac、bca...以此类推。

现在看看代码。

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

请仔细阅读以下内容，这段代码是从 (JavaScript中的排列组合) 获取的。

- Jhankar Mahbub

---

我在考虑类似的事情，但是你不应该将选定的元素添加到restParams的前面和后面吗？在这种情况下，对于'abc'，如果你挑出a，那么'bc'的排列是'bc'和'cb'。当你将'a'重新添加到列表中时，不应该将它添加到列表的前面，如'a+bc'+'a+cb'，同时也应该添加到列表的末尾，如'bc+a'+'cb+a'吗？ - BisonAVC

当你从'b'和'c'开始排列时，你会得到这些排列。（即外部'for'循环的第二次和第三次运行） - Ryan O'Neill

Answer 9

在PHP中

$set=array('A','B','C','D');

function permutate($set) {
    $b=array();
    foreach($set as $key=>$value) {
        if(count($set)==1) {
            $b[]=$set[$key];
        }
        else {
            $subset=$set;
            unset($subset[$key]);
            $x=permutate($subset);
            foreach($x as $key1=>$value1) {
                $b[]=$value.' '.$value1;
            }
        }
    }
    return $b;
}

$x=permutate($set);
var_export($x);

- nerdface

Answer 10

public class PermutationGenerator
{
    private LinkedList<List<int>> _permutationsList;
    public void FindPermutations(List<int> list, int permutationLength)
    {
        _permutationsList = new LinkedList<List<int>>();
        foreach(var value in list)
        {
            CreatePermutations(value, permutationLength);
        }
    }

    private void CreatePermutations(int value, int permutationLength)
    {
        var node = _permutationsList.First;
        var last = _permutationsList.Last;
        while (node != null)
        {
            if (node.Value.Count < permutationLength)
            {
                GeneratePermutations(node.Value, value, permutationLength);
            }
            if (node == last)
            {
                break;
            }
            node = node.Next;
        }

        List<int> permutation = new List<int>();
        permutation.Add(value);
        _permutationsList.AddLast(permutation);
    }

    private void GeneratePermutations(List<int> permutation, int value, int permutationLength)
    {
       if (permutation.Count < permutationLength)
        {
            List<int> copyOfInitialPermutation = new List<int>(permutation);
            copyOfInitialPermutation.Add(value);
            _permutationsList.AddLast(copyOfInitialPermutation);
            List<int> copyOfPermutation = new List<int>();
            copyOfPermutation.AddRange(copyOfInitialPermutation);
            int lastIndex = copyOfInitialPermutation.Count - 1;
            for (int i = lastIndex;i > 0;i--)
            {
                int temp = copyOfPermutation[i - 1];
                copyOfPermutation[i - 1] = copyOfPermutation[i];
                copyOfPermutation[i] = temp;

                List<int> perm = new List<int>();
                perm.AddRange(copyOfPermutation);
                _permutationsList.AddLast(perm);
            }
        }
    }

    public void PrintPermutations(int permutationLength)
    {
        int count = _permutationsList.Where(perm => perm.Count() == permutationLength).Count();
        Console.WriteLine("The number of permutations is " + count);
    }
}

- Bahruz Balabayov

---

这是一个有用的答案。 - Ayaz Alifov