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

[itfanr]

数组为：1 2 3 4 5 6

语言不限

感觉好难啊！

[xoyo]

用DFS就可以了~

[llbgurs]

http://docs.python.org/2/library/itertools.html#itertools.permutations

[itfanr]

@llbgurs 果然厉害

[itfanr]

@xoyo ?啥东东

[skyahead]

昨天刚好写了一个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)

[txx]

https://gist.github.com/rpplusplus/6606861

随手写了个 c 的 居然没debug 就过了.....

[momou]

前天刚学习过的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]);

[kid177]

#include <algorithm>

next_permutation

[xoyo]

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

[leunggamciu]

刚学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]

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

[amyangfei]

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

[ctrlaltdeletel]

https://gist.github.com/cadl/6609683

[dreamersdw]

https://gist.github.com/dreamersdw/6609989

[Karsa]

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

[laskuma]

@xoyo 略想吐槽。。

[fantasticfears]

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

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

[wang2191195]

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

[kotokz]

echo "123456" | ruby -ne '$_.chomp.chars.to_a.permutation{|x| puts x.join “ ”}'

[xlhuang]

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