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

Question

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

我在这里读这个 但是

维基百科从来不擅长解释。我不太明白其中的很多内容。

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

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

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

1. 对于大小为 n 的列表 L ，将有相同数量的以 L 1 开头的解决方案, 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 4

对我来说，维基百科对“词典顺序”的回答在食谱风格中似乎非常明确。它引用了该算法的 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 5

正如旋风所说，你从头开始。

您将游标与每个剩余值交换，包括游标本身，这些都是新实例（我在示例中使用了 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"

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

$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                                              

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

Answer 7

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

想法/伪代码

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

。 'a'+ 排列(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 中的排列) 获得了这段代码

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

Answer 9

另一种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

Answer 10

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

代码：

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

Answer 11

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

我创造了这个。也基于研究
排列(qwe, 0, qwe.length-1);
只是想让你知道，无论有没有回溯，你都可以做到这一点

Answer 12

这是一个玩具 Ruby 方法，其工作方式类似于 #permutation.to_a，对于疯狂的人来说可能更容易理解。虽然很慢，但也需要 5 行。

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

Answer 13

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]

Answer 14

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

Answer 15

这是一个用于排列的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;
    }
}

Answer 16

下面是用 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 递归排列

Answer 17

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

Answer 18

在斯卡拉中

    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
}

Answer 19

这是 ColdFusion 的实现（需要 CF10，因为 ArrayAppend() 的合并参数）：

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

基于上面 KhanSharp 的 js 解决方案。

Answer 20

我知道这是一个非常非常古老的问题，甚至在今天的 stackoverflow 中已经离题了，但我仍然想贡献一个友好的 javascript 答案，原因很简单，它在您的浏览器中运行。

我还添加了 debugger 指令断点，以便您可以单步执行代码（需要 chrome）来查看该算法的工作原理。在 Chrome 中打开开发控制台（Windows 中为 F12 或 Mac 上为 CMD + OPTION + I），然后单击“运行代码片段”。这实现了 @WhirlWind 在他的答案中提出的完全相同的算法。

您的浏览器应在 debugger 指令处暂停执行。使用F8 继续执行代码。

单步执行代码，看看它是如何工作的！

function permute(rest, prefix = []) {
  if (rest.length === 0) {
    return [prefix];
  }
  return (rest
    .map((x, index) => {
      const oldRest = rest;
      const oldPrefix = prefix;
      // the `...` destructures the array into single values flattening it
      const newRest = [...rest.slice(0, index), ...rest.slice(index + 1)];
      const newPrefix = [...prefix, x];
      debugger;

      const result = permute(newRest, newPrefix);
      return result;
    })
    // this step flattens the array of arrays returned by calling permute
    .reduce((flattened, arr) => [...flattened, ...arr], [])
  );
}
console.log(permute([1, 2, 3]));

Answer 21

在下面的 Java 解决方案中，我们利用字符串不可变这一事实，以避免在每次迭代时克隆结果集。

输入将是一个字符串，例如“abc”，输出将是所有可能的排列：

abc
acb
bac
bca
cba
cab

代码：

public static void permute(String s) {
    permute(s, 0);
}

private static void permute(String str, int left){
    if(left == str.length()-1) {
        System.out.println(str);
    } else {
        for(int i = left; i < str.length(); i++) {
            String s = swap(str, left, i);
            permute(s, left+1);
        }
    }
}

private static String swap(String s, int left, int right) {
    if (left == right)
        return s;

    String result = s.substring(0, left);
    result += s.substring(right, right+1);
    result += s.substring(left+1, right);
    result += s.substring(left, left+1);
    result += s.substring(right+1);
    return result;
}

相同的方法可以应用于数组（而不是字符串）：

public static void main(String[] args) {
    int[] abc = {1,2,3};
    permute(abc, 0);
}
public static void permute(int[] arr, int index) {
    if (index == arr.length) {
        System.out.println(Arrays.toString(arr));
    } else {
        for (int i = index; i < arr.length; i++) {
            int[] permutation = arr.clone();
            permutation[index] = arr[i];
            permutation[i] = arr[index];
            permute(permutation, index + 1);
        }
    }
}

Answer 22

这是我在Java上的解决方案：

public class CombinatorialUtils {

    public static void main(String[] args) {
        List<String> alphabet = new ArrayList<>();
        alphabet.add("1");
        alphabet.add("2");
        alphabet.add("3");
        alphabet.add("4");

        for (List<String> strings : permutations(alphabet)) {
            System.out.println(strings);
        }
        System.out.println("-----------");
        for (List<String> strings : combinations(alphabet)) {
            System.out.println(strings);
        }
    }

    public static List<List<String>> combinations(List<String> alphabet) {
        List<List<String>> permutations = permutations(alphabet);
        List<List<String>> combinations = new ArrayList<>(permutations);

        for (int i = alphabet.size(); i > 0; i--) {
            final int n = i;
            combinations.addAll(permutations.stream().map(strings -> strings.subList(0, n)).distinct().collect(Collectors.toList()));
        }
        return combinations;
    }

    public static <T> List<List<T>> permutations(List<T> alphabet) {
        ArrayList<List<T>> permutations = new ArrayList<>();
        if (alphabet.size() == 1) {
            permutations.add(alphabet);
            return permutations;
        } else {
            List<List<T>> subPerm = permutations(alphabet.subList(1, alphabet.size()));
            T addedElem = alphabet.get(0);
            for (int i = 0; i < alphabet.size(); i++) {
                for (List<T> permutation : subPerm) {
                    int index = i;
                    permutations.add(new ArrayList<T>(permutation) {{
                        add(index, addedElem);
                    }});
                }
            }
        }
        return permutations;
    }
}

Answer 23

如果不以 开创了这个想法。因此，为了完整起见，以下是在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"))

我不会深入讨论算法细节，因为它在其他帖子中已经得到了足够的解释。这个想法是一样的。

然而，递归问题在 Python、C 和 Java 等破坏性介质中往往更难建模和思考，而在 Lisp 或 ML 中则可以简洁地表达。

Answer 24

当我在工程的第一年时，我想出了这些算法（一个是递归的，另一个是迭代的），并用 python 实现了它们（我为随机命名方案表示歉意）：

def permute(x):
    m = [ord(i) for i in x]
    m.sort()
    count = 1
    print(count,''.join([chr(i) for i in m]))
    while (True):
        l = -1
        lgth = len(m)
        while (m[l] <= m[l-1]):
            l -= 1
            if l == -lgth:
                break
        if l == -lgth:
            break
        z = sorted(m[l-1:])
        k = m[l-1]
        z2 = z[:]
        z.reverse()
        b = z[z.index(k)-1]
        z2.remove(b)
        v = [b] + z2
        m[l-1:] = v
        count += 1
        print(count, ''.join([chr(i) for i in m]))

"""A Less-powerful solution: """

def permute_recursively(inp_list):
    if (len(inp_list) == 1):
        return [inp_list]
    else:
        x = permute_recursively(inp_list[1:])
        a = inp_list[0]
        z = []
        for i in x:
            for k in range(len(i) + 1):
                z.append(i[:k] + [a] + i[k:])
        return(z)

""" main section """

x = input("Enter the string: ")

#call to permute
permute(x)
print("****** End of permute ******\n")

#call to permute_recursively
count = 1
for i in permute_recursively(sorted(list(x))):
    print(count, ''.join(i))
    count += 1

第一个算法的特点：

• 更高效。
• 可用于任何长度的输入（如果你有足够的时间
  和计算资源）。
• 根据字典顺序生成排列
  ASCII 值。的字符。
• 几乎不使用任何内存
• 跳过生成任何重复项。
• 准确生成 https://i.sstatic.net/NZ2vt.jpg 排列，
  其中 n 是输入中的字符数，i 是索引
  任何重复的字符，m 是重复的次数
  索引为 i 的字符。

第二种算法是递归的：

• 效率较低。
• 不能用于长度超过特定限制的输入，因为
  允许的递归深度是有限的。
• 不按字典顺序生成排列。
• 使用大量内存，因为它需要存储它生成的每个排列
• 生成重复项。
• 恰好生成 n!输出

Answer 25

这是 PHP 中的递归解决方案。 WhirlWind 的帖子准确地描述了这个逻辑。值得一提的是，生成所有排列都是在阶乘时间内运行的，因此使用迭代方法可能是一个好主意。

public function permute($sofar, $input){
  for($i=0; $i < strlen($input); $i++){
    $diff = strDiff($input,$input[$i]);
    $next = $sofar.$input[$i]; //next contains a permutation, save it
    $this->permute($next, $diff);
  }
}

strDiff 函数接受两个字符串 s1 和 s2，并返回一个新字符串，其中包含 s1 中的所有内容，但不含 s2 中的元素代码>（重复内容）。所以，strDiff('finish','i') => 'fnish'（第二个“i”未被删除）。

Answer 26

这是 R 中的一个算法，以防有人需要像我一样避免加载额外的库。

permutations <- function(n){
    if(n==1){
        return(matrix(1))
    } else {
        sp <- permutations(n-1)
        p <- nrow(sp)
        A <- matrix(nrow=n*p,ncol=n)
        for(i in 1:n){
            A[(i-1)*p+1:p,] <- cbind(i,sp+(sp>=i))
        }
        return(A)
    }
}

用法示例：

> matrix(letters[permutations(3)],ncol=3)
     [,1] [,2] [,3]
[1,] "a"  "b"  "c" 
[2,] "a"  "c"  "b" 
[3,] "b"  "a"  "c" 
[4,] "b"  "c"  "a" 
[5,] "c"  "a"  "b" 
[6,] "c"  "b"  "a" 

Answer 27

#!/usr/bin/env python
import time

def permutations(sequence):
  # print sequence
  unit = [1, 2, 1, 2, 1]

  if len(sequence) >= 4:
    for i in range(4, (len(sequence) + 1)):
      unit = ((unit + [i - 1]) * i)[:-1]
      # print unit
    for j in unit:
      temp = sequence[j]
      sequence[j] = sequence[0]
      sequence[0] = temp
      yield sequence
  else:
    print 'You can use PEN and PAPER'


# s = [1,2,3,4,5,6,7,8,9,10]
s = [x for x in 'PYTHON']

print s

z = permutations(s)
try:
  while True:
    # time.sleep(0.0001)
    print next(z)
except StopIteration:
    print 'Done'

---

['P', 'Y', 'T', 'H', 'O', 'N']
['Y', 'P', 'T', 'H', 'O', 'N']
['T', 'P', 'Y', 'H', 'O', 'N']
['P', 'T', 'Y', 'H', 'O', 'N']
['Y', 'T', 'P', 'H', 'O', 'N']
['T', 'Y', 'P', 'H', 'O', 'N']
['H', 'Y', 'P', 'T', 'O', 'N']
['Y', 'H', 'P', 'T', 'O', 'N']
['P', 'H', 'Y', 'T', 'O', 'N']
['H', 'P', 'Y', 'T', 'O', 'N']
['Y', 'P', 'H', 'T', 'O', 'N']
['P', 'Y', 'H', 'T', 'O', 'N']
['T', 'Y', 'H', 'P', 'O', 'N']
['Y', 'T', 'H', 'P', 'O', 'N']
['H', 'T', 'Y', 'P', 'O', 'N']
['T', 'H', 'Y', 'P', 'O', 'N']
['Y', 'H', 'T', 'P', 'O', 'N']
['H', 'Y', 'T', 'P', 'O', 'N']
['P', 'Y', 'T', 'H', 'O', 'N']
.
.
.
['Y', 'T', 'N', 'H', 'O', 'P']
['N', 'T', 'Y', 'H', 'O', 'P']
['T', 'N', 'Y', 'H', 'O', 'P']
['Y', 'N', 'T', 'H', 'O', 'P']
['N', 'Y', 'T', 'H', 'O', 'P']

Answer 28

为了完整起见，C++

#include <iostream>
#include <algorithm>
#include <string>

std::string theSeq = "abc";
do
{
  std::cout << theSeq << endl;
} 
while (std::next_permutation(theSeq.begin(), theSeq.end()));

...

abc
acb
bac
bca
cab
cba

Answer 29

这是 C++ 中的非递归解决方案，它按升序提供下一个排列，类似于 std::next_permutation 提供的功能：

void permute_next(vector<int>& v)
{
  if (v.size() < 2)
    return;

  if (v.size() == 2)
  { 
    int tmp = v[0];
    v[0] = v[1];
    v[1] = tmp;
    return;
  }

  // Step 1: find first ascending-ordered pair from right to left
  int i = v.size()-2;
  while(i>=0)
  { 
    if (v[i] < v[i+1])
      break;
    i--;
  }
  if (i<0) // vector fully sorted in descending order (last permutation)
  {
    //resort in ascending order and return
    sort(v.begin(), v.end());
    return;
  }

  // Step 2: swap v[i] with next higher element of remaining elements
  int pos = i+1;
  int val = v[pos];
  for(int k=i+2; k<v.size(); k++)
    if(v[k] < val && v[k] > v[i])
    {
      pos = k;
      val = v[k];
    }
  v[pos] = v[i];
  v[i] = val;

  // Step 3: sort remaining elements from i+1 ... end
  sort(v.begin()+i+1, v.end());
}

Answer 30

在 C 中，创建单个矩阵（无符号字符）来快速轻松地访问从 1 到 6 的所有排列。基于 https://www.geeksforgeeks.org/heaps-algorithm 的代码-用于生成排列/。

void swap(unsigned char* a, unsigned char* b)
{
    unsigned char t;

    t = *b;
    *b = *a;
    *a = t;
}

void print_permutations(unsigned char a[], unsigned char n)
{
    // can't rely on sizeof(a[6]) == 6, such as with MSVC 2019
    for (int i = 0; i < n; i++)
    {
        assert(a[i] < n);
        printf("%d ", a[i]);
    }
    printf("\n");
}

// Generating permutation using Heap Algorithm 
void generate_permutations(unsigned char (**permutations)[6], unsigned char a[], int size, int n)
{
    // can't rely on sizeof(a[6]) == 6, such as with MSVC 2019
    // if size becomes 1 then prints the obtained permutation 
    if (size == 1)
    {
        memcpy(*permutations, a, n);
        *permutations += 1;
    }
    else
    {
        for (int i = 0; i < size; i++)
        {
            generate_permutations(permutations, a, size - 1, n);

            // if size is odd, swap first and last element
            if (size & 1)
                swap(a, a + size - 1);

            // If size is even, swap ith and last element
            else
                swap(a + i, a + size - 1);
        }
    }
}

int main()
{
    unsigned char permutations[720][6]; // easily access all permutations from 1 to 6
    unsigned char suit_length_indexes[] = { 0, 1, 2, 3, 4, 5 };
    assert(sizeof(suit_length_indexes) == sizeof(permutations[0]));
    unsigned char(*p)[sizeof(suit_length_indexes)] = permutations;
    generate_permutations(&p, suit_length_indexes, sizeof(suit_length_indexes), sizeof(suit_length_indexes));
    for (int i = 0; i < sizeof(permutations) / sizeof(permutations[0]); i++)
        print_permutations(permutations[i], sizeof(suit_length_indexes));
    return 0;
}