2

Estoy intentado resolver un ejercicio que se me planteo que es bastante simple, dada una lista, imprimir todas las posibles combinaciones/permutaciones de x elementos. Es decir, sacar todas las combinaciones posibles pero dado un filtro para los resultados.

De momento tengo esto:

def permutation( list , start , end ):
    if (start == end ):
        print list
    else:
        for i in xrange(start , end + 1):
            list[start] , list[i] = list[i] , list[start]            
            permutation( list , start + 1 , end )
            list[start] , list[i] = list[i] , list[start] #Backtracking

Ejemplo: lista [a,b,c] de 2 elementos, resultado esperado [a,b][a,c][b,a][b,c][c,a][c,b]

Y otra duda que tengo es si hay alguna forma de hacerlo pero con repeticiones. Con el ejemplo anterior, el resultado deseado: [a,b][a,c][b,a][b,c][c,a][c,b][a,a][b,b][c,c]

En mi ejercicio propuesto la lista tiene 45 elementos y se piden las combinaciones de 20 elementos.

3
  • con repeticiones ten en cuenta que la longitud del output será de len(permutation)^2. y en cada iteracion list[start] añades uno que sea doble -> aa, bb, cc...
    – lois6b
    el 7 dic. 2016 a las 11:34
  • Con repetición es simple: [[a,b] for a in lista for b in lista]. Del resto, no entiendo el enunciado. ¿Qué son start y end?¿Qué filtros aplicas a los resultados?¿Dónde está el resultado que devuelve la función? Tampoco deberías modificar directamente la lista de entrada, es peligroso, ni usar list como nombre de variable. el 7 dic. 2016 a las 12:41
  • Por favor aclara un poco tu problema, ¿a que te refieres con 'filtro'?, ¿cuál es el 'filtro'?, ¿las combinaciones son siempre de 2 elementos?, ¿que son los parámetros start y end?, etc. Tal y como está es difícil que te podamos ayudar. Si quieres combinaciones de 2 elementos lo sencillo es usar list comprehensions como bién te indica Chema, para las permutaciones de 2 elementos te añades un condicional [[a, b] for a in lista for b in lista if a != b].
    – FJSevilla
    el 7 dic. 2016 a las 13:17

2 respuestas 2

1

Existe un módulo en la libería estándar, itertools, que implementa iteradores eficientes para muchos tipos de combinaciones.

from itertools import combinations, combinations_with_replacement

lista = [a, b, c]

# dos elementos, sin repetición
sin_repeticion = [x for x in combinations(lista, 2)]

# dos elementos, con repetición
con_repeticion = [x for x in combinations_with_replacement(lista, 2)]

https://docs.python.org/3/library/itertools.html

El filtro puedes establecerlo como un condicional en la list comprehension o en un bucle for sobre el iterador.

1

Una manera muy sencilla de resolverlo sería simplemente usando list comprehension

mi_lista = [1,2,3,4]
# para los elementos con repeticiones, obtenemos una lista de tuplas
print [ (x,y) for x in mi_lista for y in mi_lista ]
# para los elementos sin repeticón solo agregamos la condición,
# para que los elementos x,y sean diferentes
print [ (x,y) for x in mi_lista for y in mi_lista if x!=y]

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.