Algoritmo para generar todas las permutaciones posibles de una lista?

Digamos que tengo una lista de n elementos, ¡sé que hay n! posibles formas de ordenar estos elementos. ¿Qué es un algoritmo para generar todos los ordenamientos posibles de esta lista? Ejemplo, tengo la lista [a, b, c]. El algoritmo devolvería [[a, b, c], [a, c, b,], [b, a, c], [b, c, a], [c, a, b], [c, b , un]].

Estoy leyendo esto aquí http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

Pero Wikipedia nunca ha sido buena para explicar. No entiendo mucho de eso.

Básicamente, para cada elemento de izquierda a derecha, se generan todas las permutaciones de los elementos restantes (y cada uno se agrega con los elementos actuales). Esto se puede hacer recursivamente (o iterativamente si le gusta el dolor) hasta que se scope el último elemento, en cuyo punto solo hay un orden posible.

Entonces con la lista [1,2,3,4] se generan todas las permutaciones que comienzan con 1, luego todas las permutaciones que comienzan con 2, luego 3 y luego 4.

Esto efectivamente reduce el problema de encontrar permutaciones de una lista de cuatro elementos a una lista de tres elementos. Después de reducir a 2 y luego a 1 lista de artículos, se encontrarán todos.
Ejemplo que muestra las permutaciones del proceso usando 3 bolas de colores:
Las bolas de color rojo, verde y azul pidieron imagen de permutaciones (de https://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svghttps://commons.wikimedia.org/wiki/File:Permutations_RGB.svg )

Aquí hay un algoritmo en Python que funciona en su lugar en una matriz:

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 

Puede probar el código aquí: http://repl.it/J9v

La respuesta de Wikipedia para el “orden lexicográfico” me parece perfectamente explícita en el estilo del libro de cocina. ¡Cita un origen del siglo 14 para el algoritmo!

Acabo de escribir una implementación rápida en Java del algoritmo de Wikipedia como un control y no fue un problema. Pero lo que tienes en tu Q como ejemplo NO es “enumera todas las permutaciones”, sino “una LISTA de todas las permutaciones”, por lo que wikipedia no será de mucha ayuda para ti. Necesita un lenguaje en el que se puedan construir listas de permutaciones. Y créanme, las listas de unos miles de millones de largo no suelen manejarse en idiomas imperativos. Realmente desea un lenguaje de progtwigción funcional no estricto, en el que las listas sean un objeto de primera clase, para sacar cosas sin acercar la máquina a la muerte por calor del Universo.

Eso es fácil. En Haskell estándar o en cualquier lenguaje FP moderno:

 -- perms of a list perms :: [a] -> [ [a] ] perms (a:as) = [bs ++ a:cs | perm < - perms as, (bs,cs) <- splits perm] perms [] = [ [] ] 

y

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

Aquí ya hay muchas buenas soluciones, pero me gustaría compartir cómo resolví este problema yo solo y espero que esto pueda ser útil para alguien a quien también le gustaría obtener su propia solución.

Después de reflexionar sobre el problema, he llegado a dos conclusiones:

  1. Para la lista L del tamaño n , habrá la misma cantidad de soluciones comenzando con L 1 , L 2 … L n elementos de la lista. Como en total hay n! permutaciones de la lista de tamaño n , obtenemos n! / n = (n-1)! n! / n = (n-1)! permutaciones en cada grupo.
  2. La lista de 2 elementos tiene solo 2 permutaciones => [a,b] y [b,a] .

Usando estas dos ideas simples, he derivado el siguiente algoritmo:

 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 

Aquí es cómo lo implementé en C #:

 public IEnumerable> Permutate(List input) { if (input.Count == 2) // this are permutations of array of size 2 { yield return new List(input); yield return new List {input[1], input[0]}; } else { foreach(T elem in input) // going through array { var rlist = new List(input); // creating subarray = array rlist.Remove(elem); // removing element foreach(List retlist in Permutate(rlist)) { retlist.Insert(0,elem); // inserting the element at pos 0 yield return retlist; } } } } 

Como dijo WhirlWind, comienzas por el principio.

Cambia el cursor con cada valor restante, incluido el cursor en sí, estas son todas las instancias nuevas (utilicé un int[] y array.clone() en el ejemplo).

Luego realice permutaciones en todas estas listas diferentes, asegurándose de que el cursor esté uno a la derecha.

Cuando ya no quedan más valores (el cursor está al final), imprima la lista. Esta es la condición de parada.

 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); } } 

Recursivo siempre requiere un esfuerzo mental para mantenerse. Y para números grandes, factorial es muy grande y el desbordamiento de la stack fácilmente será un problema.

Para números pequeños (3 o 4, que se encuentran principalmente), los bucles múltiples son bastante simples y directos. Es lamentable que las respuestas con bucles no hayan sido votadas.

Comencemos con la enumeración (en lugar de la permutación). Simplemente lea el código como código de pseudoperl.

 $foreach $i1 in @list $foreach $i2 in @list $foreach $i3 in @list print "$i1, $i2, $i3\n" 

La enumeración se encuentra con más frecuencia que la permutación, pero si se necesita permutación, simplemente agregue las condiciones:

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

Ahora, si realmente necesita un método general para listas grandes, podemos usar el método radix. Primero, considere el problema de enumeració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 

El incremento de Radix consiste esencialmente en contar números (en la base del número de elementos de la lista).

Ahora si necesita permutaion, simplemente agregue las verificaciones dentro del ciclo:

 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 

Editar: El código anterior debería funcionar, pero para la permutación, radix_increment podría ser un desperdicio. Entonces, si el tiempo es una preocupación práctica, tenemos que cambiar radix_increment en 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 

Por supuesto, ahora que este código es lógicamente más complejo, me iré para el ejercicio del lector.

Si alguien se pregunta cómo hacerlo en permutación en javascript.

Idea / pseudocódigo

  1. elige un elemento a la vez
  2. permute el rest del elemento y luego agregue el elemento elegido a la totalidad de la permutación

por ejemplo. ‘a’ + permute (bc). permute de bc sería bc & cb. Ahora agrega que estos dos darán abc, acb. de manera similar, elegir b + permute (ac) proporcionará bac, bca … y continuará.

ahora mira el código

 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 

Tómate tu tiempo para entender esto. Obtuve este código de ( preocupación en JavaScript )

Otro en Python, no está en su lugar como @cdiggins, pero creo que es más fácil de entender

 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 

Estaba pensando en escribir un código para obtener las permutaciones de cualquier entero dado de cualquier tamaño, es decir, proporcionando un número 4567 obtenemos todas las permutaciones posibles hasta 7654 … Así que trabajé en él y encontré un algoritmo y finalmente lo implementé, Aquí es el código escrito en “c”. Simplemente puede copiarlo y ejecutarlo en cualquier comstackdor de código abierto. Pero algunos defectos están esperando para ser eliminados. Por favor aprecio

Código:

 #include  #include  #include  //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 *(p+j)) { temp = *(p+i); *(p+i) = *(p+j); *(p+j) = temp; } } } } int imax(int *p, int i , int d) { while(ip[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; } 

Creé este. basado en la investigación también permutada (qwe, 0, qwe.length-1); Para que lo sepas, puedes hacerlo con o sin retroceder

Aquí hay un método Ruby de juguete que funciona como #permutation.to_a que podría ser más legible para los locos. Es hella lenta, pero también 5 líneas.

 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 

He escrito esta solución recursiva en ANSI C. Cada ejecución de la función Permutate proporciona una permutación diferente hasta que se completen todas. Las variables globales también se pueden usar para variables de hecho y recuento.

 #include  #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; } 

Versión de 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 uniqueList, int permutationSize, List 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); } } 

P.ej

 public static void main(String[] args) throws Exception { my_permutationOf(new ArrayList() { { add(1); add(2); add(3); } }, 3, null, true); } 

salida:

  [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1] 

en 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); 

enter image description here

 // C program to print all permutations with duplicates allowed #include  #include  /* 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; } 

Referencia: Geeksforgeeks.org

Aquí está el código en Python para imprimir todas las permutaciones posibles de una lista:

 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) 

He usado un algoritmo de orden lexicográfico para obtener todas las permutaciones posibles, pero un algoritmo recursivo es más eficiente. Puede encontrar el código para el algoritmo recursivo aquí: permutaciones de recursión de Python

 public class PermutationGenerator { private LinkedList> _permutationsList; public void FindPermutations(List list, int permutationLength) { _permutationsList = new LinkedList>(); foreach(var value in list) { CreatePermutations(value, permutationLength); } } private void CreatePermutations(int value, int permutationLength) { var node = _permutationsList.First; var last = _permutationsList.Last; while (node != null) { if (node.Value.Count < permutationLength) { GeneratePermutations(node.Value, value, permutationLength); } if (node == last) { break; } node = node.Next; } List permutation = new List(); permutation.Add(value); _permutationsList.AddLast(permutation); } private void GeneratePermutations(List permutation, int value, int permutationLength) { if (permutation.Count < permutationLength) { List copyOfInitialPermutation = new List(permutation); copyOfInitialPermutation.Add(value); _permutationsList.AddLast(copyOfInitialPermutation); List copyOfPermutation = new List(); copyOfPermutation.AddRange(copyOfInitialPermutation); int lastIndex = copyOfInitialPermutation.Count - 1; for (int i = lastIndex;i > 0;i--) { int temp = copyOfPermutation[i - 1]; copyOfPermutation[i - 1] = copyOfPermutation[i]; copyOfPermutation[i] = temp; List perm = new List(); perm.AddRange(copyOfPermutation); _permutationsList.AddLast(perm); } } } public void PrintPermutations(int permutationLength) { int count = _permutationsList.Where(perm => perm.Count() == permutationLength).Count(); Console.WriteLine("The number of permutations is " + count); } } 

En Scala

  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 } 

esta es una versión java para permutación

 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 

Aquí hay una implementación para ColdFusion (requiere CF10 debido al argumento de combinación para ArrayAppend ()):

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

Basado en la solución js de KhanSharp anterior.

Sé que es un tema muy antiguo e incluso fuera de lugar en el stackoverflow de hoy, pero aún así quería contribuir con una respuesta de javascript amigable por la sencilla razón de que se ejecuta en su navegador.

También agregué el punto de corte de la directiva de debugger para que pueda recorrer el código (se requiere Chrome) para ver cómo funciona este algoritmo. Abra su consola de desarrollo en Chrome ( F12 en Windows o CMD + OPTION + I en Mac) y luego haga clic en “Ejecutar fragmento de código”. Esto implementa el mismo algoritmo exacto que @WhirlWind presentó en su respuesta.

Su navegador debe detener la ejecución en la directiva de debugger . Use F8 para continuar la ejecución del código.

¡Pase el código y vea cómo funciona!

 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])); 

En la siguiente solución Java, aprovechamos el hecho de que las cadenas son inmutables para evitar clonar el conjunto de resultados en cada iteración.

La entrada será una Cadena, diga “abc”, y la salida serán todas las permutaciones posibles:

 abc acb bac bca cba cab 

Código:

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

El mismo enfoque se puede aplicar a las matrices (en lugar de una cadena):

 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); } } } 

Es mi solución en Java:

 public class CombinatorialUtils { public static void main(String[] args) { List alphabet = new ArrayList<>(); alphabet.add("1"); alphabet.add("2"); alphabet.add("3"); alphabet.add("4"); for (List strings : permutations(alphabet)) { System.out.println(strings); } System.out.println("-----------"); for (List strings : combinations(alphabet)) { System.out.println(strings); } } public static List> combinations(List alphabet) { List> permutations = permutations(alphabet); List> 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  List> permutations(List alphabet) { ArrayList> permutations = new ArrayList<>(); if (alphabet.size() == 1) { permutations.add(alphabet); return permutations; } else { List> subPerm = permutations(alphabet.subList(1, alphabet.size())); T addedElem = alphabet.get(0); for (int i = 0; i < alphabet.size(); i++) { for (List permutation : subPerm) { int index = i; permutations.add(new ArrayList(permutation) {{ add(index, addedElem); }}); } } } return permutations; } } 

Aquí hay una solución recursiva en PHP. La publicación de WhirlWind describe con precisión la lógica. Vale la pena mencionar que generar todas las permutaciones se ejecuta en tiempo factorial, por lo que podría ser una buena idea usar un enfoque iterativo en su lugar.

 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); } } 

La función strDiff toma dos cadenas, s1 y s2 , y devuelve una nueva cadena con todo en s1 sin elementos en s2 (duplica la materia). Entonces, strDiff('finish','i') => 'fnish' (la segunda ‘i’ no se elimina).

Aquí hay un algoritmo en R, en caso de que alguien necesite evitar cargar bibliotecas adicionales como tenía que hacerlo.

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

Ejemplo de uso:

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

Solución Bourne shell – en un total de cuatro líneas (sin prueba para ningún caso de param):

 test $# -eq 1 && echo "$1" && exit for i in $*; do $0 `echo "$*" | sed -e "s/$i//"` | sed -e "s/^/$i /" done 

Este es un código recursivo para Java, la idea es tener un prefijo que agregue el rest de los caracteres:

 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); } } 

Ejemplo:

Entrada = "ABC"; Salida:

ABC ACB BAC BCA CAB CBA

Para ser completo, C ++

 #include  #include  #include  std::string theSeq = "abc"; do { std::cout < < theSeq << endl; } while (std::next_permutation(theSeq.begin(), theSeq.end())); 

...

 abc acb bac bca cab cba 

No se puede hablar realmente de resolver un problema de permultación en recursión sin publicar una implementación en un (dialecto de) lenguaje que fue pionero en la idea . Entonces, para completar, esta es una de las formas en que se puede hacer en 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)))))))) 

llamando (permof (list "foo" "bar" "baz")) obtendremos:

 '(("foo" "bar" "baz") ("foo" "baz" "bar") ("bar" "foo" "baz") ("bar" "baz" "foo") ("baz" "bar" "foo") ("baz" "foo" "bar")) 

No entraré en los detalles del algoritmo porque ya se explicó lo suficiente en otras publicaciones. La idea es la misma

Sin embargo, los problemas recursivos tienden a ser mucho más difíciles de modelar y pensar en medios destructivos como Python, C y Java, mientras que en Lisp o ML se puede express de forma concisa.