Das Problem des Münzwechsels ist sehr gut dokumentiert. In Anbetracht einer unendlichen Vorrat an Münzen von Konfessionen x_1zu x_mmüssen Sie die Anzahl von Kombinationen zu finden , die summieren sich zu y. Zum Beispiel gegeben x = {1,2,3}und y = 4wir haben vier Kombinationen:

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

Einführung

Es gibt verschiedene Varianten des Münzwechselproblems. In dieser Variante gibt es zwei zusätzliche Einschränkungen:

1. Jede Stückelung muss mindestens einmal verwendet werden.
2. Insgesamt muss genau eine feste Anzahl von Münzen verwendet werden.

Zum Beispiel gegeben x = {1,2,3}, y = 36und n = 15wo ndie Gesamtzahl der Münzen ist , die verwendet werden müssen, erhalten wir vier Kombinationen:

1. {1,2,2,2,2,2,2,2,3,3,3,3,3,3,3} (1 Einsen, 7 Zweien, 7 Dreien)
2. {1,1,2,2,2,2,2,3,3,3,3,3,3,3,3} (2 Einsen, 5 Zweien, 8 Dreien)
3. {1,1,1,2,2,2,3,3,3,3,3,3,3,3,3} (3 Einsen, 3 Zweien, 9 Dreien)
4. {1,1,1,1,2,3,3,3,3,3,3,3,3,3,3} (4 Einsen, 1 Zweien, 10 Dreien)

Herausforderung

Die Herausforderung besteht darin, eine Funktion enumeratein der Sprache Ihrer Wahl zu schreiben, die alle oben beschriebenen Kombinationen auflistet:

1. Die Liste der Stückelungen. Zum Beispiel {1,5,10,25}. Sie können entweder Listen oder Arrays verwenden.
2. Eine nicht negative Ganzzahl y, die die Summe aller Kombinationen angibt.
3. Eine nicht negative Ganzzahl n, die die Gesamtzahl der Münzen angibt.

Die Reihenfolge der Argumente spielt keine Rolle. Punktfreie Funktionen sind erlaubt.

Die Ausgabe der enumerateFunktion muss eine Liste von Kombinationen sein. Jede Kombination muss eindeutig sein und eine Liste von nganzen Zahlen enthalten, die sich addieren y. Jede Stückelung muss in jeder Kombination mindestens einmal vorkommen und es darf keine Kombination fehlen. Die Reihenfolge der ganzen Zahlen und der Kombinationen spielt keine Rolle. Sie können entweder Listen oder Arrays für die Ausgabe verwenden.

Beachten Sie die folgenden Randfälle:

1. Wenn beide yund nNull sind und die Liste der Nennwerte leer ist, ist die Ausgabe eine Liste mit einer Kombination, der leeren Kombination (dh {{}}).
2. Wenn andernfalls yNull nist, Null ist oder die Liste der Nennwerte leer ist, ist die Ausgabe eine Liste von Nullkombinationen (dh {}).
3. Im Allgemeinen yist ndie Ausgabe eine Liste von Nullkombinationen , wenn sie kleiner als die Summe der Nennwerte oder kleiner als die Anzahl der Nennwerte ist.

Die Bewertung basiert auf der Größe des gesamten Programms in Byte. Beachten Sie, dass dies die enumerateFunktion, Hilfsfunktionen, Importanweisungen usw. umfasst. Testfälle sind nicht enthalten.

05AB1E, 20 Bytes

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

Die Eingabe erfolgt in der Reihenfolge: list of values, nr of coins, sum to reach.

Erklärung kurz

1. Holen Sie sich alle Permutationen der Münzliste der Länge: final length - length of unique coin list
2. Fügen Sie die Liste der eindeutigen Münzen zu diesen Listen hinzu.
3. Wenn die Summe der gesuchten Summe entspricht, speichern Sie die Liste
4. Alle gespeicherten Listen ausgeben

Probieren Sie es online aus

Der Online-Compiler kann keine große Anzahl von Münzen verarbeiten.

MATL , 22 Bytes

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

Die Eingabereihenfolge ist: Reihe von Nennwerten, Anzahl der entnommenen Münzen ( n), gewünschte Summe ( y).

Jede Kombination wird in einer anderen Zeile angezeigt. Leere Ausgabe wird als leere Zeichenfolge angezeigt (also nichts).

Probieren Sie es online!

Dem Code im Online-Compiler für das Beispiel in der Challenge fehlt der Speicher, aber er funktioniert offline mit einem Standardcomputer, der recht modern ist:

>> 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

Erläuterung

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 Bytes

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

Eine anonyme Funktion, die die Eingabe eines Tupels von Nennwerten des Formulars (x_1, x_2, x_3 ... , x_k), eines Zielwerts und einer Anzahl von Münzen über ein Argument akzeptiert und eine Liste von Tupeln des Formulars zurückgibt [(solution_1), (solution_2), (solution_3), ... (solution_k)].

Wie es funktioniert

ItertoolsDie combinations_with_replacementFunktion von wird verwendet, um alle l-len(d)Kombinationen mit Ersetzung der Nennwerte zu generieren . Durch das Anhängen dan jede dieser Kombinationen wird garantiert, dass jeder Nennwert mindestens einmal vorkommt und dass die neue Kombination eine Länge hat l. Wenn sich die Elemente einer Kombination zu summieren, twird die Kombination als Tupel zur Rückgabeliste hinzugefügt.

Probieren Sie es auf Ideone

Eine alternative Methode für 108 Bytes

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)

Eine anonyme Funktion, die die Eingabe eines Tupels von Nennwerten des Formulars (x_1, x_2, x_3 ... , x_k), eines Zielwerts und einer Anzahl von Münzen über ein Argument akzeptiert und eine Reihe von Tupeln des Formulars zurückgibt {(solution_1), (solution_2), (solution_3), ... (solution_k)}.

Wie es funktioniert (andere Version)

Hierbei wird die productFunktion from verwendet itertools, um alle l-len(d)Anordnungen der Nennwerte zu generieren . Durch das Anhängen dan jede dieser Kombinationen wird garantiert, dass jeder Nennwert mindestens einmal vorkommt und dass die neue Kombination eine Länge hat l. Wenn sich die Elemente einer Kombination zu summieren, twird die Kombination sortiert, von einer Liste in ein Tupel konvertiert und zu den Rückgabetupeln hinzugefügt. Schließlich setentfernt das Aufrufen alle Duplikate.

Probieren Sie es auf Ideone (andere Version)

JavaScript (ES6), 135 Byte

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)