如何输出一个数组的全排列？

用DFS就可以了~

@llbgurs 果然厉害

@xoyo ?啥东东

昨天刚好写了一个python，不过输入是字符串！

def get_permutations(s):
result = []

assert len(s) is not 0 # sanity check

if len(s) == 1:
result.append(s)
else: # len >= 2
for i in range(len(s)):
curr = s[i]

# rest of the string
if i == 0: # first in the string
rest = s[1 : ]
elif i == len(s) - 1: # last in the string
rest = s[ : i ]
else: # those in the middle
rest = s[0 : i] + s[i + 1 : ]

for a in get_permutations(rest): # get all the premutations of [s - curr]
result.append(curr + a)

return result

if __name__ == "__main__":
s = '1234'
print get_permutations(s)

前天刚学习过的JS:
/*
全排列（递归交换）算法
1、将第一个位置分别放置各个不同的元素；
2、对剩余的位置进行全排列（递归）；
3、递归出口为只对一个元素进行全排列。
*/
function swap(arr,i,j) {
if(i!=j) {
var temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
var count=0;
function show(arr) {
document.write("P_{"+ ++count+"}: "+arr+"<br />");
}
function perm(arr) {
(function fn(n) { //为第n个位置选择元素
for(var i=n;i<arr.length;i++) {
swap(arr,i,n);
if(n+1<arr.length-1) //判断数组中剩余的待全排列的元素是否大于1个
fn(n+1); //从第n+1个下标进行全排列
else
show(arr); //显示一组结果
swap(arr,i,n);
}
})(0);
}
permutations([1,2,3,4,5,6]);

#include <algorithm>

next_permutation

@itfanr Depth first search 深度优先搜索。比如@txx的代码就是。

刚学C的时候写的，用递归比较好理解，可以[先固定第一个字符，对余下的字符作全排列]，因为一个字符的全排列就是它本身，所以这里就构成了一个递归

void prem(char *list,int i,int n)
{
int j;
if(i==n)
{
for(j=0;j<=n;j++)
printf("%c",list[j]);
printf(" ");
}
else
{
for(j=i;j<=n;j++)
{
SWAP(&list[i],&list[j]);
prem(list,i+1,n);//处理子序列
SWAP(&list[i],&list[j]);
}
}
return;
}

char list[] = "1234";
prem(list,0,3);

@leunggamciu 请原谅我单词拼错了！

for i in itertools.permutations('123456', len('123456')):
print ''.join(i)

<code>
def pickOne (array1, array2) :
length = len (array2)
if length == 0 :
return
for i in range (0, length) :
tempArray1 = array1[:]
tempArray2 = array2[:]
moveArrayItem (tempArray1, tempArray2, i)
print (tempArray1)
pickOne (tempArray1, tempArray2)

def moveArrayItem (array1, array2, index) :
if index < len(array2) :
array1.append (array2.pop(index))

array = [1,2,3,4,5,6]
tempArray = []
pickOne (tempArray, array)

</code>

@xoyo 略想吐槽。。

https://gist.github.com/fantasticfears/6611085

next_permutation实现详细解释：http://stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation#answers

@fantasticfears 高端洋气c++11
其实现在非常喜欢来数组了。。。int a[] = {1,2,3,4,5,6};

<code>
<pre>
var result = [];
function permutation1(arr) {
perm1(arr, 0);
}
function perm1(arr, index) {
var n = arr.length;
if (index === n - 1) {
result.push(arr.slice());
return false;
} else {
for (j = index; j < n; ++j) {
swap(arr, j, index);
arguments.callee(arr, j + 1);
swap(arr, j, index);
}
}
}
function swap(arr, index1, index2) {
var temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
</pre>
</code>

http://gist.github.com/tioover/6638449

其实应该用Scheme 来写。

《组合数学》中提到过一种全排列升成算法。

给定一个整数 k，在其上方标记一个左箭头或右箭头以示方向，如：

< >
k 或 k

对于 {1..k} 的一个排列，对于其中每一个数都给定一个方向。如果一个整数 k 的箭头指向一个与其相邻但是比它小的整数，那么 k 即为「活动的」。例如对于

>>><>>
263154

356 是活动的。

可以得出如下结论：

* 1 一定不是活动的，因为 1 是最小的整数。
* 除了以下两种情况，{1..n} 中最大的整数 n 总是活动的：n 在最左边且它的箭头朝左，或 n 在最右边且它的箭头朝右。

算法如下。

从

<<..<
12..n

开始。

当存在一个活动的整数时，执行：

1. 求出最大的活动整数 m
2. 交换 m 及其箭头所指的与其相邻的整数
3. 交换所有满足 p>m 的整数 p 的方向。

以 n=4 为例：

<<<<
1234

<<<<
1243

<<<<
1423

<<<<
4123

><<<
4132

<><<
1432

<<><
1342

<<<>
1324

<<<<
3124

<<<<
3142

（略）

<<>>
2134

到 2134 中没有活动整数，算法终止。此时已经打出 {1234} 的全排列。

我之前发的怎么没有了？

http://gist.github.com/tioover/6638449

http://ericlippert.com/2013/04/15/producing-permutations-part-one/
一个系列的博客详细讲解全排列

建议楼主平时多积累些基础的算法知识，像全排列这样经典的递归算法应该信手拈来才是。

@kedebug 笔试考了 拈不来