Enumerazione efficiente di sottoinsiemi ordinati in Python

Question

Non sono sicuro della terminologia matematica appropriata per il codice che sto tentando di scrivere. Mi piacerebbe generare combinazioni di numeri interi univoci, in cui "sottoinsiemi ordinati" di ciascuna combinazione vengono utilizzati per escludere alcune combinazioni successive.

Speriamo che un esempio renderà questo chiaro:

from itertools import chain, combinations 
​ 
mylist = range(4) 
max_depth = 3 

rev = chain.from_iterable(combinations(mylist, i) for i in xrange(max_depth, 0, -1)) 
for el in list(rev): 
    print el 

---

che i risultati di codice in uscita che contiene tutti i sottoinsiemi che voglio, ma anche alcuni tra quelli in più che non lo faccio. Ho inserito manualmente i commenti per indicare quali elementi non desidero.

(0, 1, 2) 
(0, 1, 3) 
(0, 2, 3) 
(1, 2, 3) 
(0, 1) # Exclude: (0, 1, _) occurs as part of (0, 1, 2) above 
(0, 2) # Exclude: (0, 2, _) occurs above 
(0, 3) # Keep 
(1, 2) # Exclude: (1, 2, _) occurs above 
(1, 3) # Keep: (_, 1, 3) occurs above, but (1, 3, _) does not 
(2, 3) # Keep 
(0,) # Exclude: (0, _, _) occurs above 
(1,) # Exclude: (1, _, _) occurs above 
(2,) # Exclude: (2, _) occurs above 
(3,) # Keep 

---

Così, l'uscita desiderata del mio generatore o iteratore sarebbe:

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

So che potrei fare una lista di tutti i (voluto e non voluto) combinazioni e poi filtrare quelli che non voglio, ma mi chiedevo se esistesse un modo più efficiente, generatore o iteratore.

Answer 1

Si sta tentando di escludere qualsiasi combinazione che è un prefisso di una combinazione precedentemente restituito. Fare così è semplice.

• Se una tupla t ha lunghezza max_depth, non può essere un prefisso di una tupla precedentemente tornato, dal momento che ogni tupla è un prefisso avrebbe dovuto essere più lungo.
• Se una tupla t termina con mylist[-1], allora non può essere un prefisso di una tupla precedentemente restituita, poiché non ci sono elementi che potrebbero essere legalmente aggiunti alla fine di t per estenderlo.
• Se una tupla t ha lunghezza inferiore max_depth e non finisce con mylist[-1], allora t è un prefisso della tupla precedentemente restituito t + (mylist[-1],) e t non deve essere restituito.

Così, le combinazioni si dovrebbe generare sono esattamente quelle di lunghezza max_depth e quelle più brevi che terminano con mylist[-1]. Il codice seguente lo fa, esattamente nello stesso ordine in cui il codice originale, e casi di movimentazione in modo corretto come maxdepth > len(mylist):

def nonprefix_combinations(iterable, maxlen): 
    iterable = list(iterable) 
    if not (iterable and maxlen): 
     return 
    for comb in combinations(iterable, maxlen): 
     yield comb 
    for length in xrange(maxlen-2, -1, -1): 
     for comb in combinations(iterable[:-1], length): 
      yield comb + (iterable[-1],) 

(ho assunto qui che, nel caso in cui maxdepth == 0, ancora non si vuole includere la tupla vuota nell'output, anche se per maxdepth == 0, non è un prefisso di una tupla precedentemente restituita. Se si desidera la tupla vuota in questo caso, è possibile modificare if not (iterable and maxlen) in if not iterable.)

Answer 2

Ho notato un modello interessante nell'output desiderato e ho un generatore che lo produce. Funziona per tutti i tuoi casi?

from itertools import combinations 

def orderedSetCombination(iterable, r): 
    # Get the last element of the iterable 
    last = (iterable[-1],) 
    # yield all the combinations of the iterable without the 
    # last element 
    for iter in combinations(iterable[:-1], r): 
     yield iter 
    # while r > 1 reduce r by 1 and yield all the combinations 
    while r>1: 
     r -= 1 
     for iter in combinations(iterable[:-1], r): 
      yield iter+last 
    # yield the last item 
    yield last 

iter = [0,1,2,3] 

for el in (list(orderedSetCombination(iter, 3))): 
    print(el) 

Ecco la mia spiegazione della logica:

# All combinations that does not include the last element of the iterable 
# taking r = max_depth items at a time 

(0,1,2) 

# from here on, its the combinations of all the elements except 
# the last element and the last element is added to it. 
# so here taking r = r -1 items at a time and adding the last element 
# combinations([0,1,2], r=2) 

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

# the only possible value right now at index r = 2 is the last element (3) 
# since all possible values of (0,1,_) (0,2,_) (1,2,_) are already listed 
# So reduce r by 1 again and continue: combinations([0,1,2], r=1) 

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

# continue until r == 0 and then yield the last element 

(3,)