Jak poszedłbyś przetestować wszystkie możliwe kombinacje dodatków z danego zestawu N
liczb, aby sumowały się one do podanej liczby końcowej?
Krótki przykład:
- Zestaw liczb do dodania:
N = {1,5,22,15,0,...}
- Pożądany rezultat:
12345
Jak poszedłbyś przetestować wszystkie możliwe kombinacje dodatków z danego zestawu N
liczb, aby sumowały się one do podanej liczby końcowej?
Krótki przykład:
N = {1,5,22,15,0,...}
12345
Odpowiedzi:
Problem ten można rozwiązać za pomocą rekurencyjnych kombinacji wszystkich możliwych kwot odfiltrowujących te, które osiągają cel. Oto algorytm w Pythonie:
Tego rodzaju algorytmy są bardzo dobrze wyjaśnione w następującym wykładzie Standford's Abstract Programming - ten film jest bardzo godny polecenia, aby zrozumieć, jak rekurencja działa w celu generowania permutacji rozwiązań.
Edytować
Powyżej jako funkcja generatora, dzięki czemu jest nieco bardziej przydatna. Wymaga Python 3.3+ z powodu
yield from
.Oto wersja Java tego samego algorytmu:
To jest dokładnie ta sama heurystyka. Moja Java jest trochę zardzewiała, ale myślę, że jest łatwa do zrozumienia.
Konwersja C # rozwiązania Java: (autor: @JeremyThompson)
Rozwiązanie Ruby: (autor @emaillenin)
Edycja: dyskusja złożoności
Jak wspominają inni, jest to trudny problem NP . Można go rozwiązać w czasie wykładniczym O (2 ^ n), na przykład dla n = 10 będzie 1024 możliwych rozwiązań. Jeśli cele, które próbujesz osiągnąć, znajdują się w niskim zakresie, algorytm działa. Na przykład:
subset_sum([1,2,3,4,5,6,7,8,9,10],100000)
generuje 1024 gałęzie, ponieważ cel nigdy nie odfiltruje możliwych rozwiązań.Z drugiej strony
subset_sum([1,2,3,4,5,6,7,8,9,10],10)
generuje tylko 175 gałęzi, ponieważ cel do osiągnięcia10
pozwala odfiltrować wiele kombinacji.Jeśli
N
iTarget
są dużymi liczbami, należy przejść do przybliżonej wersji rozwiązania.źródło
[1, 2, 0, 6, -3, 3], 3
- wyświetla tylko[1,2], [0,3], [3]
przy brakujących przypadkach, takich jak[6, -3, 3]
[1, 2, 5], 5
tylko wyjść[5]
, kiedy[1, 1, 1, 1, 1]
,[2, 2, 1]
i[2, 1, 1, 1]
są rozwiązaniami.i+1
inremaining = numbers[i+1:]
. Wygląda na to, że ten algorytm nie zezwala na duplikaty.[1, 1, 3]
spojrzeć na stackoverflow.com/a/34971783/3684296 (Python)Rozwiązanie tego problemu podano milion razy w Internecie. Problem nazywa się Problem zmiany monety . Rozwiązania można znaleźć na stronie http://rosettacode.org/wiki/Count_the_coins, a jej matematyczny model na stronie http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf (lub zmiana monety Google problem ).
Nawiasem mówiąc, interesujące jest rozwiązanie Scala firmy Tsagadai. Ten przykład daje 1 lub 0. Jako efekt uboczny, wypisuje na konsoli wszystkie możliwe rozwiązania. Wyświetla rozwiązanie, ale nie udaje się go w żaden sposób wykorzystać.
Aby być jak najbardziej użytecznym, kod powinien zwrócić a
List[List[Int]]
, aby umożliwić uzyskanie liczby rozwiązań (długość listy list), „najlepszego” rozwiązania (najkrótsza lista) lub wszystkich możliwych rozwiązań.Oto przykład. Jest bardzo nieefektywny, ale łatwo go zrozumieć.
Po uruchomieniu wyświetla:
sumCombinations()
Funkcja może być stosowany sam, a wynik może być dalej analizowane w celu wyświetlenia „najlepsze” rozwiązanie (najkrótsza listy) lub szereg rozwiązań (liczbie List).Pamiętaj, że nawet w ten sposób wymagania mogą nie być w pełni spełnione. Może się zdarzyć, że kolejność każdej listy w rozwiązaniu będzie znacząca. W takim przypadku każda lista musiałaby zostać zduplikowana tyle razy, ile jest kombinacji jej elementów. Lub możemy być zainteresowani tylko różnymi kombinacjami.
Na przykład możemy rozważyć, że
List(5, 10)
powinny dać dwie kombinacje:List(5, 10)
iList(10, 5)
. NaList(5, 5, 5)
to może dać trzy kombinacje czy tylko jeden, w zależności od wymagań. W przypadku liczb całkowitych trzy permutacje są równoważne, ale jeśli mamy do czynienia z monetami, jak w przypadku „problemu wymiany monet”, nie są.W wymaganiach nie podano również, czy każdy numer (lub moneta) może być użyty tylko raz, czy wiele razy. Możemy (i powinniśmy!) Uogólnić problem na listę list występowania każdej liczby. Przekłada się to w rzeczywistości na „jakie są możliwe sposoby zarabiania pewnej ilości pieniędzy za pomocą zestawu monet (a nie zestawu wartości monet)”. Pierwotny problem to tylko szczególny przypadek tego przypadku, w którym mamy tyle wystąpień każdej monety, ile potrzeba, aby uzyskać całkowitą kwotę przy każdej wartości monety.
źródło
W Haskell :
I J :
Jak możesz zauważyć, obaj zastosuj to samo podejście i podziel problem na dwie części: wygeneruj każdy element zestawu mocy i sprawdź sumę każdego elementu do celu.
Istnieją inne rozwiązania, ale jest to najprostsze.
Czy potrzebujesz pomocy z jednym z nich lub szukasz innego podejścia?
źródło
not in scope: 'subsequences'
jakieś wskazówki?import Data.List
Wersja Javascript:
źródło
remaining = numbers.slice();
remaining.slice(i + 1);
przeciwnym razie należynumbers.slice(i + 1);
zmienić tablicę liczbslice
zwraca (płytką) kopię, nie modyfikujenumbers
tablicy.Wersja C ++ tego samego algorytmu
źródło
Wersja C # odpowiedzi na kod @msalvadores
źródło
Myślałem, że skorzystam z odpowiedzi na to pytanie, ale nie mogłem, więc oto moja odpowiedź. Wykorzystuje zmodyfikowaną wersję odpowiedzi w Strukturze i interpretacji programów komputerowych . Myślę, że jest to lepsze rozwiązanie rekurencyjne i powinno bardziej zadowolić purystów.
Moja odpowiedź jest w Scali (i przepraszam, jeśli moja Scala jest do bani, właśnie zaczęłam się uczyć). FindSumCombinations szaleństwo jest do rodzaju i niepowtarzalny oryginalnej listy do rekursji do uniknięcia powtórzeń.
Aby go użyć:
źródło
przekonwertowałem powyższą logikę z Pythona na php ..
źródło
Innym rozwiązaniem Pythona byłoby użycie
itertools.combinations
modułu w następujący sposób:Wynik:
[(8, 7), (5, 10), (3, 8, 4), (3, 5, 7)]
źródło
Oto rozwiązanie w R.
źródło
subset_sum(numbers = c(1:2), target = 5)
zwraca"sum(1+2+2)=5"
. Brakuje jednak kombinacji 1 + 1 + 1 + 1 + 1. W ustawianiu celów na wyższe liczby (np. 20) brakuje jeszcze większej liczby kombinacji.subset_sum(1:2, 4)
nie powinien zwracać żadnych rozwiązań, ponieważ nie ma kombinacji 1 i 2, która dodaje do 4. To, co należy dodać do mojej funkcji, to ucieczka, jeślii
jest większa niż długośćnumbers
Oto wersja Java, która dobrze nadaje się do małej N i bardzo dużej sumy docelowej, gdy złożoność
O(t*N)
(rozwiązanie dynamiczne) jest większa niż algorytm wykładniczy. Moja wersja wykorzystuje spotkanie w środkowym ataku, wraz z niewielkim przesunięciem w celu zmniejszenia złożoności z klasycznego naiwnegoO(n*2^n)
doO(2^(n/2))
.Jeśli chcesz użyć tego dla zestawów zawierających od 32 do 64 elementów, powinieneś zmienić ten,
int
który reprezentuje bieżący podzbiór w funkcji kroku, nalong
chociaż wydajność wyraźnie drastycznie spadnie wraz ze wzrostem rozmiaru zestawu. Jeśli chcesz użyć tego dla zestawu z nieparzystą liczbą elementów, powinieneś dodać 0 do zestawu, aby był parzysty.źródło
Jest to podobne do problemu wymiany monet
źródło
Bardzo wydajny algorytm wykorzystujący tabele napisane kilka lat temu w c ++.
Jeśli ustawisz DRUKUJ 1, wydrukuje wszystkie kombinacje (ale nie będzie to efektywna metoda).
Jest tak wydajny, że oblicza ponad 10 ^ 14 kombinacji w czasie krótszym niż 10ms.
źródło
Wersja Excel VBA poniżej. Musiałem zaimplementować to w VBA (nie moje preferencje, nie oceniaj mnie!) I wykorzystałem odpowiedzi z tej strony do tego podejścia. Przesyłam na wypadek, gdyby inni również potrzebowali wersji VBA.
Dane wyjściowe (zapisane w oknie natychmiastowym) powinny wynosić:
źródło
Oto lepsza wersja z lepszym formatowaniem wyjściowym i funkcjami C ++ 11:
źródło
Nierekurencyjna wersja Java, która po prostu dodaje elementy i redystrybuuje je wśród możliwych wartości.
0
są ignorowane i działają na ustalonych listach (możesz się nimi bawić) lub na liście powtarzalnych liczb.Przykładowe dane wejściowe:
Przykładowe dane wyjściowe:
źródło
Aby znaleźć kombinacje za pomocą programu Excel - (jest dość łatwe). (Twój komputer nie może być zbyt wolny)
Pobierz plik Excel „Sum to Target”.
Postępuj zgodnie ze wskazówkami na stronie internetowej.
mam nadzieję że to pomoże.
źródło
Szybka konwersja rozwiązania Java: (autor: @JeremyThompson)
stosowanie:
źródło
Można to również wykorzystać do wydrukowania wszystkich odpowiedzi
Złożoność czasu ma charakter wykładniczy. Rząd 2 ^ n
źródło
Robiłem coś podobnego do zadania Scala. Pomysł opublikowania mojego rozwiązania tutaj:
źródło
Przeniesiłem próbkę C # do Objective-c i nie widziałem jej w odpowiedziach:
źródło
Odpowiedź KeithBellera z nieznacznie zmienionymi nazwami zmiennych i kilkoma komentarzami.
źródło
Wersja PHP , inspirowana wersją C # Keitha Bellera.
Wersja PHP bala dla mnie nie działała, ponieważ nie musiałem grupować numerów. Chciałem prostszej implementacji z jedną wartością docelową i pulą liczb. Ta funkcja również przycina wszelkie zduplikowane wpisy.
źródło
Zalecane jako odpowiedź:
Oto rozwiązanie wykorzystujące generatory es2015 :
Korzystanie z generatorów może być bardzo przydatne, ponieważ umożliwia wstrzymanie wykonywania skryptu natychmiast po znalezieniu prawidłowego podzbioru. Jest to sprzeczne z rozwiązaniami bez generatorów (tj. Bez stanu), które muszą iterować przez każdy pojedynczy podzbiór
numbers
źródło
Po pierwsze odejmij 0. Zero jest identyfikatorem do dodania, więc w tym konkretnym przypadku jest bezużyteczne przez prawa monoidów. Odejmij także liczby ujemne, jeśli chcesz wspiąć się na liczbę dodatnią. W przeciwnym razie potrzebujesz również operacji odejmowania.
Więc ... najszybszy algorytm, jaki można uzyskać w tym konkretnym zadaniu, jest następujący w JS.
Jest to bardzo szybki algorytm, ale jeśli posortujesz
data
tablicę malejącą , będzie to jeszcze szybsze. Używanie.sort()
jest nieznaczne, ponieważ algorytm zakończy się znacznie mniej rekurencyjnymi wywołaniami.źródło
Wersja Perla (wiodąca odpowiedź):
Wynik:
Wersja Javascript:
Jednoliniowy skrypt Javascript, który faktycznie zwraca wyniki (zamiast go drukować):
I mój ulubiony, liniowiec z oddzwanianiem:
źródło
Jest to dynamiczne rozwiązanie dla JS, które informuje, w jaki sposób każdy może uzyskać określoną sumę. To może być właściwe rozwiązanie, jeśli myślisz o złożoności czasu i przestrzeni.
źródło
źródło
Nie podobało mi się rozwiązanie JavaScript. Widziałem, dlaczego buduję jeden dla siebie, stosując częściowe stosowanie, zamykanie i rekurencję:
Ok, głównie martwiłem się, czy tablica kombinacji może spełnić docelowy wymóg, ale dzięki temu podejściu możesz zacząć znajdować resztę kombinacji
Tutaj wystarczy ustawić cel i przekazać tablicę kombinacji.
aktualnie wdrażane przeze mnie rozwiązanie
źródło