程序打印给定元素的排列

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()执行基本测试用例

奖励:这类似于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);
    }
}