1
xoyo 2013-09-18 16:52:36 +08:00
用DFS就可以了~
|
2
llbgurs 2013-09-18 16:56:11 +08:00 2
|
5
skyahead 2013-09-18 17:38:19 +08:00
昨天刚好写了一个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) |
6
txx 2013-09-18 17:41:54 +08:00
|
7
momou 2013-09-18 17:55:48 +08:00
前天刚学习过的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<sub>"+ ++count+"</sub>: "+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]); |
8
kid177 2013-09-18 18:46:48 +08:00
#include <algorithm>
next_permutation |
10
leunggamciu 2013-09-18 20:52:37 +08:00
刚学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); |
11
leunggamciu 2013-09-18 20:54:08 +08:00
@leunggamciu 请原谅我单词拼错了!
|
12
amyangfei 2013-09-18 21:28:01 +08:00
for i in itertools.permutations('123456', len('123456')):
print ''.join(i) |
13
ctrlaltdeletel 2013-09-18 22:15:28 +08:00
|
14
dreamersdw 2013-09-18 22:28:04 +08:00 1
|
15
Karsa 2013-09-18 23:13:34 +08:00
<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> |
17
fantasticfears 2013-09-18 23:42:12 +08:00
|
18
wang2191195 2013-09-19 00:36:17 +08:00
@fantasticfears 高端洋气c++11
其实现在非常喜欢来数组了。。。int a[] = {1,2,3,4,5,6}; |
19
kotokz 2013-09-20 00:52:53 +08:00
echo "123456" | ruby -ne '$_.chomp.chars.to_a.permutation{|x| puts x.join “ ”}'
|
20
xlhuang 2013-09-20 02:17:51 +08:00
<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> |
21
xlhuang 2013-09-20 02:56:28 +08:00
|
22
tioover 2013-09-20 22:30:42 +08:00
|
23
yukirock 2013-09-21 02:16:36 +08:00
《组合数学》中提到过一种全排列升成算法。
给定一个整数 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} 的全排列。 |
24
tioover 2013-09-21 02:23:05 +08:00
|
25
coldear 2013-09-21 06:03:31 +08:00
|
26
kedebug 2013-09-21 11:47:10 +08:00
建议楼主平时多积累些基础的算法知识,像全排列这样经典的递归算法应该信手拈来才是。
|