打印给定元素的排列程序
我最近参加了ACMauthentication编程竞赛。 这是我当时做不到的问题：
“给定一个具有n个元素的整数数组，写一个程序来打印所有的排列。”
请告诉我如何做这个问题。 有没有任何algorithm来做这样的问题？
假设没有重复：只需要用所有可能的后续元素来更改每个元素，并recursion地调用该函数。
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; } 你可以看到辅助函数swap()和printArray()在ideone上执行一个基本testing用例的代码
奖金 ：这与fisher-yates shuffle的想法类似，但是在这里 – 用随机select的跟随元素交换元素i – 与每个元素交换 – 每次一个。
recursion的方法应该没问题：
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 (ie 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
这个algorithm不会产生重复的排列。
这是一个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); } }
这是一个迭代的解决scheme：
首先sorting数组。
- find最大的索引ia [i + 1]。 （如果不存在这样的索引，则不存在更多的排列）
find最大的索引j
交换a [i]和[j]。
反转[i + 1] .. a [n-1]并转到步骤*。
要获得排列你必须使用回声和回溯，你也可以通过powershell解决它，但它变得复杂
void swap(int *x1,int *x2) { int x=*x1; *x1=*x2; *x2=x; } void per(int *arr,int st,int ls) { int i=0; if(st==ls) { int k; for(k=0;k<ls;k++) { printf("%d ",arr[k]); } printf("\n"); } else { for(i=st;i<ls;i++) { swap(arr+st,arr+i); per(arr,st+1,ls); swap(arr+st,arr+i); } } } int main() { int arr[4]={1,2,3,1}; int st=0; int ls=4; per(arr,st,ls); }
