打印给定元素的排列的程序

Question

我最近参加了ACM认证的编程竞赛。这是我当时做不到的问题：

给定一个具有n个元素的整数数组，编写一个程序来打印所有排列。

请告诉我怎么做这道题。有没有解决这类问题的算法？

Answer 1

假设没有重复:只需用所有可能的后续元素更改每个元素，然后递归地调用函数。

void permute(int *array,int i,int length) { 
  if (length == i){
     printArray(array,length);
     return;
  }
  int j = i;
  for (j = i; j < length; j++) { 
     swap(array+i,array+j);
     permute(array,i+1,length);
     swap(array+i,array+j);
  }
  return;
}

您可以在ideone上看到使用基本测试用例执行辅助函数swap()和printArray()的代码

Bonus：这类似于fisher-yates shuffle的想法，但在这里-包括将i中的元素与随机选择的后面的元素交换-您可以将其与所有元素交换-每次交换一个。

Answer 2

递归方法应该做得很好：

If the list is empty
    Return the only possible permutation, an empty list.

Else
    For each element of the list
        Put the element at the first place (i.e. swap it with the first element)
          (If the element is same as the first one, don't swap)
        Recursively find all the permutations of the rest of the list

这个算法不会产生重复的排列。

下面是一个python实现：

def permute(s):
    if len(s) == 0:
        return [[]]

    ret = [s[0:1] + x for x in permute(s[1:])]

    for i in range(1, len(s)):
        if s[i] == s[0]:
            continue
        s[0], s[i] = s[i], s[0]
        ret += [s[0:1] + x for x in permute(s[1:])]

    return ret

s = [0, 1, 2, 3]
for x in permute(s):
    print x

在C中类似的事情应该是这样的：

void swap(char* str, int i, int j)
{
    char temp = str[i];
    str[i] = str[j];
    str[j] = temp;
}

void permute(char *string, int start, int end)
{
    if(start == end)
    {
        printf("%s\n", string);
        return;
    }

    permute(string, start + 1, end);
    int i;
    for(i = start + 1; i < end; i++)
    {
        if(string[start] == string[i])
            continue;
        swap(string, start, i);
        permute(string, start + 1, end);
        swap(string, start, i);
    }
}

Answer 3

这是一个迭代的解决方案：

首先对数组进行排序。

• Find maximum index I ai+1. (如果不存在这样的索引，则没有剩余的排列)

查找最大索引j

交换ai和aj。

反转ai+1..an-1并转到步骤*。