todas - permutaciones python

Permutaciones de recursión de Python

Question

Tengo problemas para tratar de hacer un código de permutación con recursión. Se supone que debe devolver una lista al uso con todas las posiciones posibles para cada letra. entonces para la palabra cat se supone que debe regresar [''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, pero no estoy seguro de cómo usarlos

Answer 1

Desea hacer la recursión, por lo que primero debe 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 una condición final:

permutation [a] = [a]

Entonces, 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.

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

Answer 2

Cuando está perdido en la función recursiva, debe dibujar el árbol de llamadas. La siguiente versión (inspirada @Ben answer) 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, debe dibujar el árbol de llamadas de estas funciones, ¿observa algo?

Answer 3

Recursivamente, piense en el caso base y construya desde esa intuición.

1) ¿Qué sucede cuando solo hay un personaje ''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 previa ''c'' nos da ''ca'', ''ac''.

3) Podemos continuar construyendo permutaciones cada vez mayores 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 incluyen el último carácter en la cadena s [-1], generamos una nueva cadena para cada posición donde podríamos incluir ese carácter y anexar 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

Answer 4

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