algorithm来生成列表的所有可能的排列？
假设我有n个元素的列表，我知道有n个元素！ 可能的方法来订购这些元素。 什么是algorithm来生成这个列表的所有可能的顺序？ 例如，我有列表[a，b，c]。 该algorithm会返回[a，b，c]，[a，c，b，]，[b，a，c]，[b，c，a]，[c，a，b]，[c，b ， 一个]]。
我正在阅读这里http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations
但维基百科从来没有擅长解释。 我不太了解。
基本上，对于从左到右的每个项目，剩余项目的所有排列被生成（并且每个项目被添加当前元素）。 这可以recursion地（或者如果你喜欢痛苦地迭代地）完成，直到最后一个项目到达，在这一点上只有一个可能的顺序。
因此，对于列表[1,2,3,4]，所有以1开始的排列都会生成，然后是以2开始，然后是3，然后是4开始的所有排列。
这有效地减less了从四个项目的列表的排列到三个项目的列表之一的问题。 减less到2，然后1个项目列表，所有这些将被发现。
显示使用3个彩色球的过程排列的示例：
（来自https://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svg – https://commons.wikimedia.org/wiki/File:Permutations_RGB.svg ）
这里是一个Python中的algorithm，它适用于一个数组：
def permute(xs, low=0): if low + 1 >= len(xs): yield xs else: for p in permute(xs, low + 1): yield p for i in range(low + 1, len(xs)): xs[low], xs[i] = xs[i], xs[low] for p in permute(xs, low + 1): yield p xs[low], xs[i] = xs[i], xs[low] for p in permute([1, 2, 3, 4]): print p 你可以在这里尝试一下自己的代码： http : //repl.it/J9v
维基百科的“词典顺序”的答案似乎完全明确在我的菜谱风格。 它引用了algorithm的14世纪起源！
我刚刚写了一个在维基百科的Javaalgorithm的快速实现作为一个检查，这是没有问题的。 但是你在Q中有什么不是“列出所有排列”，而是“所有排列列表”，因此维基百科对你来说帮助不大。 你需要一种语言，其中排列的列表是可行的。 相信我，列举几十亿通常不是通常使用命令式语言处理的。 你真的想要一个非严格的函数式编程语言，其中列表是一stream的对象，在不使机器靠近宇宙热死亡的情况下出去。
这很容易。 在标准的Haskell或任何现代FP语言中：
-- perms of a list perms :: [a] -> [ [a] ] perms (a:as) = [bs ++ a:cs | perm <- perms as, (bs,cs) <- splits perm] perms [] = [ [] ]
和
-- ways of splitting a list into two parts splits :: [a] -> [ ([a],[a]) ] splits [] = [ ([],[]) ] splits (a:as) = ([],a:as) : [(a:bs,cs) | (bs,cs) <- splits as]
这里已经有很多很好的解决scheme，但是我想分享一下我自己解决这个问题的方法，并希望这对于那些也希望得到他自己的解决scheme的人有所帮助。
经过对这个问题的思考，我得到了两个结论：
- 对于大小为
n的列表L，将有相同数量的解决scheme，以列表的L 1 ，L 2 … L n个元素开始。 因为总共有n!大小为n的列表的排列，我们得到n! / n = (n-1)!n! / n = (n-1)!在每个组中排列。 - 2个元素的列表只有2个排列=>
[a,b]和[b,a]。
使用这两个简单的想法，我推导出以下algorithm：
permute array if array is of size 2 return first and second element as new array return second and first element as new array else for each element in array new subarray = array with excluded element return element + permute subarray
这里是我如何在C＃中实现这个：
public IEnumerable<List<T>> Permutate<T>(List<T> input) { if (input.Count == 2) // this are permutations of array of size 2 { yield return new List<T>(input); yield return new List<T> {input[1], input[0]}; } else { foreach(T elem in input) // going through array { var rlist = new List<T>(input); // creating subarray = array rlist.Remove(elem); // removing element foreach(List<T> retlist in Permutate(rlist)) { retlist.Insert(0,elem); // inserting the element at pos 0 yield return retlist; } } } }
正如WhirlWind所说，你从一开始就开始。
你交换光标与剩余的每个值，包括光标本身，这些都是新的实例（我在例子中使用了int[]和array.clone() ）。
然后对所有这些不同的列表执行排列，确保光标位于右侧。
当没有剩余的值时（光标在最后），打印列表。 这是停止条件。
public void permutate(int[] list, int pointer) { if (pointer == list.length) { //stop-condition: print or process number return; } for (int i = pointer; i < list.length; i++) { int[] permutation = (int[])list.clone();. permutation[pointer] = list[i]; permutation[i] = list[pointer]; permutate(permutation, pointer + 1); } }
recursion总是需要一些精力来维护。 而对于大数，factorial容易是巨大的，堆栈溢出很容易成为一个问题。
对于小数字（3或4，大部分遇到），多个循环非常简单直接。 这是循环不幸的答案没有得到表决。
我们从枚举开始（而不是排列）。 只需将代码作为伪Perl代码读取即可。
$foreach $i1 in @list $foreach $i2 in @list $foreach $i3 in @list print "$i1, $i2, $i3\n"
枚举比排列更经常遇到，但是如果需要排列，只需添加条件：
$foreach $i1 in @list $foreach $i2 in @list $if $i2==$i1 next $foreach $i3 in @list $if $i3==$i1 or $i3==$i2 next print "$i1, $i2, $i3\n"
现在，如果你真的需要一个可能的大列表的一般方法，我们可以使用基数方法。 首先，考虑枚举问题：
$n=@list my @radix $for $i=0:$n $radix[$i]=0 $while 1 my @temp $for $i=0:$n push @temp, $list[$radix[$i]] print join(", ", @temp), "\n" $call radix_increment subcode: radix_increment $i=0 $while 1 $radix[$i]++ $if $radix[$i]==$n $radix[$i]=0 $i++ $else last $if $i>=$n last
基数增量本质上是数字计数（以列表元素数为基数）。
现在，如果你需要permutaion，只需在循环内添加检查：
subcode: check_permutation my @check my $flag_dup=0 $for $i=0:$n $check[$radix[$i]]++ $if $check[$radix[$i]]>1 $flag_dup=1 last $if $flag_dup next
编辑：上面的代码应该工作，但对于排列，radix_increment可能是浪费。 所以如果时间是一个实际问题，我们必须将radix_increment更改为permute_inc：
subcode: permute_init $for $i=0:$n $radix[$i]=$i subcode: permute_inc $max=-1 $for $i=$n:0 $if $max<$radix[$i] $max=$radix[$i] $else $for $j=$n:0 $if $radix[$j]>$radix[$i] $call swap, $radix[$i], $radix[$j] break $j=$i+1 $k=$n-1 $while $j<$k $call swap, $radix[$j], $radix[$k] $j++ $k-- break $if $i<0 break
当然现在这个代码在逻辑上更加复杂，我会去读者的练习。
如果有人想知道如何在javascript中进行排列。
理念/伪
- 每次select一个元素
- 排列元素的剩余部分，然后将拾取的元素添加到所有的排列中
例如。 'a'+ permute（bc）。 bc的排列是bc＆cb。 现在添加这两个将给abc，acb。 同样，selectb + permute（ac）将提供bac，bca …并继续。
现在看代码
function permutations(arr){ var len = arr.length, perms = [], rest, picked, restPerms, next; //for one or less item there is only one permutation if (len <= 1) return [arr]; for (var i=0; i<len; i++) { //copy original array to avoid changing it while picking elements rest = Object.create(arr); //splice removed element change array original array(copied array) //[1,2,3,4].splice(2,1) will return [3] and remaining array = [1,2,4] picked = rest.splice(i, 1); //get the permutation of the rest of the elements restPerms = permutations(rest); // Now concat like a+permute(bc) for each for (var j=0; j<restPerms.length; j++) { next = picked.concat(restPerms[j]); perms.push(next); } } return perms; }
花点时间了解这一点。 我从（ pertumation在JavaScript中 ）得到了这个代码
另一个在Python中，它不是@cdiggins的，但我认为它更容易理解
def permute(num): if len(num) == 2: # get the permutations of the last 2 numbers by swapping them yield num num[0], num[1] = num[1], num[0] yield num else: for i in range(0, len(num)): # fix the first number and get the permutations of the rest of numbers for perm in permute(num[0:i] + num[i+1:len(num)]): yield [num[i]] + perm for p in permute([1, 2, 3, 4]): print p
我正在考虑编写一个代码来获取任何给定的任意大小的整数，即提供一个数字4567，我们得到所有可能的排列，直到7654 …所以我研究了它，发现了一个algorithm，并最终实现了它，是用“c”写的代码。 您可以简单地将其复制并在任何开源编译器上运行。 但是有些缺陷正在等待被debugging。 请欣赏。
码：
#include <stdio.h> #include <conio.h> #include <malloc.h> //PROTOTYPES int fact(int); //For finding the factorial void swap(int*,int*); //Swapping 2 given numbers void sort(int*,int); //Sorting the list from the specified path int imax(int*,int,int); //Finding the value of imax int jsmall(int*,int); //Gives position of element greater than ith but smaller than rest (ahead of imax) void perm(); //All the important tasks are done in this function int n; //Global variable for input OR number of digits void main() { int c=0; printf("Enter the number : "); scanf("%d",&c); perm(c); getch(); } void perm(int c){ int *p; //Pointer for allocating separate memory to every single entered digit like arrays int i, d; int sum=0; int j, k; long f; n = 0; while(c != 0) //this one is for calculating the number of digits in the entered number { sum = (sum * 10) + (c % 10); n++; //as i told at the start of loop c = c / 10; } f = fact(n); //It gives the factorial value of any number p = (int*) malloc(n*sizeof(int)); //Dynamically allocation of array of n elements for(i=0; sum != 0 ; i++) { *(p+i) = sum % 10; //Giving values in dynamic array like 1234....n separately sum = sum / 10; } sort(p,-1); //For sorting the dynamic array "p" for(c=0 ; c<f/2 ; c++) { //Most important loop which prints 2 numbers per loop, so it goes upto 1/2 of fact(n) for(k=0 ; k<n ; k++) printf("%d",p[k]); //Loop for printing one of permutations printf("\n"); i = d = 0; i = imax(p,i,d); //provides the max i as per algo (i am restricted to this only) j = i; j = jsmall(p,j); //provides smallest i val as per algo swap(&p[i],&p[j]); for(k=0 ; k<n ; k++) printf("%d",p[k]); printf("\n"); i = d = 0; i = imax(p,i,d); j = i; j = jsmall(p,j); swap(&p[i],&p[j]); sort(p,i); } free(p); //Deallocating memory } int fact (int a) { long f=1; while(a!=0) { f = f*a; a--; } return f; } void swap(int *p1,int *p2) { int temp; temp = *p1; *p1 = *p2; *p2 = temp; return; } void sort(int*p,int t) { int i,temp,j; for(i=t+1 ; i<n-1 ; i++) { for(j=i+1 ; j<n ; j++) { if(*(p+i) > *(p+j)) { temp = *(p+i); *(p+i) = *(p+j); *(p+j) = temp; } } } } int imax(int *p, int i , int d) { while(i<n-1 && d<n-1) { if(*(p+d) < *(p+d+1)) { i = d; d++; } else d++; } return i; } int jsmall(int *p, int j) { int i,small = 32767,k = j; for (i=j+1 ; i<n ; i++) { if (p[i]<small && p[i]>p[k]) { small = p[i]; j = i; } } return j; }
void permutate(char[] x, int i, int n){ x=x.clone(); if (i==n){ System.out.print(x); System.out.print(" "); counter++;} else { for (int j=i; j<=n;j++){ // System.out.print(temp); System.out.print(" "); //Debugger swap (x,i,j); // System.out.print(temp); System.out.print(" "+"i="+i+" j="+j+"\n");// Debugger permutate(x,i+1,n); // swap (temp,i,j); } } } void swap (char[] x, int a, int b){ char temp = x[a]; x[a]=x[b]; x[b]=temp; }
我创造了这一个。 基于研究过分排列（qwe，0，qwe.length-1）; 只要你知道，你可以做或不做原路返回
这里有一个类似#permutation.to_a的玩具Ruby方法，对疯狂的人来说可能更易读。 这是海拉缓慢，但也5行。
def permute(ary) return [ary] if ary.size <= 1 ary.collect_concat.with_index do |e, i| rest = ary.dup.tap {|a| a.delete_at(i) } permute(rest).collect {|a| a.unshift(e) } end end
我已经用ANSI C编写了这个recursion解决scheme。Permutate函数的每个执行提供了一个不同的排列，直到所有的排列完成。 全局variables也可以用于variablesfact和count。
#include <stdio.h> #define SIZE 4 void Rotate(int vec[], int size) { int i, j, first; first = vec[0]; for(j = 0, i = 1; i < size; i++, j++) { vec[j] = vec[i]; } vec[j] = first; } int Permutate(int *start, int size, int *count) { static int fact; if(size > 1) { if(Permutate(start + 1, size - 1, count)) { Rotate(start, size); } fact *= size; } else { (*count)++; fact = 1; } return !(*count % fact); } void Show(int vec[], int size) { int i; printf("%d", vec[0]); for(i = 1; i < size; i++) { printf(" %d", vec[i]); } putchar('\n'); } int main() { int vec[] = { 1, 2, 3, 4, 5, 6 }; /* Only the first SIZE items will be permutated */ int count = 0; do { Show(vec, SIZE); } while(!Permutate(vec, SIZE, &count)); putchar('\n'); Show(vec, SIZE); printf("\nCount: %d\n\n", count); return 0; }
Java版本
/** * @param uniqueList * @param permutationSize * @param permutation * @param only Only show the permutation of permutationSize, * else show all permutation of less than or equal to permutationSize. */ public static void my_permutationOf(List<Integer> uniqueList, int permutationSize, List<Integer> permutation, boolean only) { if (permutation == null) { assert 0 < permutationSize && permutationSize <= uniqueList.size(); permutation = new ArrayList<>(permutationSize); if (!only) { System.out.println(Arrays.toString(permutation.toArray())); } } for (int i : uniqueList) { if (permutation.contains(i)) { continue; } permutation.add(i); if (!only) { System.out.println(Arrays.toString(permutation.toArray())); } else if (permutation.size() == permutationSize) { System.out.println(Arrays.toString(permutation.toArray())); } if (permutation.size() < permutationSize) { my_permutationOf(uniqueList, permutationSize, permutation, only); } permutation.remove(permutation.size() - 1); } }
例如
public static void main(String[] args) throws Exception { my_permutationOf(new ArrayList<Integer>() { { add(1); add(2); add(3); } }, 3, null, true); }
输出：
[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]
在PHP中
$set=array('A','B','C','D'); function permutate($set) { $b=array(); foreach($set as $key=>$value) { if(count($set)==1) { $b[]=$set[$key]; } else { $subset=$set; unset($subset[$key]); $x=permutate($subset); foreach($x as $key1=>$value1) { $b[]=$value.' '.$value1; } } } return $b; } $x=permutate($set); var_export($x);
这里是Python中的代码来打印列表的所有可能的排列：
def next_perm(arr): # Find non-increasing suffix i = len(arr) - 1 while i > 0 and arr[i - 1] >= arr[i]: i -= 1 if i <= 0: return False # Find successor to pivot j = len(arr) - 1 while arr[j] <= arr[i - 1]: j -= 1 arr[i - 1], arr[j] = arr[j], arr[i - 1] # Reverse suffix arr[i : ] = arr[len(arr) - 1 : i - 1 : -1] print arr return True def all_perm(arr): a = next_perm(arr) while a: a = next_perm(arr) arr = raw_input() arr.split(' ') arr = map(int, arr) arr.sort() print arr all_perm(arr)
我已经使用了字典顺序algorithm来获得所有可能的排列，但recursionalgorithm更有效率。 你可以在这里findrecursionalgorithm的代码： Pythonrecursion排列
在斯卡拉
def permutazione(n: List[Int]): List[List[Int]] = permutationeAcc(n, Nil) def permutationeAcc(n: List[Int], acc: List[Int]): List[List[Int]] = { var result: List[List[Int]] = Nil for (i ← n if (!(acc contains (i)))) if (acc.size == n.size-1) result = (i :: acc) :: result else result = result ::: permutationeAcc(n, i :: acc) result }
这是一个排列的java版本
public class Permutation { static void permute(String str) { permute(str.toCharArray(), 0, str.length()); } static void permute(char [] str, int low, int high) { if (low == high) { System.out.println(str); return; } for (int i=low; i<high; i++) { swap(str, i, low); permute(str, low+1, high); swap(str, low, i); } } static void swap(char [] array, int i, int j) { char t = array[i]; array[i] = array[j]; array[j] = t; } }
下面是ColdFusion的一个实现（由于ArrayAppend（）的合并参数，所以需要CF10）：
public array function permutateArray(arr){ if (not isArray(arguments.arr) ) { return ['The ARR argument passed to the permutateArray function is not of type array.']; } var len = arrayLen(arguments.arr); var perms = []; var rest = []; var restPerms = []; var rpLen = 0; var next = []; //for one or less item there is only one permutation if (len <= 1) { return arguments.arr; } for (var i=1; i <= len; i++) { // copy the original array so as not to change it and then remove the picked (current) element rest = arraySlice(arguments.arr, 1); arrayDeleteAt(rest, i); // recursively get the permutation of the rest of the elements restPerms = permutateArray(rest); rpLen = arrayLen(restPerms); // Now concat each permutation to the current (picked) array, and append the concatenated array to the end result for (var j=1; j <= rpLen; j++) { // for each array returned, we need to make a fresh copy of the picked(current) element array so as to not change the original array next = arraySlice(arguments.arr, i, 1); arrayAppend(next, restPerms[j], true); arrayAppend(perms, next); } } return perms; }
基于上面的KhanSharp的js解决scheme。
我知道这是一个非常非常老，甚至在今天的stackoverflow主题，但我仍然想贡献一个友好的JavaScript的答案，因为它在您的浏览器中运行的简单原因。
我还添加了debugger伪指令断点，所以你可以遍历代码（需要chrome）来看看这个algorithm是如何工作的。 用chrome打开你的开发控制台（Windows中的F12或者Mac上的CMD + OPTION + I ），然后点击“Run code snippet”。 这实现了@WhirlWind在他的答案中提出的相同的确切algorithm。
您的浏览器应该暂停执行debugger指令。 使用F8继续执行代码。
通过代码，看看它是如何工作的！
function permute(rest, prefix = []) { if (rest.length === 0) { return [prefix]; } return (rest .map((x, index) => { const oldRest = rest; const oldPrefix = prefix; // the `...` destructures the array into single values flattening it const newRest = [...rest.slice(0, index), ...rest.slice(index + 1)]; const newPrefix = [...prefix, x]; debugger; const result = permute(newRest, newPrefix); return result; }) // this step flattens the array of arrays returned by calling permute .reduce((flattened, arr) => [...flattened, ...arr], []) ); } console.log(permute([1, 2, 3]));
// C program to print all permutations with duplicates allowed #include <stdio.h> #include <string.h> /* Function to swap values at two pointers */ void swap(char *x, char *y) { char temp; temp = *x; *x = *y; *y = temp; } /* Function to print permutations of string This function takes three parameters: 1. String 2. Starting index of the string 3. Ending index of the string. */ void permute(char *a, int l, int r) { int i; if (l == r) printf("%s\n", a); else { for (i = l; i <= r; i++) { swap((a+l), (a+i)); permute(a, l+1, r); swap((a+l), (a+i)); //backtrack } } } /* Driver program to test above functions */ int main() { char str[] = "ABC"; int n = strlen(str); permute(str, 0, n-1); return 0; }
参考： Geeksforgeeks.org
这是产生所有permuatations的迭代解决scheme。 如果它们在数组中是重复的，则应该添加一个条件来检查列表是否已经包含生成的排列
class Program { static List<List<int>> listOfGeneratedCombinations = new List<List<int>(); static List<List<int>> listOfTempGeneratedCombinations = new List<List<int>>(); public static void GenerateAllCombination(int[] arr) { listOfGeneratedCombinations.Add(arr.ToList<int>()); for (int i=0;i<arr.Length;i++) { GenerateAllCombinations(i); } } public static void GenerateAllCombinations(int index) { foreach(var array in listOfGeneratedCombinations) { int[] arr = array.ToArray<int>(); for (int i = index; i < arr.Length - 1; i++) { int t = arr[index]; arr[index] = arr[i + 1]; arr[i + 1] = t; List<int> tempList = arr.ToList<int>(); listOfTempGeneratedCombinations.Add(tempList); t = arr[i + 1]; arr[i + 1] = arr[index]; arr[index] = t; } } listOfGeneratedCombinations.AddRange(listOfTempGeneratedCombinations); listOfTempGeneratedCombinations.Clear(); } public static void PrintGeneratedPermutation() { foreach(var list in listOfGeneratedCombinations) { foreach(var elem in list) Console.Write(elem); Console.WriteLine(); } } static void Main(string[] args) { int[] arr = new int[] {1,2,3,4}; GenerateAllCombination(arr); PrintGeneratedPermutation(); Console.ReadLine(); } }
}
在下面的Java解决scheme中，我们利用了string是不可变的事实，以避免在每次迭代时克隆结果集。
input将是一个string，说“abc”，输出将是所有可能的排列：
abc acb bac bca cba cab
码：
public static void permute(String s) { permute(s, 0); } private static void permute(String str, int left){ if(left == str.length()-1) { System.out.println(str); } else { for(int i = left; i < str.length(); i++) { String s = swap(str, left, i); permute(s, left+1); } } } private static String swap(String s, int left, int right) { if (left == right) return s; String result = s.substring(0, left); result += s.substring(right, right+1); result += s.substring(left+1, right); result += s.substring(left, left+1); result += s.substring(right+1); return result; }
同样的方法可以应用于数组（而不是string）：
public static void main(String[] args) { int[] abc = {1,2,3}; permute(abc, 0); } public static void permute(int[] arr, int index) { if (index == arr.length) { System.out.println(Arrays.toString(arr)); } else { for (int i = index; i < arr.length; i++) { int[] permutation = arr.clone(); permutation[index] = arr[i]; permutation[i] = arr[index]; permute(permutation, index + 1); } } }
这是我在Java上的解决scheme：
public class CombinatorialUtils { public static void main(String[] args) { List<String> alphabet = new ArrayList<>(); alphabet.add("1"); alphabet.add("2"); alphabet.add("3"); alphabet.add("4"); for (List<String> strings : permutations(alphabet)) { System.out.println(strings); } System.out.println("-----------"); for (List<String> strings : combinations(alphabet)) { System.out.println(strings); } } public static List<List<String>> combinations(List<String> alphabet) { List<List<String>> permutations = permutations(alphabet); List<List<String>> combinations = new ArrayList<>(permutations); for (int i = alphabet.size(); i > 0; i--) { final int n = i; combinations.addAll(permutations.stream().map(strings -> strings.subList(0, n)).distinct().collect(Collectors.toList())); } return combinations; } public static <T> List<List<T>> permutations(List<T> alphabet) { ArrayList<List<T>> permutations = new ArrayList<>(); if (alphabet.size() == 1) { permutations.add(alphabet); return permutations; } else { List<List<T>> subPerm = permutations(alphabet.subList(1, alphabet.size())); T addedElem = alphabet.get(0); for (int i = 0; i < alphabet.size(); i++) { for (List<T> permutation : subPerm) { int index = i; permutations.add(new ArrayList<T>(permutation) {{ add(index, addedElem); }}); } } } return permutations; } }
这是PHP中的recursion解决scheme。 WhirlWind的post准确地描述了逻辑。 值得一提的是，生成所有置换运行在阶乘时间，所以使用迭代方法可能是一个好主意。
public function permute($sofar, $input){ for($i=0; $i < strlen($input); $i++){ $diff = strDiff($input,$input[$i]); $next = $sofar.$input[$i]; //next contains a permutation, save it $this->permute($next, $diff); } }
strDiff函数接受两个strings1和s2 ，并返回一个新的string，其中s1所有内容都没有s2元素（重复的）。 所以， strDiff('finish','i') => 'fnish' （第二个'i' 不会被删除）。
这里是R中的algorithm，以防止任何人需要避免像我必须加载额外的库。
permutations <- function(n){ if(n==1){ return(matrix(1)) } else { sp <- permutations(n-1) p <- nrow(sp) A <- matrix(nrow=n*p,ncol=n) for(i in 1:n){ A[(i-1)*p+1:p,] <- cbind(i,sp+(sp>=i)) } return(A) } }
用法示例：
> matrix(letters[permutations(3)],ncol=3) [,1] [,2] [,3] [1,] "a" "b" "c" [2,] "a" "c" "b" [3,] "b" "a" "c" [4,] "b" "c" "a" [5,] "c" "a" "b" [6,] "c" "b" "a"
#!/usr/bin/env python import time def permutations(sequence): # print sequence unit = [1, 2, 1, 2, 1] if len(sequence) >= 4: for i in range(4, (len(sequence) + 1)): unit = ((unit + [i - 1]) * i)[:-1] # print unit for j in unit: temp = sequence[j] sequence[j] = sequence[0] sequence[0] = temp yield sequence else: print 'You can use PEN and PAPER' # s = [1,2,3,4,5,6,7,8,9,10] s = [x for x in 'PYTHON'] print s z = permutations(s) try: while True: # time.sleep(0.0001) print next(z) except StopIteration: print 'Done'
['P', 'Y', 'T', 'H', 'O', 'N'] ['Y', 'P', 'T', 'H', 'O', 'N'] ['T', 'P', 'Y', 'H', 'O', 'N'] ['P', 'T', 'Y', 'H', 'O', 'N'] ['Y', 'T', 'P', 'H', 'O', 'N'] ['T', 'Y', 'P', 'H', 'O', 'N'] ['H', 'Y', 'P', 'T', 'O', 'N'] ['Y', 'H', 'P', 'T', 'O', 'N'] ['P', 'H', 'Y', 'T', 'O', 'N'] ['H', 'P', 'Y', 'T', 'O', 'N'] ['Y', 'P', 'H', 'T', 'O', 'N'] ['P', 'Y', 'H', 'T', 'O', 'N'] ['T', 'Y', 'H', 'P', 'O', 'N'] ['Y', 'T', 'H', 'P', 'O', 'N'] ['H', 'T', 'Y', 'P', 'O', 'N'] ['T', 'H', 'Y', 'P', 'O', 'N'] ['Y', 'H', 'T', 'P', 'O', 'N'] ['H', 'Y', 'T', 'P', 'O', 'N'] ['P', 'Y', 'T', 'H', 'O', 'N'] . . . ['Y', 'T', 'N', 'H', 'O', 'P'] ['N', 'T', 'Y', 'H', 'O', 'P'] ['T', 'N', 'Y', 'H', 'O', 'P'] ['Y', 'N', 'T', 'H', 'O', 'P'] ['N', 'Y', 'T', 'H', 'O', 'P']
Bourne shell解决scheme – 总共四行（没有参数testing的情况下）：
test $# -eq 1 && echo "$1" && exit for i in $*; do $0 `echo "$*" | sed -e "s/$i//"` | sed -e "s/^/$i /" done
这是一个java的recursion代码，想法是有一个前缀，添加其余的字符：
public static void permutation(String str) { permutation("", str); } private static void permutation(String prefix, String str) { int n = str.length(); if (n == 0) System.out.println(prefix); else { for (int i = 0; i < n; i++) permutation(prefix + str.charAt(i), str); } }
例：
input=“ABC”; 输出：
ABC ACB BAC BCA CAB CBA
只是要完成，C ++
#include <iostream> #include <algorithm> #include <string> std::string theSeq = "abc"; do { std::cout << theSeq << endl; } while (std::next_permutation(theSeq.begin(), theSeq.end()));
…
abc acb bac bca cab cba
你不能真正谈论解决recursion中的一个诡异问题，而不用一个开创这个想法的（方言）语言来发布一个实现。 所以，为了完整起见，这是Scheme中可以做到的一个方法。
(define (permof wd) (cond ((null? wd) '()) ((null? (cdr wd)) (list wd)) (else (let splice ([l '()] [m (car wd)] [r (cdr wd)]) (append (map (lambda (x) (cons mx)) (permof (append lr))) (if (null? r) '() (splice (cons ml) (car r) (cdr r))))))))
调用(permof (list "foo" "bar" "baz"))我们会得到：
'(("foo" "bar" "baz") ("foo" "baz" "bar") ("bar" "foo" "baz") ("bar" "baz" "foo") ("baz" "bar" "foo") ("baz" "foo" "bar"))
我不会进入algorithm细节，因为在其他文章中已经解释得足够了。 这个想法是一样的。
但是，在Python，C和Java等破坏性媒介中，recursion问题往往难以build模和思考，而在Lisp或ML中，它可以被简洁地expression出来。
;){kind=link}
;){kind=link}