Count the coins/0-1: Difference between revisions

=={{header|Mathematica}}/{{header|Wolfram Language}}==

<lang Mathematica>ClearAll[CoinSums]

CoinSums[coins_List, sum_] := Module[{c, len, max, bin, sel, out},

c = {Range[Length[coins]], coins} // Transpose;

c = Select[c, Last /* LessEqualThan[sum]];

len = Length[c];

max = 2^len - 1;

out = Reap@Do[

bin = IntegerDigits[i, 2, len];

sel = Pick[c, bin, 1];

If[Total[sel[[All, 2]]] == sum,

Sow@<|"Coins" -> sel[[All, 2]],

"Indices" -> sel[[All, 1]]|>

]

,

{i, 0, max}

];

out = out[[2, 1]];

Print[Length@out];

out

]

CoinSums[{1, 2, 3, 4, 5}, 6]

CoinSums[{1, 1, 2, 3, 3, 4, 5}, 6]

CoinSums[{1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100}, 40] // Take[#, UpTo[10]] &</lang>

{{out}}

Note that the indexing is 1-based and that for the last case only the first 10 solutions are shown:

<pre>3

{<|Coins->{2,4},Indices->{2,4}|>,<|Coins->{1,5},Indices->{1,5}|>,<|Coins->{1,2,3},Indices->{1,2,3}|>}

9

{<|Coins->{3,3},Indices->{4,5}|>,<|Coins->{2,4},Indices->{3,6}|>,<|Coins->{1,5},Indices->{2,7}|>,<|Coins->{1,2,3},Indices->{2,3,5}|>,<|Coins->{1,2,3},Indices->{2,3,4}|>,<|Coins->{1,5},Indices->{1,7}|>,<|Coins->{1,2,3},Indices->{1,3,5}|>,<|Coins->{1,2,3},Indices->{1,3,4}|>,<|Coins->{1,1,4},Indices->{1,2,6}|>}

464

{<|Coins->{10,10,10,10},Indices->{11,12,13,14}|>,<|Coins->{15,25},Indices->{10,15}|>,<|Coins->{15,25},Indices->{9,15}|>,<|Coins->{15,15,10},Indices->{9,10,14}|>,<|Coins->{15,15,10},Indices->{9,10,13}|>,<|Coins->{15,15,10},Indices->{9,10,12}|>,<|Coins->{15,15,10},Indices->{9,10,11}|>,<|Coins->{5,10,25},Indices->{8,14,15}|>,<|Coins->{5,10,25},Indices->{8,13,15}|>,<|Coins->{5,10,25},Indices->{8,12,15}|>}</pre>