Cómo generar permutaciones de una lista sin "duplicados marcha atrás" en Python usando generadores

Question

Esto se relaciona con la pregunta How to generate all permutations of a list in Python

Cómo generar todas las permutaciones que partido siguientes criterios: si dos permutaciones son inverso el uno del otro (es decir [1,2,3,4] y [4,3,2,1]), se consideran iguales y solo uno de ellos debe estar en el resultado final.

Ejemplo:

permutations_without_duplicates ([1,2,3]) 
[1, 2, 3] 
[1, 3, 2] 
[2, 1, 3] 

estoy listas que contengan números enteros únicos permutar.

El número de permutaciones resultantes será alto, por lo que me gustaría utilizar los generadores de Python si es posible.

Editar: Me gustaría no almacenar la lista de todas las permutaciones en la memoria si es posible.

Answer 1

Tengo una maravillosa seguimiento a la propuesta de SilentGhost - la publicación de una respuesta por separado ya que los márgenes de un comentario serían demasiado estrechas para contener código :-)

itertools.permutations está incorporada (desde 2,6) y rápido. Solo necesitamos una condición de filtrado para cada (permanente, permanente [:: - 1]) aceptaría exactamente una de ellas. Desde el PO dice artículos son siempre distintas, sólo podemos comparar los 2 elementos:

for p in itertools.permutations(range(3)): 
    if p[0] < p[-1]: 
     print p 

que imprime:

(0, 1, 2) 
(0, 2, 1) 
(1, 0, 2) 

Esto funciona porque la inversión de la permutación se voltee siempre la relación!
p[0] < p[1] o cualquier otro par también funcionaría, por lo que también tienes cierto control sobre la mitad de las permutaciones que obtienes.

No estoy seguro si hay alguna manera más eficaz de filtrar.itertools.permutations garantiza el orden lexicográfico, pero la posición lexicográfica p y p[::-1] están relacionadas de una manera bastante compleja. En particular, simplemente detenerse en el medio no funciona.

Pero sospecho (no comprobé) que el iterador incorporado con filtrado 2: 1 superaría a cualquier implementación personalizada. ¡Y por supuesto gana en simplicidad!

Answer 2

itertools.permutations hace exactamente lo que quiere. también puede hacer uso de reversed built-in

Answer 3

EDIT: cambiado por completo para mantener todo como un generador (nunca la lista completa en la memoria). Debe cumplir con los requisitos (sólo calcula la mitad de las posibles permutaciones (no los inversos) Edit2: añadido más corto (y más simple) función factorial de here

Edit3::.. (Ver comentarios) - una versión con mejoras se pueden encontrar en bwopah's version

def fac(x): 
    return (1 if x==0 else x * fac(x-1)) 

def all_permutations(plist): 
    global counter 

    if len(plist) <=1: 
     yield plist 
    else: 
     for perm in all_permutations(plist[1:]): 
      for i in xrange(len(perm)+1): 
       if len(perm[:i] + plist[0:1] + perm[i:]) == lenplist: 
         if counter == limit: 
          raise StopIteration 
         else: 
          counter = counter + 1 
       yield perm[:i] + plist[0:1] + perm[i:] 

counter = 0 
plist = ['a','b','c'] 
lenplist = len(plist) 
limit = fac(lenplist)/2 

all_permutations_gen = all_permutations(plist) 
print all_permutations_gen 
print list(all_permutations_gen) 

Answer 4

¿Qué tal esto:.

from itertools import permutations 

def rev_generator(plist): 
    reversed_elements = set() 
    for i in permutations(plist): 
     if i not in reversed_elements: 
      reversed_i = tuple(reversed(i)) 
      reversed_elements.add(reversed_i) 
      yield i 

>>> list(rev_generator([1,2,3])) 
[(1, 2, 3), (1, 3, 2), (2, 1, 3)] 

Además, si el valor de retorno debe ser una lista, puede simplemente cambiar el rendimiento a la lista de rendimiento (i), pero para fines de iteración, las tuplas funcionarán bien.

Answer 5

Aquí está el código que hace el truco. Para deshacerse de los dups noté que para su lista si el valor de la primera ubicación es mayor que el valor de la última ubicación, entonces será un dup. Creo un mapa para hacer un seguimiento de dónde estaba cada elemento en la lista para comenzar y luego usar ese mapa para hacer la prueba. El código tampoco usa recursividad, por lo que mantiene pequeña su huella de memoria. Además, la lista puede ser de cualquier ítem, no solo los números ven los dos últimos casos de prueba.

Aquí está el código.

class Permutation: 
    def __init__(self, justalist): 
     self._data = justalist[:] 
     self._len=len(self._data) 
     self._s=[] 
     self._nfact=1 
     self._map ={} 
     i=0 
     for elem in self._data: 
      self._s.append(elem) 
      self._map[str(elem)]=i 
      i+=1 
      self._nfact*=i 
     if i != 0: 
      self._nfact2=self._nfact//i 

    def __iter__(self): 
     for k in range(self._nfact): 
      for i in range(self._len): 
       self._s[i]=self._data[i] 
      s=self._s 
      factorial=self._nfact2 
      for i in range(self._len-1): 
       tempi = (k // factorial) % (self._len - i) 
       temp = s[i + tempi] 
       for j in range(i + tempi,i,-1): 
        s[j] = s[j-1] 
       s[i] = temp 
       factorial //= (self._len - (i + 1)) 

      if self._map[str(s[0])] < self._map[str(s[-1])]: 
       yield s 




s=[1,2] 
print("_"*25) 
print("input list:",s) 
for sx in Permutation(s): 
    print(sx) 

s=[1,2,3] 
print("_"*25) 
print("input list:",s) 
for sx in Permutation(s): 
    print(sx) 

s=[1,2,3,4] 
print("_"*25) 
print("input list:",s) 
for sx in Permutation(s): 
    print(sx) 

s=[3,2,1] 
print("_"*25) 
print("input list:",s) 
for sx in Permutation(s): 
    print(sx) 

s=["Apple","Pear","Orange"] 
print("_"*25) 
print("input list:",s) 
for sx in Permutation(s): 
    print(sx) 

s=[[1,4,5],"Pear",(1,6,9),Permutation([])] 
print("_"*25) 
print("input list:",s) 
for sx in Permutation(s): 
    print(sx) 

y aquí está la salida para mis casos de prueba.

_________________________ 
input list: [1, 2] 
[1, 2] 
_________________________ 
input list: [1, 2, 3] 
[1, 2, 3] 
[1, 3, 2] 
[2, 1, 3] 
_________________________ 
input list: [1, 2, 3, 4] 
[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, 4, 1, 3] 
[3, 1, 2, 4] 
[3, 2, 1, 4] 
_________________________ 
input list: [3, 2, 1] 
[3, 2, 1] 
[3, 1, 2] 
[2, 3, 1] 
_________________________ 
input list: ['Apple', 'Pear', 'Orange'] 
['Apple', 'Pear', 'Orange'] 
['Apple', 'Orange', 'Pear'] 
['Pear', 'Apple', 'Orange'] 
_________________________ 
input list: [[1, 4, 5], 'Pear', (1, 6, 9), <__main__.Permutation object at 0x0142DEF0>] 
[[1, 4, 5], 'Pear', (1, 6, 9), <__main__.Permutation object at 0x0142DEF0>] 
[[1, 4, 5], 'Pear', <__main__.Permutation object at 0x0142DEF0>, (1, 6, 9)] 
[[1, 4, 5], (1, 6, 9), 'Pear', <__main__.Permutation object at 0x0142DEF0>] 
[[1, 4, 5], (1, 6, 9), <__main__.Permutation object at 0x0142DEF0>, 'Pear'] 
[[1, 4, 5], <__main__.Permutation object at 0x0142DEF0>, 'Pear', (1, 6, 9)] 
[[1, 4, 5], <__main__.Permutation object at 0x0142DEF0>, (1, 6, 9), 'Pear'] 
['Pear', [1, 4, 5], (1, 6, 9), <__main__.Permutation object at 0x0142DEF0>] 
['Pear', [1, 4, 5], <__main__.Permutation object at 0x0142DEF0>, (1, 6, 9)] 
['Pear', (1, 6, 9), [1, 4, 5], <__main__.Permutation object at 0x0142DEF0>] 
['Pear', <__main__.Permutation object at 0x0142DEF0>, [1, 4, 5], (1, 6, 9)] 
[(1, 6, 9), [1, 4, 5], 'Pear', <__main__.Permutation object at 0x0142DEF0>] 
[(1, 6, 9), 'Pear', [1, 4, 5], <__main__.Permutation object at 0x0142DEF0>] 

Answer 6

esta es una implementación de la sugerencia de OneByOne

de http://en.wikipedia.org/wiki/Permutation#Lexicographical_order_generation El siguiente algoritmo genera la siguiente permutación lexicográfico después de una permutación dada. Cambia la permutación dada en el lugar.

1. Encuentra el índice más alto i tal que s [i] < s [i + 1]. Si no existe tal índice, la permutación es la última permutación.
2. Encuentra el índice más alto j> i tal que s [j]> s [i]. Tal j debe existir, ya que i + 1 es ese índice.
3. Intercambia s [i] con s [j].
4. inversa todo el fin de todos los elementos después de índice i

la función:

def perms(items): 
    items.sort() 
    yield items[:] 
    m = [len(items)-2] # step 1 
    while m: 
     i = m[-1] 
     j = [ j for j in range(i+1,len(items)) if items[j]>items[i] ][-1] # step 2 
     items[i], items[j] = items[j], items[i] # step 3 
     items[i+1:] = list(reversed(items[i+1:])) # step 4 
     if items<list(reversed(items)): 
      yield items[:] 
     m = [ i for i in range(len(items)-1) if items[i]<items[i+1] ] # step 1 

comprobar nuestro trabajo:

>>> foo=list(perms([1,3,2,4,5])) 
>>> True in [(list(reversed(i)) in foo) for i in foo] 
False 

Answer 7

Si genera permutaciones en orden lexicográfico, entonces no necesita almacenar nada para determinar si ya se ha visto el reverso de una permutación dada. Simplemente tiene que compararlo lexicográficamente con su reverso; si es más pequeño, devuélvalo, si es más grande, sáltelo.

Probablemente exista una forma más eficiente de hacerlo, pero esto es simple y tiene las propiedades que necesita (implementable como generador, utiliza O (n) memoria de trabajo).

Answer 8

Algunos código de configuración primero:

try: 
    from itertools import permutations 
except ImportError: 
    # straight from http://docs.python.org/library/itertools.html#itertools.permutations 
    def permutations(iterable, r=None): 
     # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC 
     # permutations(range(3)) --> 012 021 102 120 201 210 
     pool = tuple(iterable) 
     n = len(pool) 
     r = n if r is None else r 
     if r > n: 
      return 
     indices = range(n) 
     cycles = range(n, n-r, -1) 
     yield tuple(pool[i] for i in indices[:r]) 
     while n: 
      for i in reversed(range(r)): 
       cycles[i] -= 1 
       if cycles[i] == 0: 
        indices[i:] = indices[i+1:] + indices[i:i+1] 
        cycles[i] = n - i 
       else: 
        j = cycles[i] 
        indices[i], indices[-j] = indices[-j], indices[i] 
        yield tuple(pool[i] for i in indices[:r]) 
        break 
      else: 
       return 

def non_reversed_permutations(iterable): 
    "Return non-reversed permutations for an iterable with unique items" 
    for permutation in permutations(iterable): 
     if permutation[0] < permutation[-1]: 
      yield permutation 

Answer 9

Ésta es una versión más concisa y más rápido de respuesta aceptada de ChristopheD, que me gustó mucho. La recursión es genial. Lo hice hacer cumplir las características únicas de la lista entrante eliminando duplicados, sin embargo, tal vez solo debería generar una excepción.

def fac(x): 
    return (1 if x==0 else x * fac(x-1)) 

def permz(plist): 
    plist = sorted(set(plist)) 
    plen = len(plist) 
    limit = fac(plen)/2 
    counter = 0 
    if plen==1: 
     yield plist 
    else: 
     for perm in permz(plist[1:]): 
      for i in xrange(plen): 
       if counter == limit: 
        raise StopIteration 
       counter += 1 
       yield perm[:i] + plist[0:1] + perm[i:] 

# ---- testing ---- 
plists = [ 
    list('love'), 
    range(5), 
    [1,4,2,3,9], 
    ['a',2,2.1], 
    range(8)]    

for plist in plists: 
    perms = list(permz(plist)) 
    print plist, True in [(list(reversed(i)) in foo) for i in perms] 

Answer 10

Aquí es mi aplicación:

a = [1,2,3,4] 

def p(l): 
    if len(l) <= 1: 
    yield l 
    else: 
    for i in range(len(l)): 
     for q in p([l[j] for j in range(len(l)) if j != i]): 
     yield [l[i]] + q 

out = (i for i in p(a) if i < i[::-1]) 

función P es una función permu regular, da todas las posibilidades. El filtro está hecho cuando itera el resultado. Simplemente, tiene dos resultados posibles, la mitad más pequeña de todo el permo y la mitad más grande del permo. En este ejemplo, el out contiene la mitad más pequeña de la lista.