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

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

基本上,对于从左到右的每个项目,生成剩余项目的所有排列(并且每个项目都添加有当前元素).这可以递归地进行(或者如果你喜欢疼痛则迭代地进行)直到到达最后一个项目,此时只有一个可能的顺序.

因此,使用列表[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)

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

Answer 3

对于我来说,维基百科对"词典顺序"的回答在食谱风格中显得非常明确.它引用了算法的14世纪起源!

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

这很简单.在标准的Haskell或任何现代FP语言中:

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

Answer 4

这里已经有很多好的解决方案,但我想分享一下我自己如何解决这个问题,希望这对那些想要得出自己的解决方案的人有所帮助.

在对这个问题进行一些思考后,我得出了两个以下结论:

1. 对于L大小列表,n将从列表的L ₁,L ₂ ... L _n元素开始的解决方案的数量相等.由于总体上存在n!大小列表的排列n,因此我们得到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;
            }

        }
    }
}

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

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"

现在,如果您确实需要可能用于大型列表的通用方法,我们可以使用radix方法.首先,考虑枚举问题:

$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

基数增量基本上是数字计数(在列表元素数量的基础上).

现在,如果您需要permutaion,只需在循环中添加检查:

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                                              

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

Answer 7

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

理念/伪

1. 一次挑选一个元素
2. 置换元素的其余部分,然后将拾取的元素添加到所有排列中

例如.'a'+ permute(bc).bc的变换将是bc&cb.现在加上这两个会给abc,acb.类似地,选择b + permute(ac)将provice 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中的相关)获得此代码

Answer 8

我已经用 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;
}