Permutaciones de la recursión de Python

Estoy teniendo problemas tratando de hacer un código de permutación con recursión. Se supone que esto devuelve una lista al uso con todas las posiciones posibles para cada letra. así que para la palabra cat se supone que se devuelve ['cat','act',atc,'cta','tca','tac'] . hasta ahora tengo esto

 def permutations(s): lst=[] if len(s) == 1 or len(s) == 0 : # Return a list containing the string, not the string return [s] # Call permutations to get the permutations that don't include the # first character of s plst = permutations(s[1:]) print(plst) for item in plst: print (item) plst= permutations(s[1+1:]) # Now move through each possible position of the first character # and create a new string that puts that character into the strings # in plst for i in range(len(s)): pass # Create a new string out of item # and put it into lst # Modify for item in lst: print(index) 

Hay pasos allí, pero no estoy seguro de cómo usarlos.

Desea hacer recursión, por lo que primero tiene que averiguar cómo funcionaría la recursión. En este caso es el siguiente:

 permutation [a,b,c,...] = [a + permutation[b,c,...], b + permutation[a,c,..], ...] 

Y como condición final:

 permutation [a] = [a] 

Así que la recursión divide la lista en sublistas con un elemento extraído cada vez. Luego este elemento se agrega al frente de cada una de las permutaciones de la sublista.

Así que en pseudo-código:

 def permutation(s): if len(s) == 1: return [s] perm_list = [] # resulting list for a in s: remaining_elements = [x for x in s if x != a] z = permutation(remaining_elements) # permutations of sublist for t in z: perm_list.append([a] + t) return perm_list 

¿Esto ayuda?

Recursivamente, piensa en el caso base y construye desde esa intuición.

1) ¿Qué sucede cuando hay un solo carácter ‘c’? Solo hay una permutación de ese elemento, por lo que devolvemos una lista que contiene solo ese elemento.

2) ¿Cómo podemos generar la siguiente permutación dada la última? Agregar una letra adicional ‘a’ en todas las posiciones posibles en la permutación anterior ‘c’ nos da ‘ca’, ‘ac’.

3) Podemos continuar creando permutaciones cada vez más grandes agregando un carácter adicional en todas las posiciones posibles en cada permutación anterior.

El siguiente código devuelve una lista de un carácter si la cadena tiene un carácter o menos. De lo contrario, para todas las permutaciones que no incluyan el último carácter en la cadena s [-1], generamos una nueva cadena para cada posición en la que podríamos incluir ese carácter y agregamos la nueva cadena a nuestra lista actual de permutaciones.

 def permutations(s): if len(s) <= 1: return [s] else: perms = [] for e in permutations(s[:-1]): for i in xrange(len(e)+1): perms.append(e[:i] + s[-1] + e[i:]) return perms 

Cuando estás perdido en la función recursiva, debes dibujar el árbol de llamadas. La siguiente versión (inspirada en @Ben respuesta) mantiene el orden de entrada (si la entrada está en orden lexicográfico, la lista de permutaciones será '012' -> ['012', '021', '102', '120', '201', '210'] .

 def permut2(mystr): if len(mystr) <= 1: return [mystr] res = [] for elt in mystr: permutations = permut2(mystr.replace(elt, "")) for permutation in permutations: res.append(elt + permutation) return res 

La siguiente versión funciona para cadenas y listas, observe que el paso de reconstrucción no es el mismo:

 def permut(array): if len(array) == 1: return [array] res = [] for permutation in permut(array[1:]): for i in range(len(array)): res.append(permutation[:i] + array[0:1] + permutation[i:]) return res 

Como ejercicio, debes dibujar el árbol de llamadas de estas funciones, ¿notas algo?

 def permutations(string_input, array, fixed_value=""): for ch in string_input: permutations(string_input.replace(ch, ""), array, fixed_value + ch) if not string_input: array.append(fixed_value) 

Puedes llamarlo por

 array = [] permutations("cat", array) print array 

Esta es la solución más fácil que se me ocurrió.

  def permutations(_string): # stores all generated permutations permutations = [] # this function will do recursion def step(done, remain): # done is the part we consider "permutated" # remain is the set of characters we will use # if there is nothing left we can appened generated string if remain == '': permutations.append(done) else: # we iterate over the remaining part and indexing each character for i, char in enumerate(remain): # we dont want to repeat occurance of any character so pick the remaining # part minus the currect character we use in the loop rest = remain[:i] + remain[i + 1:] # use recursion, add the currect character to done part and mark rest as remaining step(done + char, rest) step("", _string) return permutations 

Puedes probarlo con:

 @pytest.mark.parametrize('_string,perms', ( ("a", ["a"]), ("ab", ["ab", "ba"]), ("abc", ["abc", "acb", "cba", "cab", "bac", "bca"]), ("cbd", ["cbd", "cdb", "bcd", "bdc", "dcb", "dbc"]) )) def test_string_permutations(_string, perms): assert set(permutations(_string)) == set(perms) 

Sé que este es un yo también, pero creo que este podría ser más fácil de entender para algunas personas …

  1. El caso base es cuando la entrada es solo un carácter.
  2. Configure un bucle for que recorra cada una de las letras de la cadena.
  3. Otro bucle for recursivamente permuta a través de todas las otras posibilidades.

permuta (s) de def:

 out = [] if len(s) == 1: out = [s] else: for i,let in enumerate(s): for perm in permute(s[:i]+s[i+1:]): out += [let+perm] return out 

Puede usar una función que itera un índice a través de la lista, y generar una lista consistente en el valor en el índice seguido de las permutaciones del rest de los valores de la lista. A continuación se muestra un ejemplo de las funciones de Python 3.5+:

 def permutations(s): if not s: yield [] yield from ([s[i], *p] for i in range(len(s)) for p in permutations(s[:i] + s[i + 1:])) 

de modo que la list(permutations('abc')) devuelve:

 [['a', 'b', 'c'], ['a', 'c', 'b'], ['b', 'a', 'c'], ['b', 'c', 'a'], ['c', 'a', 'b'], ['c', 'b', 'a']]