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.

¿Cómo puedo obtener las permutaciones para cada número dentro del rango 1 a lst?

18 Jul, 2023 Programación

Entonces escribí este código que intenta devolver todas las permutaciones de un número dentro del rango (1, lst).

def permutacion(lst):
if isinstance(lst, int):
lst = list(range(1, lst + 1))
if len(lst) == 0:
return []
if len(lst) == 1:
return ({(1,)})
if len(lst) == 2:
return ({(1,2),(2,1)})
l = []
for i in range(len(lst)):
m = lst[i]
remLst = lst[:i] + lst[i + 1:]
for p in permutacion(remLst):
l.append(tuple([m] + list(p)))
return set(l)

Sin embargo, la salida que obtuve parece incorrecta… porque cuando ingreso

permutacion(3)

Obtengo…

{(1, 2, 1), (1, 1, 2), (3, 2, 1), (2, 1, 2), (2, 2, 1), (3, 1, 2)}

pero se supone que debo obtener

{(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)}

y cuando mi entrada es permutacion(4), mi salida es

{(4, 1, 2, 1), (1, 4, 1, 2), (4, 1, 1, 2), (3, 1, 2, 1), (4, 3, 2, 1), (3, 2, 2, 1), (4, 3, 1, 2), (3, 4, 2, 1), (3, 2, 1, 2), (4, 2, 2, 1), (3, 1, 1, 2), (3, 4, 1, 2), (2, 3, 2, 1), (4, 2, 1, 2), (2, 4, 1, 2), (2, 4, 2, 1), (2, 3, 1, 2), (1, 2, 1, 2), (1, 2, 2, 1), (1, 3, 2, 1), (2, 1, 1, 2), (2, 1, 2, 1), (1, 4, 2, 1), (1, 3, 1, 2)}

pero se supone que debo obtener esto…

{(4, 3, 1, 2), (3,4, 1, 2), (3, 1, 4, 2), (3, 1, 2,4),
(4, 1, 3, 2), (1, 4, 3, 2), (1, 3, 4, 2), (1, 3, 2, 4),
(4, 1, 2, 3), (1, 4, 2, 3), (1, 2, 4, 3), (1, 2, 3, 4),
(4, 3, 2, 1), (3, 4, 2, 1), (3, 2, 4, 1), (3, 2, 1, 4),
(4, 2, 3, 1), (2, 4, 3, 1), (2, 3, 4, 1), (2, 3, 1, 4),
(4, 2, 1, 3), (2, 4, 1, 3), (2, 1, 4, 3), (2, 1, 3, 4)}

¿Qué cambios debo hacer para que mi código devuelva la salida correcta?

Tags:  , , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    El problema con el código radica en los casos base para las permutaciones de longitud 1 y 2. En lugar de devolver conjuntos con tuplas que contienen valores duplicados, deberíamos devolver conjuntos con tuplas que contienen valores únicos.

    Aquí está el código corregido:

    def permutacion(lst):
    if isinstance(lst, int):
        lst = list(range(1, lst + 1))
    if len(lst) == 0:
        return []
    if len(lst) == 1:
        return {(lst[0],)}
    if len(lst) == 2:
        return {(lst[0], lst[1]), (lst[1], lst[0])}
    l = []
    for i in range(len(lst)):
        m = lst[i]
        remLst = lst[:i] + lst[i + 1:]
        for p in permutacion(remLst):
            l.append(tuple([m] + list(p)))
    return set(l)

    Con el código corregido, permutacion(3) devuelve [(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)] y permutacion(4) devuelve [(1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3), (1,4,3,2), (2,1,3,4), (2,1,4,3), (2,3,1,4), (2,3,4,1), (2,4,1,3), (2,4,3,1), (3,1,2,4), (3,1,4,2), (3,2,1,4), (3,2,4,1), (3,4,1,2), (3,4,2,1), (4,1,2,3), (4,1,3,2), (4,2,1,3), (4,2,3,1), (4,3,1,2), (4,3,2,1)], que es la salida correcta.

Comments are closed.