Algorytm dla itertools.combinations w Pythonie

Question

Rozwiązałem zagadkę programistyczną obejmującą kombinacje. Doprowadziło mnie to do wspaniałej funkcji itertools.combinations i chciałbym wiedzieć, jak to działa pod maską. Dokumentacja mówi, że algorytm jest z grubsza równoważna następującej:

def combinations(iterable, r): 
    # combinations('ABCD', 2) --> AB AC AD BC BD CD 
    # combinations(range(4), 3) --> 012 013 023 123 
    pool = tuple(iterable) 
    n = len(pool) 
    if r > n: 
     return 
    indices = list(range(r)) 
    yield tuple(pool[i] for i in indices) 
    while True: 
     for i in reversed(range(r)): 
      if indices[i] != i + n - r: 
       break 
     else: 
      return 
     indices[i] += 1 
     for j in range(i+1, r): 
      indices[j] = indices[j-1] + 1 
     yield tuple(pool[i] for i in indices) 

Mam pomysł: zaczynamy od najbardziej oczywistych kombinacji (r pierwsze kolejnymi elementami). Następnie zmieniamy jeden (ostatni) element, aby uzyskać każdą kolejną kombinację.

To, z czym walczę, to uwarunkowana pętla for.

for i in reversed(range(r)): 
    if indices[i] != i + n - r: 
     break 

Ta ekspedycja jest bardzo zwięzła i podejrzewam, że dzieje się tam, gdzie dzieje się cała magia. Proszę, daj mi podpowiedź, abym mógł to zrozumieć.

Answer 1

Pętla ma dwa cele:

1. kończące jeżeli ostatnia indeksu lista została osiągnięta
2. Ustalenie najbardziej prawe miejsce na liście indeksu, które można prawnie zwiększyć. Ta pozycja jest punktem wyjściowym do resetowania wszystkich indeców w prawo.

Załóżmy, że masz możliwość iteracji ponad 5 elementów i chcesz kombinacji długości 3. Potrzebne do tego są generowane listy indeksów.Soczyste część powyższego algorytmu generuje następnego takiego Indeksu listę z obecnego:

# obvious 
index-pool:  [0,1,2,3,4] 
first index-list: [0,1,2] 
        [0,1,3] 
        ... 
        [1,3,4] 
last index-list: [2,3,4] 

i + n - r jest maksymalna wartość wskaźnika i w indeksie liście:

index 0: i + n - r = 0 + 5 - 3 = 2 
index 1: i + n - r = 1 + 5 - 3 = 3 
index 2: i + n - r = 2 + 5 - 3 = 4 
# compare last index-list above 

=>

for i in reversed(range(r)): 
    if indices[i] != i + n - r: 
     break 
else: 
    break 

To pętle wstecz przez curre nt index-list i zatrzymuje się na pierwszej pozycji, która nie zawiera maksymalnej wartości indeksu. Jeśli wszystkie pozycje mają maksymalną wartość indeksu, nie ma już listy indeksów, czyli return.

W ogólnym przypadku [0,1,4] można sprawdzić, czy następna lista powinna być [0,2,3]. Pętla zatrzymuje się w położeniu 1, kolejny kod

indices[i] += 1 

zwiększa wartość dla indeces[i] (1 -> 2). Wreszcie

for j in range(i+1, r): 
    indices[j] = indices[j-1] + 1 

resetuje wszystkie pozycji > i do najmniejszych wartościach indeksu prawnymi, każdy 1 większe niż jego poprzednik.

Answer 2

Ta pętla jest prosta: sprawdza, czy algorytm powinien zakończyć się na.

Początek algorytm z pierwszych r przedmiotów i wzrasta aż osiągnie ostatnie r przedmioty w iterable, które są [Sn-r+1 ... Sn-1, Sn] (jeśli pozwolimy S być iterable).

Teraz, algorytm skanuje każdy element w indeksach, i upewnić się, że wciąż mają gdzie pójść - tak to weryfikuje indice i th jest nie indeks n - r + i, który w poprzednim ustępie, jest (ignorujemy 1 tutaj, ponieważ listy są oparte na 0).

Jeśli wszystkie te wskaźniki są równe ostatnim pozycjom r - wówczas przechodzi do else, zatwierdzając return i kończąc algorytm.

---

Moglibyśmy stworzyć taką samą funkcjonalność za pomocą

if indices == list(range(n-r, n)): return 

ale główny powód tego „bałaganu” (używając reverse i break) jest to, że pierwszy indeks od końca, że ​​nie pasuje jest zapisany wewnątrz i i jest używany do następnego poziomu algorytmu, który zwiększa ten indeks i dba o ponowne ustawienie reszty.

---

Można to sprawdzić poprzez zastąpienie yield S z

print('Combination: {} Indices: {}'.format(tuple(pool[i] for i in indices), indices)) 

Answer 3

Source code ma dodatkowe informacje o tym, co się dzieje.

Oświadczenie yeild przed while pętla powraca trywialny kombinację elementów (co jest po prostu pierwsze r elementy A, (A[0], ..., A[r-1])) i przygotowuje indices do przyszłej pracy. Załóżmy, że mamy A='ABCDE' i r=3. Następnie po pierwszym kroku wartość indices wynosi [0, 1, 2], co wskazuje na ('A', 'B', 'C'). wygląd

Miejmy na kodzie źródłowym pętli w pytaniu:

2160   /* Scan indices right-to-left until finding one that is not 
2161    at its maximum (i + n - r). */ 
2162   for (i=r-1 ; i >= 0 && indices[i] == i+n-r ; i--) 
2163    ; 

wyszukiwania Ta pętla do skrajnego prawego elementu indices które nie osiągnęło jeszcze wartość maksymalną. Po pierwszym oświadczeniu yield wartość indices to [0, 1, 2]. Dlatego pętla for kończy się na indices[2].

Następny poniższy kod zwiększa ty element i z indices:

2170   /* Increment the current index which we know is not at its 
2171    maximum. Then move back to the right setting each index 
2172    to its lowest possible value (one higher than the index 
2173    to its left -- this maintains the sort order invariant). */ 
2174   indices[i]++; 

W rezultacie otrzymujemy połączenie indeksu [0, 1, 3], co wskazuje na ('A', 'B', 'D').

Następnie cofnąć kolejnych indeksów, które są zbyt duże:

2175   for (j=i+1 ; j<r ; j++) 
2176    indices[j] = indices[j-1] + 1; 

Wskaźniki zwiększać krok po kroku:

indeksów krok

1. (0, 1, 2)
2. (0, 1, 3)
3. (0, 1, 4)
4. (0, 2, 3)
5. (0, 2, 4)
6. (0, 3, 4)
7. (1, 2, 3) ...