Problemem zmiana moneta jest bardzo dobrze udokumentowane. Biorąc pod uwagę nieskończoną dostaw nominałów monet x_1do x_mtrzeba znaleźć liczbę kombinacji, które dodają do y. Na przykład podane x = {1,2,3}i y = 4mamy cztery kombinacje:

1. {1,1,1,1}
2. {1,1,2}
3. {1,3}
4. {2,2}

Wprowadzenie

Istnieje kilka odmian problemu zmiany monety. W tej odmianie mamy dwa dodatkowe ograniczenia:

1. Każdy nominał musi być użyty co najmniej raz.
2. W sumie należy użyć dokładnie określonej liczby monet.

Na przykład, biorąc pod uwagę x = {1,2,3}, y = 36a n = 15gdzie njest to łączna liczba monet, które muszą być stosowane, otrzymujemy cztery kombinacje:

1. {1,2,2,2,2,2,2,2,3,3,3,3,3,3,3} (1 jedynki, 7 dwójek, 7 trójek)
2. {1,1,2,2,2,2,2,3,3,3,3,3,3,3,3} (2 jedynki, 5 dwójek, 8 trójek)
3. {1,1,1,2,2,2,3,3,3,3,3,3,3,3,3} (3 jedynki, 3 dwójki, 9 trójek)
4. {1,1,1,1,2,3,3,3,3,3,3,3,3,3,3} (4 jedynki, 1 dwójka, 10 trójek)

Wyzwanie

Wyzwanie polega na napisaniu funkcji enumeratew wybranym języku, która wylicza wszystkie kombinacje zgodnie z powyższym opisem:

1. Lista nominałów. Na przykład {1,5,10,25}. Możesz użyć list lub tablic.
2. Nieujemna liczba całkowita yoznaczająca sumę każdej kombinacji.
3. Nieujemna liczba całkowita noznaczająca całkowitą liczbę monet.

Kolejność argumentów nie ma znaczenia. Funkcje pointfree są dozwolone.

Dane wyjściowe enumeratefunkcji musi być listą kombinacji. Każda kombinacja musi być unikalna i musi być listą nliczb całkowitych, które się sumują y. Każdy nominał musi pojawić się co najmniej raz w każdej kombinacji i nie może zabraknąć żadnej kombinacji. Kolejność liczb całkowitych i kombinacji nie ma znaczenia. Do danych wyjściowych można użyć list lub tablic.

Należy pamiętać o następujących przypadkach krawędzi:

1. Jeśli oba yi nsą zerowe, a lista nominałów jest pusty, to wyjście jest lista jednej kombinacji, pusty połączenie (tj {{}}).
2. W przeciwnym razie, jeśli ywynosi zero, noznacza zero lub lista nominałów jest pusta, wówczas wynikiem jest lista zerowych kombinacji (tj {}.).
3. Mówiąc bardziej ogólnie, jeśli yjest mniejsza niż suma nominałów lub njest mniejsza niż liczba nominałów, wówczas wynikiem jest lista zerowych kombinacji.

Punktacja będzie oparta na wielkości całego programu w bajtach. Pamiętaj, że obejmuje to enumeratefunkcję, funkcje pomocnicze, instrukcje importu itp. Nie obejmuje przypadków testowych.

05AB1E, 20 bajtów

g-¹sã€{Ùvy¹«DO³Qiˆ}¯

Wejście znajduje się w kolejności: list of values, nr of coins, sum to reach.

Wyjaśnienie w skrócie

1. Uzyskaj wszystkie permutacje z listy monet długości: final length - length of unique coin list
2. Dodaj listę unikalnych monet do tych list.
3. Jeśli suma jest równa kwocie poszukiwanej, zapisz listę
4. Wydrukuj wszystkie zapisane listy

Wypróbuj online

Internetowy kompilator nie obsługuje dużej liczby monet.

MATL , 22 bajty

Z^!S!Xu!tsi=Z)"1G@m?@!

Kolejność wprowadzania to: tablica nominałów, liczba pobranych monet ( n), żądana suma ( y).

Każda kombinacja jest wyświetlana w innym wierszu. Pusty wynik jest wyświetlany jako pusty ciąg (więc nic).

Wypróbuj online!

W kompilatorze internetowym zabrakło pamięci na przykład w wyzwaniu, ale działa w trybie offline ze standardowym, dość nowoczesnym komputerem:

>> matl
 > Z^!S!Xu!tsi=Z)"1G@m?@!
 > 
> [1 2 3]
> 15
> 36
1 1 1 1 2 3 3 3 3 3 3 3 3 3 3
1 1 1 2 2 2 3 3 3 3 3 3 3 3 3
1 1 2 2 2 2 2 3 3 3 3 3 3 3 3
1 2 2 2 2 2 2 2 3 3 3 3 3 3 3

Wyjaśnienie

Z^      % Implicitly input array of denomminations and number of coins n. Compute 
        % Cartesian power. This gives 2D array with each "combination"
        % on a different row
!S!     % Sort each row
Xu      % Deduplicate rows
!       % Transpose: rows become columns. Call this array A
ts      % Push a copy, compute sum of each column
i       % Input y (desired sum)
=       % Logical array that contains true if the "combination" has the desired sum
Z)      % Keep only those columns in array A
"       % For each column
  1G    %   Push array of denominations again
  @     %   Push current column
  m     %   Is each denomination present in the column?
  ?     %   If so
    @!  %     Push current column again. Transpose into a row
        %   End if
        % End for
        % Implicitly display stack contents

Python 3, 120 106 bajtów

from itertools import*
lambda d,t,l:[i+d for i in combinations_with_replacement(d,l-len(d))if sum(i+d)==t]

Anonimowa funkcja, która pobiera argument liczby krotek nominałów formy (x_1, x_2, x_3 ... , x_k), wartości docelowej i liczby monet, i zwraca listę krotek formularza [(solution_1), (solution_2), (solution_3), ... (solution_k)].

Jak to działa

Itertools„s combinations_with_replacementfunkcja jest stosowana w celu wytworzenia wszystkich l-len(d)kombinacji, zastępując nominałów. Dołączając ddo każdej z tych kombinacji, gwarantuje się, że każdy nominał pojawia się co najmniej raz, a nowa kombinacja ma długość l. Jeśli elementy kombinacji sumują się t, kombinacja jest dodawana do listy zwrotnej jako krotka.

Wypróbuj na Ideone

Alternatywna metoda dla 108 bajtów

from itertools import*
lambda d,t,l:set(tuple(sorted(i+d))for i in product(d,repeat=l-len(d))if sum(i+d)==t)

Anonimowa funkcja, która pobiera (x_1, x_2, x_3 ... , x_k)za pomocą argumentu krotkę nominałów formy , wartość docelową i liczbę monet i zwraca zestaw krotek formularza {(solution_1), (solution_2), (solution_3), ... (solution_k)}.

Jak to działa (inna wersja)

Ta productfunkcja wykorzystuje itertoolsdo generowania wszystkich l-len(d)układów nominałów. Dołączając ddo każdej z tych kombinacji, gwarantuje się, że każdy nominał pojawia się co najmniej raz, a nowa kombinacja ma długość l. Jeśli elementy kombinacji sumują się t, kombinacja jest sortowana, konwertowana z listy na krotkę i dodawana do krotek zwracanych. Wreszcie wywołanie setusuwa wszelkie duplikaty.

Wypróbuj na Ideone (inna wersja)

JavaScript (ES6), 135 bajtów

g=(a,n,y,r)=>n>0?y>0&&a.map((x,i)=>g(a.slice(i),n-1,y-x,[...r,x])):n|y||console.log(r)
(a,n,y)=>g(a,n-a.length,a.reduce((y,x)=>y-x,y),a)