es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Creando Permutaciones con Python

25 Jul, 2023 Programación

Estoy tratando de escribir un programa para obtener todas las permutaciones de una cadena de letras utilizando la recursión. Como soy principiante en Python, aprendí sobre la recursión con ejemplos como el número de Fibonacci y el factorial. Entiendo estos ejemplos matemáticos, pero aún tengo dificultades para construir un programa funcional con recursión. Intenté entender otros problemas similares en la web pero aún no logro comprender el concepto.

Entonces, el problema es: ¿Cómo obtener todas las permutaciones de una cadena de letras? Por ejemplo, str = 'abc'. Mi lógica es algo así:
1. crear 3 espacios para 3 letras abc
2. agregar una letra, digamos ‘a’, y puede ir a cualquiera de los 3 espacios
3. siguiendo el caso anterior, agregar ‘b’. Ahora solo quedan 2 espacios y ‘b’ puede ir a cualquiera de esos 2 espacios.
4. repetir hasta que no queden espacios. Ahora llegamos a un caso base donde el número de espacios es igual a 0.

Pero no puedo escribirlo en código.

Tags:  ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para resolver este problema usando recursión, podemos seguir estos pasos:

    1. Definir una función que tome una cadena como entrada y devuelva una lista con todas sus permutaciones.
    2. Comprobar si la longitud de la cadena es 1. Si es así, devolver la cadena como una lista con un solo elemento.
    3. Para cada caracter en la cadena, crear una nueva cadena que consista en todos los otros caracteres excepto el actual, y llamar recursivamente a la misma función con esta nueva cadena como entrada.
    4. Combinar el caracter actual con cada una de las permutaciones obtenidas en el paso anterior, y añadirlas a una lista.
    5. Devolver la lista de todas las permutaciones obtenidas.

    Aquí está el código de esta función en Python:

    def get_permutations(s):
    if len(s) == 1:
        return [s]
    result = []
    for i, c in enumerate(s):
        rest = s[:i] + s[i+1:]
        perms = get_permutations(rest)
        for p in perms:
            result.append(c + p)
    return result

    Para usar esta función, simplemente llámela con una cadena como entrada:

    s = 'abc'
perms = get_permutations(s)
print(perms) # imprime ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

    Esta función funciona llamándose recursivamente con una subcadena de la cadena original que excluye el caracter seleccionado actualmente. El caso base es cuando la longitud de la cadena es 1, donde la función simplemente devuelve la cadena como una lista con un solo elemento.

    Luego, para cada caracter en la cadena, la función crea una nueva cadena con todos los caracteres excepto el actual, y se llama recursivamente con esta nueva cadena. Luego combina el caracter actual con cada permutación obtenida de la llamada recursiva, y las añade a la lista de resultados. Finalmente, la función devuelve la lista de todas las permutaciones obtenidas.

Comments are closed.