Come generare permutazioni di una lista senza “doppioni inversa” in Python utilizzando generatori

Question

Questo è legato alla domanda Come generare tutto permutazioni di una lista in Python

Come generare tutte le permutazioni che partita seguenti criteri : se due permutazioni sono opposto l'uno dell'altro (cioè [1,2,3,4] e [4,3,2, 1]), essi sono considerati uguali e solo uno di essi dovrebbe essere nel risultato finale .

Esempio:

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

sto permutando le liste che contengono numeri interi unici.

Il numero di permutazioni risultante sarà alto così mi piacerebbe usare generatori di Python, se possibile.

Modifica:. Mi piacerebbe non memorizzare l'elenco di tutte le permutazioni di memoria, se possibile,

Answer 1

Ho una meravigliosa follow alla proposta di SilentGhost - la pubblicazione di un risposta separata dal momento che i margini di un commento sarebbe troppo stretta per contenere codice: -)

itertools.permutations è costruito in (dal 2,6) e veloce. Abbiamo solo bisogno di una condizione di filtraggio che per ogni (perm, perm [:: - 1]) avrebbe accettato esattamente uno di loro. Dal momento che l'OP dice articoli sono sempre distinti, possiamo semplicemente confrontare ogni 2 elementi:

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

che stampa:

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

Questo funziona perché invertire la permutazione sarebbe sempre capovolgere il rapporto!
p[0] < p[1] o di qualsiasi altra coppia potrebbe anche funzionare, in modo da avere anche un certo controllo su cui la metà di permutazioni che si ottiene.

Non sono sicuro se c'è un modo più efficiente per filtrare. itertools.permutations garantisce ordine lessicografico, ma la posizione di p lexicographic e p[::-1] sono legati in maniera piuttosto complessa. In particolare, una semplice pausa a metà non funziona.

Ma ho il sospetto (non controllare) che l'iteratore incorporato con 2: 1 di filtraggio sarebbe superare qualsiasi implementazione personalizzata. E, naturalmente, vince sulla semplicità!

Answer 2

Se si generano permutazioni in ordine lessicografico, allora non c'è bisogno di memorizzare qualsiasi cosa per capire se il contrario di un dato permutazione è già stato visto. Basta confrontare lessicografico al suo inverso -. Se è più piccolo poi restituirlo, se è più grande quindi saltare it

C'è probabilmente un modo più efficiente per farlo, ma questo è semplice e ha le proprietà che si richiedono (implementabile come un generatore, utilizza O (n) memoria di lavoro).

Answer 3

Questa è una versione più concisa e più veloce di risposta accettato di ChristopheD, che mi è piaciuto molto. La ricorsione è grande. L'ho fatta rispettare uniquenss della lista in entrata, eliminando i duplicati, ma forse dovrebbe solo sollevare un'eccezione, invece.

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 4

Modifica : cambiata completamente per mantenere tutto come un generatore (non l'intera lista in memoria). Devono soddisfare i requisiti (calcola solo la metà delle possibili permutazioni (non quelli inversa). EDIT2 : aggiunto più breve (e più semplice) funzione fattoriale da qui .

Edit3: : (vedi commenti) - una versione con miglioramenti può essere trovato in la versione di bwopah .

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 5

Che ne dite di questo:

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)]

Inoltre, se il valore di ritorno deve essere un elenco, basta solo cambiare il rendimento ho a cedere lista (i), ma per scopi di iterazione, le tuple funzionerà bene.

Answer 6

Ecco il codice che fa il trucco. Per sbarazzarsi dei dups ho notato che per la vostra lista, se il valore della prima posizione è superiore al valore dell'ultima posizione, allora sarà un dup. Creo una mappa per tenere traccia di dove ogni elemento è stato nella lista per iniziare e quindi utilizzare tale carta per fare il test. Il codice, inoltre, non utilizza la ricorsione in modo che mantiene la sua impronta di memoria di piccole dimensioni. Anche la lista può essere di qualsiasi tipo articoli non solo i numeri vedere gli ultimi due casi di test.

Ecco il codice.

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)

e qui è l'uscita per i miei casi di test.

_________________________
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 7

Ecco la mia realizzazione:

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])

P funzione è una funzione permu regolare, dà tutte le possibilità. Il filtro è fatto quando itera il risultato. Semplicemente, ha due risultati possibili, il più piccolo metà del tutto Permus e più grande la metà del Permus. In questo esempio, il fuori contiene la parte più piccola della lista.

Answer 8

Questa è un'implementazione del suggerimento di onebyone

http://en.wikipedia.org/wiki/Permutation#Lexicographical_order_generation Il seguente algoritmo genera la prossima permutazione lessicografico dopo un dato permutazione. Cambia la permutazione data sul posto.

1. Trova l'indice più alto i tale che s [i]
2. Trova il più alto indice j> i tale che s [j]> s [i]. Tale j deve esistere, poiché i + 1 è un tale indice.
3. Swap s [i] con s [J].
4. inverso tutto l'ordine di tutti gli elementi dopo indice i

funzione:

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

controllare il nostro lavoro:

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

Answer 9

Alcuni codice di configurazione iniziale:

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 10

itertools.permutations fa esattamente quello che vuoi. si potrebbe fare di uso di reversed built-in pure