Jak skutecznie iterować kombinacje tablic ze stałą sumą?

Question

Mam tablicę, a jej długość to X. Każdy element tablicy ma zakres 1 .. L. Chcę efektywnie iterować poprzez wszystkie kombinacje tablic, które mają sumę L.

Prawidłowe rozwiązania dla L = 4, a X = 2

1 3 
3 1 
2 2 

Prawidłowe rozwiązania dla L = 5 i X = 3

1 1 3 
1 3 1 
3 1 1 
1 2 2 
2 1 2 
2 2 1 

Naiwne wykonania jest (nic dziwnego) zbyt wolno dla mojego problemu (X ma maksymalnie 8 w moim przypadku, a L ma nawet 128).

Czy ktoś może mi powiedzieć, w jaki sposób jest wywoływany ten problem lub gdzie znaleźć szybki algorytm dla problemu?

Dzięki!

Answer 1

Jeśli dobrze rozumiem, masz podane dwa numery 1 ≤ X ≤ L i chcesz wygenerować wszystkie sekwencje liczb całkowitych dodatnich o długości X że suma L.

(Uwaga: to jest podobne do integer partition problem, ale nie to samo, ponieważ uważamy, że 1,2,2 jest inną sekwencją niż 2,1,2, natomiast w przypadku problemu z partycją całkowitą ignorujemy kolejność, tak, że są one uważane za takie same partycja)

sekwencje którego szukasz odpowiadają combinations z X. - 1 pozycji z L - 1. w przypadku, jeśli stawiamy numery 1 do L - 1 w kolejności i wybierz X - 1 z nich, a następnie długości przerw między wybranymi liczby są liczbami całkowitymi dodatnimi, które sumują się do L.

Na przykład załóżmy, że L jest 16 i X jest 5. Następnie wybierz 4 numery od 1 do 15 włącznie:

Dodaj 0 na początku i na końcu 16 i interwały:

i 3 + 4 + 1 + 6 + 2 = 16 według potrzeby.

Więc generate the combinations z X - 1 elementów z L - 1, a dla każdego z nich, przekształcić go na partycji poprzez znalezienie interwały. Na przykład w Pythonie można napisać:

from itertools import combinations 

def partitions(n, t): 
    """ 
    Generate the sequences of `n` positive integers that sum to `t`. 
    """ 
    assert(1 <= n <= t) 
    def intervals(c): 
     last = 0 
     for i in c: 
      yield i - last 
      last = i 
     yield t - last 
    for c in combinations(range(1, t), n - 1): 
     yield tuple(intervals(c)) 

>>> list(partitions(2, 4)) 
[(1, 3), (2, 2), (3, 1)] 
>>> list(partitions(3, 5)) 
[(1, 1, 3), (1, 2, 2), (1, 3, 1), (2, 1, 2), (2, 2, 1), (3, 1, 1)] 

Istnieje (L - 1)!/(X - 1)! (L - X)!kombinacje X - 1 pozycji z L - 1, więc środowisko wykonawcze tego algorytmu (i rozmiar jego wyjścia) jest wykładnicze w L. Jeśli jednak nie policzysz wyjścia, potrzebujesz tylko przestrzeni O (L).

Z L = 128 i X = 8, istnieją 89,356,415,775 przegródki, więc zajmie to trochę czasu na wyjście nimi wszystkimi!

(Może jeśli wyjaśnić, dlaczego obliczanie tych partycji, możemy być w stanie zaproponować jakiś sposób spełnienia wymagań, bez konieczności rzeczywiście produkują je wszystkie.)