Efektywne wyliczanie uporządkowanych podzbiorów w Pythonie

Question

Nie jestem pewien odpowiedniej terminologii matematycznej dla kodu, który próbuję napisać. Chciałbym generować kombinacje unikalnych liczb całkowitych, gdzie "uporządkowane podzbiory" każdej kombinacji są używane do wykluczenia pewnych późniejszych kombinacji.

Mam nadzieję przykładem będzie to jasne:

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 

---

, że wyniki kodu na wyjściu, który zawiera wszystkie podzbiory chcę, ale także jakieś dodatkowe te, które nie. Ręcznie wstawiłem komentarze, aby wskazać, których elementów nie chcę.

(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 

---

Zatem pożądane wyjście mojego generatora lub iterator byłoby:

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

Wiem, że mógłbym zrobić listę wszystkich (chciane i niechciane) kombinacji, a następnie odfiltrować te, których nie chcę, ale zastanawiałem się, czy istnieje bardziej wydajny, oparty na generatorze lub iteratorze sposób.

Answer 1

Próbujesz wyklucza jakąkolwiek kombinację, która jest prefiks z wcześniej wrócił kombinacji. Takie postępowanie jest proste.

• Jeśli krotką t ma długość max_depth, to nie może być przedrostek z wcześniej wrócił krotki, ponieważ każda krotka jest to prefiks musiałby być dłuższy.
• Jeśli krotka t kończy się na mylist[-1], to nie może być prefiksem poprzednio zwracanej krotki, ponieważ nie ma żadnych elementów, które można legalnie dodać na końcu t, aby ją rozszerzyć.
• Jeśli krotką t ma długość mniejszą niż max_depth i nie kończy się mylist[-1], następnie t jest prefiks wcześniej zwróconej krotki t + (mylist[-1],) i nie powinny być zwracane t.

Tak więc kombinacje, które należy wygenerować, są dokładnie tymi o długości max_depth i krótszymi, które kończą się na mylist[-1]. Poniższy kod działa tak, dokładnie w takiej samej kolejności jak oryginalnego kodu i prawidłowo obchodzić się przypadki takie jak 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],) 

(zakłada się, że już tutaj, że w przypadku, gdy maxdepth == 0, nadal nie chcą dołącz pustą krotkę do wyjścia, nawet jeśli dla maxdepth == 0, nie jest to prefiks poprzednio zwracanej krotki .Jeśli chcesz pustą krotkę w tym przypadku, możesz zmienić if not (iterable and maxlen) na if not iterable.)

Answer 2

Zauważyłem interesujący wzór w pożądanym wyjściu i mam generator, który to produkuje. Czy to działa we wszystkich twoich przypadkach?

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) 

Oto moja wyjaśnieniu logiki:

# 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,)