Count the coins/0-1: Difference between revisions
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
|||
(9 intermediate revisions by 6 users not shown) | |||
Line 26: | Line 26: | ||
* Show an example of coins you used to reach the given sum and their indices. See Raku for this case. |
* Show an example of coins you used to reach the given sum and their indices. See Raku for this case. |
||
=={{header|11l}}== |
|||
{{trans|Nim}} |
|||
<syntaxhighlight lang="11l">T Solver |
|||
Int want, width |
|||
count1 = 0 |
|||
count2 = 0 |
|||
F (want, width) |
|||
.want = want |
|||
.width = width |
|||
F count(Int sum; [Int] used, have, uindices, rindices) -> Void |
|||
I sum == .want |
|||
.count1++ |
|||
.count2 += factorial(used.len) |
|||
I .count1 < 11 |
|||
V uindiceStr = uindices.join(‘ ’).ljust(.width) |
|||
print(‘ indices ’uindiceStr‘ => used ’used.join(‘ ’)) |
|||
E I sum < .want & !have.empty |
|||
V thisCoin = have[0] |
|||
V index = rindices[0] |
|||
V rest = have[1..] |
|||
V new_rindices = rindices[1..] |
|||
.count(sum + thisCoin, used [+] thisCoin, rest, uindices [+] index, new_rindices) |
|||
.count(sum, used, rest, uindices, new_rindices) |
|||
F count_coins(Int want, [Int] &coins, Int width) |
|||
print(‘Sum ’want‘ from coins ’coins.join(‘ ’)) |
|||
V solver = Solver(want, width) |
|||
V rindices = Array(0 .< coins.len) |
|||
solver.count(0, [Int](), coins, [Int](), rindices) |
|||
I solver.count1 > 10 |
|||
print(‘ .......’) |
|||
print(‘ (only the first 10 ways generated are shown)’) |
|||
print(‘Number of ways - order unimportant : ’(solver.count1)‘ (as above)’) |
|||
print(‘Number of ways - order important : ’(solver.count2)" (all perms of above indices)\n") |
|||
count_coins(6, &[1, 2, 3, 4, 5], 5) |
|||
count_coins(6, &[1, 1, 2, 3, 3, 4, 5], 7) |
|||
count_coins(40, &[1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 18)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Sum 6 from coins 1 2 3 4 5 |
|||
indices 0 1 2 => used 1 2 3 |
|||
indices 0 4 => used 1 5 |
|||
indices 1 3 => used 2 4 |
|||
Number of ways - order unimportant : 3 (as above) |
|||
Number of ways - order important : 10 (all perms of above indices) |
|||
Sum 6 from coins 1 1 2 3 3 4 5 |
|||
indices 0 1 5 => used 1 1 4 |
|||
indices 0 2 3 => used 1 2 3 |
|||
indices 0 2 4 => used 1 2 3 |
|||
indices 0 6 => used 1 5 |
|||
indices 1 2 3 => used 1 2 3 |
|||
indices 1 2 4 => used 1 2 3 |
|||
indices 1 6 => used 1 5 |
|||
indices 2 5 => used 2 4 |
|||
indices 3 4 => used 3 3 |
|||
Number of ways - order unimportant : 9 (as above) |
|||
Number of ways - order important : 38 (all perms of above indices) |
|||
Sum 40 from coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100 |
|||
indices 0 1 2 3 4 5 6 7 10 => used 1 2 3 4 5 5 5 5 10 |
|||
indices 0 1 2 3 4 5 6 7 11 => used 1 2 3 4 5 5 5 5 10 |
|||
indices 0 1 2 3 4 5 6 7 12 => used 1 2 3 4 5 5 5 5 10 |
|||
indices 0 1 2 3 4 5 6 7 13 => used 1 2 3 4 5 5 5 5 10 |
|||
indices 0 1 2 3 4 5 6 8 => used 1 2 3 4 5 5 5 15 |
|||
indices 0 1 2 3 4 5 6 9 => used 1 2 3 4 5 5 5 15 |
|||
indices 0 1 2 3 4 5 7 8 => used 1 2 3 4 5 5 5 15 |
|||
indices 0 1 2 3 4 5 7 9 => used 1 2 3 4 5 5 5 15 |
|||
indices 0 1 2 3 4 5 10 11 => used 1 2 3 4 5 5 10 10 |
|||
indices 0 1 2 3 4 5 10 12 => used 1 2 3 4 5 5 10 10 |
|||
....... |
|||
(only the first 10 ways generated are shown) |
|||
Number of ways - order unimportant : 464 (as above) |
|||
Number of ways - order important : 3782932 (all perms of above indices) |
|||
</pre> |
|||
=={{header|ALGOL 68}}== |
|||
{{Trans|Go}}which is{{Trans|Wren}} |
|||
<syntaxhighlight lang="algol68"> |
|||
BEGIN # count the ways of summing coins to a particular number - translation of the Go sample # |
|||
INT countu := 0; # order unimportant # |
|||
INT counti := 0; # order important # |
|||
INT width := 0; # for printing purposes # |
|||
PROC factorial = (INT n )INT: |
|||
BEGIN |
|||
INT prod := 1; |
|||
FOR i FROM 2 TO n DO |
|||
prod *:= i |
|||
OD; |
|||
prod |
|||
END # factorial # ; |
|||
OP LEN = ( []INT a )INT: ( UPB a - LWB a ) + 1; |
|||
OP LEN = ( STRING a )INT: ( UPB a - LWB a ) + 1; |
|||
PROC append = ( []INT a, INT b )[]INT: |
|||
BEGIN |
|||
[ 1 : LEN a + 1 ]INT result; |
|||
result[ 1 : LEN a ] := a; |
|||
result[ LEN a + 1 ] := b; |
|||
result |
|||
END # append # ; |
|||
OP TOSTRING = ( []INT a )STRING: |
|||
BEGIN |
|||
STRING result := "["; |
|||
STRING separator := ""; |
|||
FOR i FROM LWB a TO UPB a DO |
|||
result +:= separator + whole( a[ i ], 0 ); |
|||
separator := " " |
|||
OD; |
|||
result +:= "]" |
|||
END # TOSTRING # ; |
|||
PROC pad = ( STRING a, INT width )STRING: |
|||
IF INT len a = LEN a; len a >= width THEN a ELSE a + ( " " * ( width - len a ) ) FI; |
|||
PROC count = ( INT want, []INT used, INT sum, []INT have, uindices, rindices )VOID: |
|||
IF sum = want THEN |
|||
countu +:= 1; |
|||
counti +:= factorial( LEN used ); |
|||
IF countu < 11 THEN |
|||
STRING uindices str = TOSTRING uindices; |
|||
print( ( " indices ", pad( uindices str, width ), " => used ", TOSTRING used, newline ) ) |
|||
FI |
|||
ELIF sum < want AND LEN have /= 0 THEN |
|||
INT this coin = have[ LWB have ]; |
|||
INT index = rindices[ LWB rindices ]; |
|||
[]INT rest = have[ LWB have + 1 : ]; |
|||
count( want, append( used, this coin ), sum + this coin, rest, |
|||
append( uindices, index ), rindices[ LWB rindices + 1 : ] ); |
|||
count( want, used, sum, rest, uindices, rindices[ LWB rindices + 1 : ] ) |
|||
FI # count # ; |
|||
PROC count coins = ( INT want, []INT coins, INT rqd width )VOID: |
|||
BEGIN |
|||
print( ( "Sum ", whole( want, 0 ), " from coins ", TOSTRING coins, newline ) ); |
|||
countu := 0; |
|||
counti := 0; |
|||
width := rqd width; |
|||
[ 0 : LEN coins - 1 ]INT rindices; |
|||
FOR i FROM LWB rindices TO UPB rindices DO |
|||
rindices[ i ] := i |
|||
OD; |
|||
count( want, []INT(), 0, coins, []INT(), rindices ); |
|||
IF countu > 10 THEN |
|||
print( ( " .......", newline ) ); |
|||
print( ( " (only the first 10 ways generated are shown)", newline ) ) |
|||
FI; |
|||
print( ( "Number of ways - order unimportant : ", whole( countu, 0 ) |
|||
, " (as above)", newline ) ); |
|||
print( ( "Number of ways - order important : ", whole( counti, 0 ) |
|||
, " (all perms of above indices)", newline, newline ) ) |
|||
END # count coins # ; |
|||
BEGIN # task # |
|||
count coins( 6, ( 1, 2, 3, 4, 5 ), 7 ); |
|||
count coins( 6, ( 1, 1, 2, 3, 3, 4, 5 ), 9 ); |
|||
count coins( 40, ( 1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100 ), 20 ) |
|||
END |
|||
END |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Sum 6 from coins [1 2 3 4 5] |
|||
indices [0 1 2] => used [1 2 3] |
|||
indices [0 4] => used [1 5] |
|||
indices [1 3] => used [2 4] |
|||
Number of ways - order unimportant : 3 (as above) |
|||
Number of ways - order important : 10 (all perms of above indices) |
|||
Sum 6 from coins [1 1 2 3 3 4 5] |
|||
indices [0 1 5] => used [1 1 4] |
|||
indices [0 2 3] => used [1 2 3] |
|||
indices [0 2 4] => used [1 2 3] |
|||
indices [0 6] => used [1 5] |
|||
indices [1 2 3] => used [1 2 3] |
|||
indices [1 2 4] => used [1 2 3] |
|||
indices [1 6] => used [1 5] |
|||
indices [2 5] => used [2 4] |
|||
indices [3 4] => used [3 3] |
|||
Number of ways - order unimportant : 9 (as above) |
|||
Number of ways - order important : 38 (all perms of above indices) |
|||
Sum 40 from coins [1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100] |
|||
indices [0 1 2 3 4 5 6 7 10] => used [1 2 3 4 5 5 5 5 10] |
|||
indices [0 1 2 3 4 5 6 7 11] => used [1 2 3 4 5 5 5 5 10] |
|||
indices [0 1 2 3 4 5 6 7 12] => used [1 2 3 4 5 5 5 5 10] |
|||
indices [0 1 2 3 4 5 6 7 13] => used [1 2 3 4 5 5 5 5 10] |
|||
indices [0 1 2 3 4 5 6 8] => used [1 2 3 4 5 5 5 15] |
|||
indices [0 1 2 3 4 5 6 9] => used [1 2 3 4 5 5 5 15] |
|||
indices [0 1 2 3 4 5 7 8] => used [1 2 3 4 5 5 5 15] |
|||
indices [0 1 2 3 4 5 7 9] => used [1 2 3 4 5 5 5 15] |
|||
indices [0 1 2 3 4 5 10 11] => used [1 2 3 4 5 5 10 10] |
|||
indices [0 1 2 3 4 5 10 12] => used [1 2 3 4 5 5 10 10] |
|||
....... |
|||
(only the first 10 ways generated are shown) |
|||
Number of ways - order unimportant : 464 (as above) |
|||
Number of ways - order important : 3782932 (all perms of above indices) |
|||
</pre> |
|||
=={{header|FreeBASIC}}== |
|||
Based on the Phix entry and the Nim entry |
|||
<syntaxhighlight lang="vb">#define factorial(n) Iif(n<2, 1, n*factorial1(n-1)) |
|||
REM silly way |
|||
Function silly(coins() As Short, tgt As Short, cdx As Short = 1) As Integer |
|||
Dim As Integer count = 0 |
|||
If tgt = 0 Then |
|||
count += 1 |
|||
Elseif tgt > 0 And cdx <= Ubound(coins) Then |
|||
count += silly(coins(), tgt-coins(cdx), cdx+1) |
|||
count += silly(coins(), tgt, cdx+1) |
|||
End If |
|||
Return count |
|||
End Function |
|||
REM very silly way |
|||
Function very_silly(coins() As Short, tgt As Short, cdx As Short = 1, taken As Short = 0) As Integer |
|||
Dim As Integer count = 0 |
|||
If tgt = 0 Then |
|||
count += factorial(taken) |
|||
Elseif tgt > 0 And cdx <= Ubound(coins) Then |
|||
count += very_silly(coins(), tgt-coins(cdx), cdx+1, taken+1) |
|||
count += very_silly(coins(), tgt, cdx+1, taken) |
|||
End If |
|||
Return count |
|||
End Function |
|||
Sub countCoins(coins() As Short, tgt As Short) |
|||
Print "Sum"; tgt; " from coins "; |
|||
For a As Short = 1 To Ubound(coins) |
|||
Print coins(a); |
|||
Next a |
|||
Print !"\nNumber of ways - order unimportant:"; silly(coins(), tgt) |
|||
Print "Number of ways - order important :"; very_silly(coins(), tgt); !"\n" |
|||
End Sub |
|||
Dim As Short test0(1 To ...) = {1, 2, 3, 4, 5} |
|||
countCoins(test0(), 6) |
|||
Dim As Short test1(1 To ...) = {1, 1, 2, 3, 3, 4, 5} |
|||
countCoins(test1(), 6) |
|||
Dim As Short test2(1 To ...) = {1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100} |
|||
countCoins(test2(), 40) |
|||
Sleep</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Sum 6 from coins 1 2 3 4 5 |
|||
Number of ways - order unimportant: 3 |
|||
Number of ways - order important : 10 |
|||
Sum 6 from coins 1 1 2 3 3 4 5 |
|||
Number of ways - order unimportant: 9 |
|||
Number of ways - order important : 38 |
|||
Sum 40 from coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100 |
|||
Number of ways - order unimportant: 464 |
|||
Number of ways - order important : 3782932</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 86: | Line 351: | ||
countCoins(6, []int{1, 1, 2, 3, 3, 4, 5}, 9) |
countCoins(6, []int{1, 1, 2, 3, 3, 4, 5}, 9) |
||
countCoins(40, []int{1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100}, 20) |
countCoins(40, []int{1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100}, 20) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 126: | Line 391: | ||
Number of ways - order important : 3782932 (all perms of above indices) |
Number of ways - order important : 3782932 (all perms of above indices) |
||
</pre> |
</pre> |
||
=={{header|J}}== |
|||
Implementation:<syntaxhighlight lang="j">selcoins=: {{ #:I.x=(#:i.2^#y)+/ .*y }} |
|||
ccoins=: {{ (#i), +/!x:+/"1 i=. x selcoins y }}</syntaxhighlight> |
|||
<code>selcoins</code> identifies the valid selections of the coins. <code>ccoins</code> counts them, giving two counts (first is where coin order does not matter, second is where each permutation of physical coins is counted separately). |
|||
Task examples:<syntaxhighlight lang="j"> 6 ccoins 1 2 3 4 5 |
|||
3 10 |
|||
6 ccoins 1 1 2 3 3 4 5 |
|||
9 38 |
|||
40 ccoins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100 |
|||
464 3782932</syntaxhighlight> |
|||
Some example coin selections:<syntaxhighlight lang="j"> rplc&(' 0';'')"1":6 (]#~selcoins) 1 2 3 4 5 |
|||
2 4 |
|||
1 5 |
|||
1 2 3 |
|||
rplc&(' 0';'')"1":6 (]#~selcoins) 1 1 2 3 3 4 5 |
|||
3 3 |
|||
2 4 |
|||
1 5 |
|||
1 2 3 |
|||
1 2 3 |
|||
1 5 |
|||
1 2 3 |
|||
1 2 3 |
|||
1 1 4 |
|||
rplc&(' 0';'')"1":40 (]#~9{.selcoins) 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100 |
|||
10 10 10 10 |
|||
15 25 |
|||
15 25 |
|||
15 15 10 |
|||
15 15 10 |
|||
15 15 10 |
|||
15 15 10 |
|||
5 10 25 |
|||
5 10 25</syntaxhighlight> |
|||
=={{header|jq}}== |
=={{header|jq}}== |
||
Line 133: | Line 437: | ||
The solutions presented in this section use generic `combinations` and `permutations` |
The solutions presented in this section use generic `combinations` and `permutations` |
||
functions defined as follows: |
functions defined as follows: |
||
<syntaxhighlight lang="jq"> |
|||
<lang jq> |
|||
# Input: an array of arrays |
# Input: an array of arrays |
||
# Output: a stream of arrays corresponding to the selection of exactly one item |
# Output: a stream of arrays corresponding to the selection of exactly one item |
||
Line 152: | Line 456: | ||
| [.[$i]] + (del(.[$i])|permutations) |
| [.[$i]] + (del(.[$i])|permutations) |
||
end ; |
end ; |
||
</syntaxhighlight> |
|||
</lang> |
|||
<syntaxhighlight lang="jq"> |
|||
<lang jq> |
|||
## Generic helper functions: |
## Generic helper functions: |
||
def count(s): reduce s as $x (0; .+1); |
def count(s): reduce s as $x (0; .+1); |
||
Line 160: | Line 464: | ||
# Output: [ [a,0], [b,0],... ] | combinations |
# Output: [ [a,0], [b,0],... ] | combinations |
||
def zero_or_one: [ .[] | [., 0] ] | combinations; |
def zero_or_one: [ .[] | [., 0] ] | combinations; |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''The task''' |
'''The task''' |
||
<syntaxhighlight lang="jq"> |
|||
<lang jq> |
|||
def count_combinations_with_sum($sum): |
def count_combinations_with_sum($sum): |
||
count( zero_or_one | select(add == $sum)); |
count( zero_or_one | select(add == $sum)); |
||
Line 183: | Line 487: | ||
[[1, 1, 2, 3, 3, 4, 5], 6], |
[[1, 1, 2, 3, 3, 4, 5], 6], |
||
[[1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 40] |
[[1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 40] |
||
| task</ |
| task</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 200: | Line 504: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Combinatorics |
||
function coinsum(coins, targetsum; verbose=true) |
function coinsum(coins, targetsum; verbose=true) |
||
Line 221: | Line 525: | ||
coinsum([1, 1, 2, 3, 3, 4, 5], 6) |
coinsum([1, 1, 2, 3, 3, 4, 5], 6) |
||
coinsum([1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 40, verbose=false) |
coinsum([1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 40, verbose=false) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
Coins are [1, 2, 3, 4, 5], target sum is 6: |
Coins are [1, 2, 3, 4, 5], target sum is 6: |
||
Line 294: | Line 598: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">ClearAll[CoinSums] |
||
CoinSums[coins_List, sum_] := Module[{c, len, max, bin, sel, out}, |
CoinSums[coins_List, sum_] := Module[{c, len, max, bin, sel, out}, |
||
c = {Range[Length[coins]], coins} // Transpose; |
c = {Range[Length[coins]], coins} // Transpose; |
||
Line 316: | Line 620: | ||
CoinSums[{1, 2, 3, 4, 5}, 6] |
CoinSums[{1, 2, 3, 4, 5}, 6] |
||
CoinSums[{1, 1, 2, 3, 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]] &</ |
CoinSums[{1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100}, 40] // Take[#, UpTo[10]] &</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Note that the indexing is 1-based and that for the last case only the first 10 solutions are shown: |
Note that the indexing is 1-based and that for the last case only the first 10 solutions are shown: |
||
Line 328: | Line 632: | ||
=={{header|MiniZinc}}== |
=={{header|MiniZinc}}== |
||
; coins = [1, 2, 3, 4, 5] and sum = 6 |
; coins = [1, 2, 3, 4, 5] and sum = 6 |
||
<syntaxhighlight lang="minizinc"> |
|||
<lang MiniZinc> |
|||
%Subset sum. Nigel Galloway: January 6th., 2021. |
%Subset sum. Nigel Galloway: January 6th., 2021. |
||
enum Items={a,b,c,d,e}; |
enum Items={a,b,c,d,e}; |
||
Line 335: | Line 639: | ||
var int: wSelected=sum(n in selected)(weight[n]); |
var int: wSelected=sum(n in selected)(weight[n]); |
||
constraint wSelected=6; |
constraint wSelected=6; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 359: | Line 663: | ||
</pre> |
</pre> |
||
; coins = [1, 1, 2, 3, 3, 4, 5] and sum = 6 |
; coins = [1, 1, 2, 3, 3, 4, 5] and sum = 6 |
||
<syntaxhighlight lang="minizinc"> |
|||
<lang MiniZinc> |
|||
%Subset sum. Nigel Galloway: January 6th., 2021. |
%Subset sum. Nigel Galloway: January 6th., 2021. |
||
enum Items={a,b,c,d,e,f,g}; |
enum Items={a,b,c,d,e,f,g}; |
||
Line 366: | Line 670: | ||
var int: wSelected=sum(n in selected)(weight[n]); |
var int: wSelected=sum(n in selected)(weight[n]); |
||
constraint wSelected=6; |
constraint wSelected=6; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 402: | Line 706: | ||
</pre> |
</pre> |
||
; coins = [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] and sum = 40 |
; coins = [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] and sum = 40 |
||
<syntaxhighlight lang="minizinc"> |
|||
<lang MiniZinc> |
|||
%Subset sum. Nigel Galloway: January 6th., 2021. |
%Subset sum. Nigel Galloway: January 6th., 2021. |
||
enum Items={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p}; |
enum Items={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p}; |
||
Line 409: | Line 713: | ||
var int: wSelected=sum(n in selected)(weight[n]); |
var int: wSelected=sum(n in selected)(weight[n]); |
||
constraint wSelected=40; |
constraint wSelected=40; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 462: | Line 766: | ||
Using a solver object rather than global variables. |
Using a solver object rather than global variables. |
||
< |
<syntaxhighlight lang="nim">import math, sequtils, strutils |
||
type Solver = object |
type Solver = object |
||
Line 499: | Line 803: | ||
countCoins(6, [1, 2, 3, 4, 5], 5) |
countCoins(6, [1, 2, 3, 4, 5], 5) |
||
countCoins(6, [1, 1, 2, 3, 3, 4, 5], 7) |
countCoins(6, [1, 1, 2, 3, 3, 4, 5], 7) |
||
countCoins(40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 18)</ |
countCoins(40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 18)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 540: | Line 844: | ||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
first count all combinations by brute force.Order is important.Modified nQueens.<BR>Next adding weigths by index.<BR>Using Phix wording 'silly'. |
first count all combinations by brute force.Order is important.Modified nQueens.<BR>Next adding weigths by index.<BR>Using Phix wording 'silly'. |
||
< |
<syntaxhighlight lang="pascal">program Coins0_1; |
||
{$IFDEF FPC} |
{$IFDEF FPC} |
||
{$MODE DELPHI} |
{$MODE DELPHI} |
||
Line 651: | Line 955: | ||
CheckAll(High(coins3),40); |
CheckAll(High(coins3),40); |
||
end. |
end. |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 663: | Line 967: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">#!/usr/bin/perl |
||
use strict; # https://rosettacode.org/wiki/Count_the_coins/0-1 |
use strict; # https://rosettacode.org/wiki/Count_the_coins/0-1 |
||
Line 694: | Line 998: | ||
count( $want, $used, $sum, \@rest); |
count( $want, $used, $sum, \@rest); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 710: | Line 1,014: | ||
=== sane way === |
=== sane way === |
||
In the second test, this counts [1,2,3] as one way to get 6, not counting the other [1,2,3] or the other [1,2,3] or the other [1,2,3]. |
In the second test, this counts [1,2,3] as one way to get 6, not counting the other [1,2,3] or the other [1,2,3] or the other [1,2,3]. |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">choices</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cdx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">choices</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cdx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
||
Line 730: | Line 1,034: | ||
<span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">},</span><span style="color: #000000;">40</span><span style="color: #0000FF;">}}</span> |
<span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">},</span><span style="color: #000000;">40</span><span style="color: #0000FF;">}}</span> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">choices</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)})</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">choices</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)})</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 737: | Line 1,041: | ||
=== silly way === |
=== silly way === |
||
In the second test, this counts [1,2,3] as four ways to get 6, since there are two 1s and two 3s... ("order unimportant") |
In the second test, this counts [1,2,3] as four ways to get 6, since there are two 1s and two 3s... ("order unimportant") |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">silly</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cdx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">silly</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cdx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
||
Line 754: | Line 1,058: | ||
<span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">},</span><span style="color: #000000;">40</span><span style="color: #0000FF;">}}</span> |
<span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">},</span><span style="color: #000000;">40</span><span style="color: #0000FF;">}}</span> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">silly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)})</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">silly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)})</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 761: | Line 1,065: | ||
=== very silly way === |
=== very silly way === |
||
In the second test, this counts [1,2,3] as 24 ways to get 6, from 2 1s, 2 3s, and 6 ways to order them ("order important") |
In the second test, this counts [1,2,3] as 24 ways to get 6, from 2 1s, 2 3s, and 6 ways to order them ("order important") |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">very_silly</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cdx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">taken</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">very_silly</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cdx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">taken</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> |
||
Line 778: | Line 1,082: | ||
<span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">},</span><span style="color: #000000;">40</span><span style="color: #0000FF;">}}</span> |
<span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">},</span><span style="color: #000000;">40</span><span style="color: #0000FF;">}}</span> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">very_silly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)})</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">very_silly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)})</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 784: | Line 1,088: | ||
</pre> |
</pre> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">from itertools import product, compress |
||
fact = lambda n: n and n*fact(n - 1) or 1 |
fact = lambda n: n and n*fact(n - 1) or 1 |
||
Line 801: | Line 1,105: | ||
for s, c in cases: |
for s, c in cases: |
||
print(f'{combo_count(s, c, perm):7d} ways for {s:2d} total from coins {c}') |
print(f'{combo_count(s, c, perm):7d} ways for {s:2d} total from coins {c}') |
||
print()</ |
print()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Order matters: False |
<pre>Order matters: False |
||
Line 818: | Line 1,122: | ||
This is pretty much duplicating other tasks, in process if not wording. Even though I am adding a solution, my vote would be for deletion as it doesn't really add anything to the other tasks; [[Combinations]], [[Permutations]], [[Subset sum problem]] and to a large extent [[4-rings or 4-squares puzzle]]. |
This is pretty much duplicating other tasks, in process if not wording. Even though I am adding a solution, my vote would be for deletion as it doesn't really add anything to the other tasks; [[Combinations]], [[Permutations]], [[Subset sum problem]] and to a large extent [[4-rings or 4-squares puzzle]]. |
||
<lang |
<syntaxhighlight lang="raku" line>for <1 2 3 4 5>, 6 |
||
,<1 1 2 3 3 4 5>, 6 |
,<1 1 2 3 3 4 5>, 6 |
||
,<1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100>, 40 |
,<1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100>, 40 |
||
Line 834: | Line 1,138: | ||
put "\nOrder {$un}important:\nCount: { +$list }\nIndices" ~ ( +$list > 10 ?? ' (10 random examples):' !! ':' ); |
put "\nOrder {$un}important:\nCount: { +$list }\nIndices" ~ ( +$list > 10 ?? ' (10 random examples):' !! ':' ); |
||
put $list.pick(10).sort».join(', ').join: "\n" |
put $list.pick(10).sort».join(', ').join: "\n" |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>How many combinations of [1, 2, 3, 4, 5] sum to 6? |
<pre>How many combinations of [1, 2, 3, 4, 5] sum to 6? |
||
Line 924: | Line 1,228: | ||
Well, after some huffing and puffing, the house is still standing so I thought I'd have a go at it. |
Well, after some huffing and puffing, the house is still standing so I thought I'd have a go at it. |
||
Based on the Perl algorithm but modified to deal with the extra credit. |
Based on the Perl algorithm but modified to deal with the extra credit. |
||
< |
<syntaxhighlight lang="wren">import "./fmt" for Fmt |
||
import "/math" for Int |
import "./math" for Int |
||
var cnt = 0 // order unimportant |
var cnt = 0 // order unimportant |
||
Line 963: | Line 1,267: | ||
countCoins.call(6, [1, 2, 3, 4, 5], 9) |
countCoins.call(6, [1, 2, 3, 4, 5], 9) |
||
countCoins.call(6, [1, 1, 2, 3, 3, 4, 5], 9) |
countCoins.call(6, [1, 1, 2, 3, 3, 4, 5], 9) |
||
countCoins.call(40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 28)</ |
countCoins.call(40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 28)</syntaxhighlight> |
||
{{out}} |
{{out}} |
Latest revision as of 08:46, 7 May 2024
Let say you have some coins in your wallet and you want to have a given sum.
You can use each coin zero or one time.
How many ways can you do it ?
The result should be a number.
For instance the answer is 10 when coins = [1, 2, 3, 4, 5] and sum = 6.
- Task
Show the result for the following examples:
- coins = [1, 2, 3, 4, 5] and sum = 6
- coins = [1, 1, 2, 3, 3, 4, 5] and sum = 6
- coins = [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] and sum = 40
- Extra
- Show the result of the same examples when the order you take the coins doesn't matter. For instance the answer is 3 when coins = [1, 2, 3, 4, 5] and sum = 6.
- Show an example of coins you used to reach the given sum and their indices. See Raku for this case.
11l
T Solver
Int want, width
count1 = 0
count2 = 0
F (want, width)
.want = want
.width = width
F count(Int sum; [Int] used, have, uindices, rindices) -> Void
I sum == .want
.count1++
.count2 += factorial(used.len)
I .count1 < 11
V uindiceStr = uindices.join(‘ ’).ljust(.width)
print(‘ indices ’uindiceStr‘ => used ’used.join(‘ ’))
E I sum < .want & !have.empty
V thisCoin = have[0]
V index = rindices[0]
V rest = have[1..]
V new_rindices = rindices[1..]
.count(sum + thisCoin, used [+] thisCoin, rest, uindices [+] index, new_rindices)
.count(sum, used, rest, uindices, new_rindices)
F count_coins(Int want, [Int] &coins, Int width)
print(‘Sum ’want‘ from coins ’coins.join(‘ ’))
V solver = Solver(want, width)
V rindices = Array(0 .< coins.len)
solver.count(0, [Int](), coins, [Int](), rindices)
I solver.count1 > 10
print(‘ .......’)
print(‘ (only the first 10 ways generated are shown)’)
print(‘Number of ways - order unimportant : ’(solver.count1)‘ (as above)’)
print(‘Number of ways - order important : ’(solver.count2)" (all perms of above indices)\n")
count_coins(6, &[1, 2, 3, 4, 5], 5)
count_coins(6, &[1, 1, 2, 3, 3, 4, 5], 7)
count_coins(40, &[1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 18)
- Output:
Sum 6 from coins 1 2 3 4 5 indices 0 1 2 => used 1 2 3 indices 0 4 => used 1 5 indices 1 3 => used 2 4 Number of ways - order unimportant : 3 (as above) Number of ways - order important : 10 (all perms of above indices) Sum 6 from coins 1 1 2 3 3 4 5 indices 0 1 5 => used 1 1 4 indices 0 2 3 => used 1 2 3 indices 0 2 4 => used 1 2 3 indices 0 6 => used 1 5 indices 1 2 3 => used 1 2 3 indices 1 2 4 => used 1 2 3 indices 1 6 => used 1 5 indices 2 5 => used 2 4 indices 3 4 => used 3 3 Number of ways - order unimportant : 9 (as above) Number of ways - order important : 38 (all perms of above indices) Sum 40 from coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100 indices 0 1 2 3 4 5 6 7 10 => used 1 2 3 4 5 5 5 5 10 indices 0 1 2 3 4 5 6 7 11 => used 1 2 3 4 5 5 5 5 10 indices 0 1 2 3 4 5 6 7 12 => used 1 2 3 4 5 5 5 5 10 indices 0 1 2 3 4 5 6 7 13 => used 1 2 3 4 5 5 5 5 10 indices 0 1 2 3 4 5 6 8 => used 1 2 3 4 5 5 5 15 indices 0 1 2 3 4 5 6 9 => used 1 2 3 4 5 5 5 15 indices 0 1 2 3 4 5 7 8 => used 1 2 3 4 5 5 5 15 indices 0 1 2 3 4 5 7 9 => used 1 2 3 4 5 5 5 15 indices 0 1 2 3 4 5 10 11 => used 1 2 3 4 5 5 10 10 indices 0 1 2 3 4 5 10 12 => used 1 2 3 4 5 5 10 10 ....... (only the first 10 ways generated are shown) Number of ways - order unimportant : 464 (as above) Number of ways - order important : 3782932 (all perms of above indices)
ALGOL 68
which is
BEGIN # count the ways of summing coins to a particular number - translation of the Go sample #
INT countu := 0; # order unimportant #
INT counti := 0; # order important #
INT width := 0; # for printing purposes #
PROC factorial = (INT n )INT:
BEGIN
INT prod := 1;
FOR i FROM 2 TO n DO
prod *:= i
OD;
prod
END # factorial # ;
OP LEN = ( []INT a )INT: ( UPB a - LWB a ) + 1;
OP LEN = ( STRING a )INT: ( UPB a - LWB a ) + 1;
PROC append = ( []INT a, INT b )[]INT:
BEGIN
[ 1 : LEN a + 1 ]INT result;
result[ 1 : LEN a ] := a;
result[ LEN a + 1 ] := b;
result
END # append # ;
OP TOSTRING = ( []INT a )STRING:
BEGIN
STRING result := "[";
STRING separator := "";
FOR i FROM LWB a TO UPB a DO
result +:= separator + whole( a[ i ], 0 );
separator := " "
OD;
result +:= "]"
END # TOSTRING # ;
PROC pad = ( STRING a, INT width )STRING:
IF INT len a = LEN a; len a >= width THEN a ELSE a + ( " " * ( width - len a ) ) FI;
PROC count = ( INT want, []INT used, INT sum, []INT have, uindices, rindices )VOID:
IF sum = want THEN
countu +:= 1;
counti +:= factorial( LEN used );
IF countu < 11 THEN
STRING uindices str = TOSTRING uindices;
print( ( " indices ", pad( uindices str, width ), " => used ", TOSTRING used, newline ) )
FI
ELIF sum < want AND LEN have /= 0 THEN
INT this coin = have[ LWB have ];
INT index = rindices[ LWB rindices ];
[]INT rest = have[ LWB have + 1 : ];
count( want, append( used, this coin ), sum + this coin, rest,
append( uindices, index ), rindices[ LWB rindices + 1 : ] );
count( want, used, sum, rest, uindices, rindices[ LWB rindices + 1 : ] )
FI # count # ;
PROC count coins = ( INT want, []INT coins, INT rqd width )VOID:
BEGIN
print( ( "Sum ", whole( want, 0 ), " from coins ", TOSTRING coins, newline ) );
countu := 0;
counti := 0;
width := rqd width;
[ 0 : LEN coins - 1 ]INT rindices;
FOR i FROM LWB rindices TO UPB rindices DO
rindices[ i ] := i
OD;
count( want, []INT(), 0, coins, []INT(), rindices );
IF countu > 10 THEN
print( ( " .......", newline ) );
print( ( " (only the first 10 ways generated are shown)", newline ) )
FI;
print( ( "Number of ways - order unimportant : ", whole( countu, 0 )
, " (as above)", newline ) );
print( ( "Number of ways - order important : ", whole( counti, 0 )
, " (all perms of above indices)", newline, newline ) )
END # count coins # ;
BEGIN # task #
count coins( 6, ( 1, 2, 3, 4, 5 ), 7 );
count coins( 6, ( 1, 1, 2, 3, 3, 4, 5 ), 9 );
count coins( 40, ( 1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100 ), 20 )
END
END
- Output:
Sum 6 from coins [1 2 3 4 5] indices [0 1 2] => used [1 2 3] indices [0 4] => used [1 5] indices [1 3] => used [2 4] Number of ways - order unimportant : 3 (as above) Number of ways - order important : 10 (all perms of above indices) Sum 6 from coins [1 1 2 3 3 4 5] indices [0 1 5] => used [1 1 4] indices [0 2 3] => used [1 2 3] indices [0 2 4] => used [1 2 3] indices [0 6] => used [1 5] indices [1 2 3] => used [1 2 3] indices [1 2 4] => used [1 2 3] indices [1 6] => used [1 5] indices [2 5] => used [2 4] indices [3 4] => used [3 3] Number of ways - order unimportant : 9 (as above) Number of ways - order important : 38 (all perms of above indices) Sum 40 from coins [1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100] indices [0 1 2 3 4 5 6 7 10] => used [1 2 3 4 5 5 5 5 10] indices [0 1 2 3 4 5 6 7 11] => used [1 2 3 4 5 5 5 5 10] indices [0 1 2 3 4 5 6 7 12] => used [1 2 3 4 5 5 5 5 10] indices [0 1 2 3 4 5 6 7 13] => used [1 2 3 4 5 5 5 5 10] indices [0 1 2 3 4 5 6 8] => used [1 2 3 4 5 5 5 15] indices [0 1 2 3 4 5 6 9] => used [1 2 3 4 5 5 5 15] indices [0 1 2 3 4 5 7 8] => used [1 2 3 4 5 5 5 15] indices [0 1 2 3 4 5 7 9] => used [1 2 3 4 5 5 5 15] indices [0 1 2 3 4 5 10 11] => used [1 2 3 4 5 5 10 10] indices [0 1 2 3 4 5 10 12] => used [1 2 3 4 5 5 10 10] ....... (only the first 10 ways generated are shown) Number of ways - order unimportant : 464 (as above) Number of ways - order important : 3782932 (all perms of above indices)
FreeBASIC
Based on the Phix entry and the Nim entry
#define factorial(n) Iif(n<2, 1, n*factorial1(n-1))
REM silly way
Function silly(coins() As Short, tgt As Short, cdx As Short = 1) As Integer
Dim As Integer count = 0
If tgt = 0 Then
count += 1
Elseif tgt > 0 And cdx <= Ubound(coins) Then
count += silly(coins(), tgt-coins(cdx), cdx+1)
count += silly(coins(), tgt, cdx+1)
End If
Return count
End Function
REM very silly way
Function very_silly(coins() As Short, tgt As Short, cdx As Short = 1, taken As Short = 0) As Integer
Dim As Integer count = 0
If tgt = 0 Then
count += factorial(taken)
Elseif tgt > 0 And cdx <= Ubound(coins) Then
count += very_silly(coins(), tgt-coins(cdx), cdx+1, taken+1)
count += very_silly(coins(), tgt, cdx+1, taken)
End If
Return count
End Function
Sub countCoins(coins() As Short, tgt As Short)
Print "Sum"; tgt; " from coins ";
For a As Short = 1 To Ubound(coins)
Print coins(a);
Next a
Print !"\nNumber of ways - order unimportant:"; silly(coins(), tgt)
Print "Number of ways - order important :"; very_silly(coins(), tgt); !"\n"
End Sub
Dim As Short test0(1 To ...) = {1, 2, 3, 4, 5}
countCoins(test0(), 6)
Dim As Short test1(1 To ...) = {1, 1, 2, 3, 3, 4, 5}
countCoins(test1(), 6)
Dim As Short test2(1 To ...) = {1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100}
countCoins(test2(), 40)
Sleep
- Output:
Sum 6 from coins 1 2 3 4 5 Number of ways - order unimportant: 3 Number of ways - order important : 10 Sum 6 from coins 1 1 2 3 3 4 5 Number of ways - order unimportant: 9 Number of ways - order important : 38 Sum 40 from coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100 Number of ways - order unimportant: 464 Number of ways - order important : 3782932
Go
package main
import "fmt"
var cnt = 0 // order unimportant
var cnt2 = 0 // order important
var wdth = 0 // for printing purposes
func factorial(n int) int {
prod := 1
for i := 2; i <= n; i++ {
prod *= i
}
return prod
}
func count(want int, used []int, sum int, have, uindices, rindices []int) {
if sum == want {
cnt++
cnt2 += factorial(len(used))
if cnt < 11 {
uindicesStr := fmt.Sprintf("%v", uindices)
fmt.Printf(" indices %*s => used %v\n", wdth, uindicesStr, used)
}
} else if sum < want && len(have) != 0 {
thisCoin := have[0]
index := rindices[0]
rest := have[1:]
rindices := rindices[1:]
count(want, append(used, thisCoin), sum+thisCoin, rest,
append(uindices, index), rindices)
count(want, used, sum, rest, uindices, rindices)
}
}
func countCoins(want int, coins []int, width int) {
fmt.Printf("Sum %d from coins %v\n", want, coins)
cnt = 0
cnt2 = 0
wdth = -width
rindices := make([]int, len(coins))
for i := range rindices {
rindices[i] = i
}
count(want, []int{}, 0, coins, []int{}, rindices)
if cnt > 10 {
fmt.Println(" .......")
fmt.Println(" (only the first 10 ways generated are shown)")
}
fmt.Println("Number of ways - order unimportant :", cnt, "(as above)")
fmt.Println("Number of ways - order important :", cnt2, "(all perms of above indices)\n")
}
func main() {
countCoins(6, []int{1, 2, 3, 4, 5}, 7)
countCoins(6, []int{1, 1, 2, 3, 3, 4, 5}, 9)
countCoins(40, []int{1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100}, 20)
}
- Output:
Sum 6 from coins [1 2 3 4 5] indices [0 1 2] => used [1 2 3] indices [0 4] => used [1 5] indices [1 3] => used [2 4] Number of ways - order unimportant : 3 (as above) Number of ways - order important : 10 (all perms of above indices) Sum 6 from coins [1 1 2 3 3 4 5] indices [0 1 5] => used [1 1 4] indices [0 2 3] => used [1 2 3] indices [0 2 4] => used [1 2 3] indices [0 6] => used [1 5] indices [1 2 3] => used [1 2 3] indices [1 2 4] => used [1 2 3] indices [1 6] => used [1 5] indices [2 5] => used [2 4] indices [3 4] => used [3 3] Number of ways - order unimportant : 9 (as above) Number of ways - order important : 38 (all perms of above indices) Sum 40 from coins [1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100] indices [0 1 2 3 4 5 6 7 10] => used [1 2 3 4 5 5 5 5 10] indices [0 1 2 3 4 5 6 7 11] => used [1 2 3 4 5 5 5 5 10] indices [0 1 2 3 4 5 6 7 12] => used [1 2 3 4 5 5 5 5 10] indices [0 1 2 3 4 5 6 7 13] => used [1 2 3 4 5 5 5 5 10] indices [0 1 2 3 4 5 6 8] => used [1 2 3 4 5 5 5 15] indices [0 1 2 3 4 5 6 9] => used [1 2 3 4 5 5 5 15] indices [0 1 2 3 4 5 7 8] => used [1 2 3 4 5 5 5 15] indices [0 1 2 3 4 5 7 9] => used [1 2 3 4 5 5 5 15] indices [0 1 2 3 4 5 10 11] => used [1 2 3 4 5 5 10 10] indices [0 1 2 3 4 5 10 12] => used [1 2 3 4 5 5 10 10] ....... (only the first 10 ways generated are shown) Number of ways - order unimportant : 464 (as above) Number of ways - order important : 3782932 (all perms of above indices)
J
Implementation:
selcoins=: {{ #:I.x=(#:i.2^#y)+/ .*y }}
ccoins=: {{ (#i), +/!x:+/"1 i=. x selcoins y }}
selcoins
identifies the valid selections of the coins. ccoins
counts them, giving two counts (first is where coin order does not matter, second is where each permutation of physical coins is counted separately).
Task examples:
6 ccoins 1 2 3 4 5
3 10
6 ccoins 1 1 2 3 3 4 5
9 38
40 ccoins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100
464 3782932
Some example coin selections:
rplc&(' 0';'')"1":6 (]#~selcoins) 1 2 3 4 5
2 4
1 5
1 2 3
rplc&(' 0';'')"1":6 (]#~selcoins) 1 1 2 3 3 4 5
3 3
2 4
1 5
1 2 3
1 2 3
1 5
1 2 3
1 2 3
1 1 4
rplc&(' 0';'')"1":40 (]#~9{.selcoins) 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100
10 10 10 10
15 25
15 25
15 15 10
15 15 10
15 15 10
15 15 10
5 10 25
5 10 25
jq
Works with gojq, the Go implementation of jq
The solutions presented in this section use generic `combinations` and `permutations` functions defined as follows:
# Input: an array of arrays
# Output: a stream of arrays corresponding to the selection of exactly one item
# from each top-level array
def combinations:
if length == 0 then []
else
.[0][] as $x
| (.[1:] | combinations) as $y
| [$x] + $y
end ;
# Generate a stream of all the permutations of the input array
def permutations:
if length == 0 then []
else
range(0;length) as $i
| [.[$i]] + (del(.[$i])|permutations)
end ;
## Generic helper functions:
def count(s): reduce s as $x (0; .+1);
# Input: an array [a, b, ... ]
# Output: [ [a,0], [b,0],... ] | combinations
def zero_or_one: [ .[] | [., 0] ] | combinations;
The task
def count_combinations_with_sum($sum):
count( zero_or_one | select(add == $sum));
def count_permutations_with_sum($sum):
count( zero_or_one | select(add == $sum) | map(select(.!=0)) | permutations);
# Each task takes the form of [ARRAY, SUM]
def task:
. as [$array, $sum]
| $array
| count_combinations_with_sum($sum) as $n
| count_permutations_with_sum($sum) as $p
| "With coins \($array) and target sum \($sum):",
" #combinations is \($n)",
" #permutations is \($p)\n";
[[1,2,3,4,5],6],
[[1, 1, 2, 3, 3, 4, 5], 6],
[[1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 40]
| task
- Output:
With coins [1,2,3,4,5] and target sum 6: #combinations is 3 #permutations is 10 With coins [1,1,2,3,3,4,5] and target sum 6: #combinations is 9 #permutations is 38 With coins [1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100] and target sum 40: #combinations is 464 #permutations is 3782932
Julia
using Combinatorics
function coinsum(coins, targetsum; verbose=true)
println("Coins are $coins, target sum is $targetsum:")
combos, perms = 0, 0
for choice in combinations(coins)
if sum(choice) == targetsum
combos += 1
verbose && println("$choice sums to $targetsum")
for perm in permutations(choice)
verbose && println(" permutation: $perm")
perms += 1
end
end
end
println("$combos combinations, $perms permutations.\n")
end
coinsum([1, 2, 3, 4, 5], 6)
coinsum([1, 1, 2, 3, 3, 4, 5], 6)
coinsum([1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 40, verbose=false)
- Output:
Coins are [1, 2, 3, 4, 5], target sum is 6: [1, 5] sums to 6 permutation: [1, 5] permutation: [5, 1] [2, 4] sums to 6 permutation: [2, 4] permutation: [4, 2] [1, 2, 3] sums to 6 permutation: [1, 2, 3] permutation: [1, 3, 2] permutation: [2, 1, 3] permutation: [2, 3, 1] permutation: [3, 1, 2] permutation: [3, 2, 1] 3 combinations, 10 permutations. Coins are [1, 1, 2, 3, 3, 4, 5], target sum is 6: [1, 5] sums to 6 permutation: [1, 5] permutation: [5, 1] [1, 5] sums to 6 permutation: [1, 5] permutation: [5, 1] [2, 4] sums to 6 permutation: [2, 4] permutation: [4, 2] [3, 3] sums to 6 permutation: [3, 3] permutation: [3, 3] [1, 1, 4] sums to 6 permutation: [1, 1, 4] permutation: [1, 4, 1] permutation: [1, 1, 4] permutation: [1, 4, 1] permutation: [4, 1, 1] permutation: [4, 1, 1] [1, 2, 3] sums to 6 permutation: [1, 2, 3] permutation: [1, 3, 2] permutation: [2, 1, 3] permutation: [2, 3, 1] permutation: [3, 1, 2] permutation: [3, 2, 1] [1, 2, 3] sums to 6 permutation: [1, 2, 3] permutation: [1, 3, 2] permutation: [2, 1, 3] permutation: [2, 3, 1] permutation: [3, 1, 2] permutation: [3, 2, 1] [1, 2, 3] sums to 6 permutation: [1, 2, 3] permutation: [1, 3, 2] permutation: [2, 1, 3] permutation: [2, 3, 1] permutation: [3, 1, 2] permutation: [3, 2, 1] [1, 2, 3] sums to 6 permutation: [1, 2, 3] permutation: [1, 3, 2] permutation: [2, 1, 3] permutation: [2, 3, 1] permutation: [3, 1, 2] permutation: [3, 2, 1] 9 combinations, 38 permutations. Coins are [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], target sum is 40: 464 combinations, 3782932 permutations.
Mathematica/Wolfram Language
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]] &
- Output:
Note that the indexing is 1-based and that for the last case only the first 10 solutions are shown:
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}|>}
MiniZinc
- coins = [1, 2, 3, 4, 5] and sum = 6
%Subset sum. Nigel Galloway: January 6th., 2021.
enum Items={a,b,c,d,e};
array[Items] of int: weight=[1,2,3,4,5];
var set of Items: selected;
var int: wSelected=sum(n in selected)(weight[n]);
constraint wSelected=6;
- Output:
selected = {a, b, c}; ---------- selected = {a, e}; ---------- selected = {b, d}; ---------- ========== %%%mzn-stat: initTime=0 %%%mzn-stat: solveTime=0.001 %%%mzn-stat: solutions=3 %%%mzn-stat: variables=21 %%%mzn-stat: propagators=31 %%%mzn-stat: propagations=236 %%%mzn-stat: nodes=11 %%%mzn-stat: failures=3 %%%mzn-stat: restarts=0 %%%mzn-stat: peakDepth=3 %%%mzn-stat-end Finished in 172msec
- coins = [1, 1, 2, 3, 3, 4, 5] and sum = 6
%Subset sum. Nigel Galloway: January 6th., 2021.
enum Items={a,b,c,d,e,f,g};
array[Items] of int: weight=[1,1,2,3,3,4,5];
var set of Items: selected;
var int: wSelected=sum(n in selected)(weight[n]);
constraint wSelected=6;
- Output:
selected = {a, b, f}; ---------- selected = {a, c, d}; ---------- selected = {a, c, e}; ---------- selected = {a, g}; ---------- selected = {b, c, d}; ---------- selected = {b, c, e}; ---------- selected = {b, g}; ---------- selected = {c, f}; ---------- selected = {d, e}; ---------- ========== %%%mzn-stat: initTime=0 %%%mzn-stat: solveTime=0.001 %%%mzn-stat: solutions=9 %%%mzn-stat: variables=29 %%%mzn-stat: propagators=43 %%%mzn-stat: propagations=820 %%%mzn-stat: nodes=35 %%%mzn-stat: failures=9 %%%mzn-stat: restarts=0 %%%mzn-stat: peakDepth=4 %%%mzn-stat-end Finished in 187msec
- coins = [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] and sum = 40
%Subset sum. Nigel Galloway: January 6th., 2021.
enum Items={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p};
array[Items] of int: weight=[1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100];
var set of Items: selected;
var int: wSelected=sum(n in selected)(weight[n]);
constraint wSelected=40;
- Output:
selected = {a, b, c, d, e, f, g, h, k}; ---------- selected = {a, b, c, d, e, f, g, h, l}; ---------- [ 0 more solutions ] selected = {a, b, c, d, e, f, g, h, m}; ---------- [ 1 more solutions ] selected = {a, b, c, d, e, f, g, i}; ---------- [ 3 more solutions ] selected = {a, b, c, d, e, f, k, l}; ---------- [ 7 more solutions ] selected = {a, b, c, d, e, g, k, l}; ---------- [ 15 more solutions ] selected = {a, b, c, d, e, j, k}; ---------- [ 31 more solutions ] selected = {a, b, c, d, g, h, l, n}; ---------- [ 63 more solutions ] selected = {a, d, e, h, i, l}; ---------- [ 127 more solutions ] selected = {b, c, e, l, m, n}; ---------- [ 206 more solutions ] selected = {k, l, m, n}; ---------- ========== %%%mzn-stat: initTime=0.001 %%%mzn-stat: solveTime=0.011 %%%mzn-stat: solutions=464 %%%mzn-stat: variables=65 %%%mzn-stat: propagators=91 %%%mzn-stat: propagations=122926 %%%mzn-stat: nodes=4203 %%%mzn-stat: failures=1638 %%%mzn-stat: restarts=0 %%%mzn-stat: peakDepth=13 %%%mzn-stat-end Finished in 207msec
Nim
Using a solver object rather than global variables.
import math, sequtils, strutils
type Solver = object
want: Positive
count1: Natural
count2: Natural
width: Natural
proc count(solver: var Solver; sum: int; used, have, uindices, rindices: seq[int]) =
if sum == solver.want:
inc solver.count1
inc solver.count2, fac(used.len)
if solver.count1 < 11:
let uindiceStr = ($uindices.join(" ")).alignLeft(solver.width)
echo " indices $1 → used $2".format(uindiceStr, used.join(" "))
elif sum < solver.want and have.len != 0:
let thisCoin = have[0]
let index = rindices[0]
let rest = have[1..^1]
let rindices = rindices[1..^1]
solver.count(sum + thisCoin, used & thisCoin, rest, uindices & index, rindices)
solver.count(sum, used, rest, uindices, rindices)
proc countCoins(want: int; coins: openArray[int]; width: int) =
echo "Sum $# from coins $#".format(want, coins.join(" "))
var solver = Solver(want: want, width: width)
var rindices = toSeq(0..coins.high)
solver.count(0, newSeq[int](), @coins, newSeq[int](), rindices)
if solver.count1 > 10:
echo " ......."
echo " (only the first 10 ways generated are shown)"
echo "Number of ways – order unimportant : ", solver.count1, " (as above)"
echo "Number of ways – order important : ", solver.count2, " (all perms of above indices)\n"
when isMainModule:
countCoins(6, [1, 2, 3, 4, 5], 5)
countCoins(6, [1, 1, 2, 3, 3, 4, 5], 7)
countCoins(40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 18)
- Output:
Sum 6 from coins 1 2 3 4 5 indices 0 1 2 → used 1 2 3 indices 0 4 → used 1 5 indices 1 3 → used 2 4 Number of ways – order unimportant : 3 (as above) Number of ways – order important : 10 (all perms of above indices) Sum 6 from coins 1 1 2 3 3 4 5 indices 0 1 5 → used 1 1 4 indices 0 2 3 → used 1 2 3 indices 0 2 4 → used 1 2 3 indices 0 6 → used 1 5 indices 1 2 3 → used 1 2 3 indices 1 2 4 → used 1 2 3 indices 1 6 → used 1 5 indices 2 5 → used 2 4 indices 3 4 → used 3 3 Number of ways – order unimportant : 9 (as above) Number of ways – order important : 38 (all perms of above indices) Sum 40 from coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100 indices 0 1 2 3 4 5 6 7 10 → used 1 2 3 4 5 5 5 5 10 indices 0 1 2 3 4 5 6 7 11 → used 1 2 3 4 5 5 5 5 10 indices 0 1 2 3 4 5 6 7 12 → used 1 2 3 4 5 5 5 5 10 indices 0 1 2 3 4 5 6 7 13 → used 1 2 3 4 5 5 5 5 10 indices 0 1 2 3 4 5 6 8 → used 1 2 3 4 5 5 5 15 indices 0 1 2 3 4 5 6 9 → used 1 2 3 4 5 5 5 15 indices 0 1 2 3 4 5 7 8 → used 1 2 3 4 5 5 5 15 indices 0 1 2 3 4 5 7 9 → used 1 2 3 4 5 5 5 15 indices 0 1 2 3 4 5 10 11 → used 1 2 3 4 5 5 10 10 indices 0 1 2 3 4 5 10 12 → used 1 2 3 4 5 5 10 10 ....... (only the first 10 ways generated are shown) Number of ways – order unimportant : 464 (as above) Number of ways – order important : 3782932 (all perms of above indices)
Pascal
first count all combinations by brute force.Order is important.Modified nQueens.
Next adding weigths by index.
Using Phix wording 'silly'.
program Coins0_1;
{$IFDEF FPC}
{$MODE DELPHI}
{$OPTIMIZATION ON,ALL}
{$ELSE}
{$Apptype console}
{$ENDIF}
uses
sysutils;// TDatetime
const
coins1 :array[0..4] of byte = (1, 2, 3, 4, 5);
coins2 :array[0..6] of byte = (1, 1, 2, 3, 3, 4, 5);
coins3 :array[0..15] of byte = (1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100);
nmax = High(Coins3);
type
{$IFNDEF FPC}
NativeInt = Int32;
{$ENDIF}
tFreeCol = array[0..nmax] of Int32;
var
FreeIdx,
IdxWeight : tFreeCol;
n,
gblCount : nativeUInt;
procedure AddNextWeight(Row,sum:nativeInt);
//order is important
var
i,Col,Weight : nativeInt;
begin
IF row <= n then
begin
For i := row to n do
begin
Col := FreeIdx[i];
Weight:= IdxWeight[col];
IF Sum+Weight <= 0 then
Begin
Sum +=Weight;
If Sum = 0 then
Begin
Sum -=Weight;
inc(gblCount);
end
else
begin
FreeIdx[i] := FreeIdx[Row];
FreeIdx[Row] := Col;
AddNextWeight(Row+1,sum);
//Undo
Sum -=Weight;
FreeIdx[Row] := FreeIdx[i];
FreeIdx[i] := Col;
end;
end;
end;
end;
end;
procedure CheckBinary(n,MaxIdx,Sum:NativeInt);
//order is not important
Begin
if sum = 0 then
inc(gblcount);
If (sum < 0) AND (n <= MaxIdx) then
Begin
//test next sum
CheckBinary(n+1,MaxIdx,Sum);// add nothing
CheckBinary(n+1,MaxIdx,Sum+IdxWeight[n]);//or the actual index
end;
end;
procedure CheckAll(i,MaxSum:NativeInt);
Begin
n := i;
gblCount := 0;
AddNextWeight(0,-MaxSum);
Write(MaxSum:6,gblCount:12);
gblCount := 0;
CheckBinary(0,i,-MaxSum);
WriteLn(gblCount:12);
end;
var
i: nativeInt;
begin
writeln('sum':6,'very silly':12,'silly':12);
For i := 0 to High(coins1) do
Begin
FreeIdx[i] := i;
IdxWeight[i] := coins1[i];
end;
CheckAll(High(coins1),6);
For i := 0 to High(coins2) do
Begin
FreeIdx[i] := i;
IdxWeight[i] := coins2[i];
end;
CheckAll(High(coins2),6);
For i := 0 to High(coins3) do
Begin
FreeIdx[i] := i;
IdxWeight[i] := coins3[i];
end;
CheckAll(High(coins3),40);
end.
- Output:
sum very silly silly 6 10 3 6 38 9 40 3782932 464 // real 0m0,080s ( fpc 3.2.0 -O3 -Xs AMD 2200G 3.7 Ghz )
Perl
#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Count_the_coins/0-1
use warnings;
countcoins( 6, [1, 2, 3, 4, 5] );
countcoins( 6, [1, 1, 2, 3, 3, 4, 5] );
countcoins( 40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] );
my $count;
sub countcoins
{
my ($want, $coins) = @_;
print "\nsum $want coins @$coins\n";
$count = 0;
count($want, [], 0, $coins);
print "Number of ways: $count\n";
}
sub count
{
my ($want, $used, $sum, $have) = @_;
if( $sum == $want ) { $count++ }
elsif( $sum > $want or @$have == 0 ) {}
else
{
my ($thiscoin, @rest) = @$have;
count( $want, [@$used, $thiscoin], $sum + $thiscoin, \@rest);
count( $want, $used, $sum, \@rest);
}
}
- Output:
sum 6 coins 1 2 3 4 5 Number of ways: 3 sum 6 coins 1 1 2 3 3 4 5 Number of ways: 9 sum 40 coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100 Number of ways: 464
Phix
sane way
In the second test, this counts [1,2,3] as one way to get 6, not counting the other [1,2,3] or the other [1,2,3] or the other [1,2,3].
with javascript_semantics function choices(sequence coins, integer tgt, cdx=1) integer count = 0 if tgt=0 then count += 1 elsif tgt>0 and cdx<=length(coins) then object ci = coins[cdx] integer {c,n} = iff(sequence(ci)?ci:{ci,1}) for j=0 to n do count += choices(coins,tgt-j*c,cdx+1) end for end if return count end function constant tests = {{{1,2,3,4,5},6}, {{{1,2},2,{3,2},4,5},6}, {{1,2,3,4,{5,4},{15,2},{10,4},25,100},40}} printf(1,"%V\n",{apply(false,choices,tests)})
- Output:
{3,5,33}
silly way
In the second test, this counts [1,2,3] as four ways to get 6, since there are two 1s and two 3s... ("order unimportant")
with javascript_semantics function silly(sequence coins, integer tgt, cdx=1) integer count = 0 if tgt=0 then count += 1 elsif tgt>0 and cdx<=length(coins) then count += silly(coins,tgt-coins[cdx],cdx+1) count += silly(coins,tgt,cdx+1) end if return count end function constant tests = {{{1,2,3,4,5},6}, {{1,1,2,3,3,4,5},6}, {{1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100},40}} printf(1,"%V\n",{apply(false,silly,tests)})
- Output:
{3,9,464}
very silly way
In the second test, this counts [1,2,3] as 24 ways to get 6, from 2 1s, 2 3s, and 6 ways to order them ("order important")
with javascript_semantics function very_silly(sequence coins, integer tgt, cdx=1, taken=0) integer count = 0 if tgt=0 then count += factorial(taken) elsif tgt>0 and cdx<=length(coins) then count += very_silly(coins,tgt-coins[cdx],cdx+1,taken+1) count += very_silly(coins,tgt,cdx+1,taken) end if return count end function constant tests = {{{1,2,3,4,5},6}, {{1,1,2,3,3,4,5},6}, {{1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100},40}} printf(1,"%V\n",{apply(false,very_silly,tests)})
- Output:
{10,38,3782932}
Python
from itertools import product, compress
fact = lambda n: n and n*fact(n - 1) or 1
combo_count = lambda total, coins, perm:\
sum(perm and fact(len(x)) or 1
for x in (list(compress(coins, c))
for c in product(*([(0, 1)]*len(coins))))
if sum(x) == total)
cases = [(6, [1, 2, 3, 4, 5]),
(6, [1, 1, 2, 3, 3, 4, 5]),
(40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100])]
for perm in [False, True]:
print(f'Order matters: {perm}')
for s, c in cases:
print(f'{combo_count(s, c, perm):7d} ways for {s:2d} total from coins {c}')
print()
- Output:
Order matters: False 3 ways for 6 total from coins [1, 2, 3, 4, 5] 9 ways for 6 total from coins [1, 1, 2, 3, 3, 4, 5] 464 ways for 40 total from coins [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] Order matters: True 10 ways for 6 total from coins [1, 2, 3, 4, 5] 38 ways for 6 total from coins [1, 1, 2, 3, 3, 4, 5] 3782932 ways for 40 total from coins [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100]
Raku
First part is combinations filtered on a certain property. Second part (extra credit) is permutations of those combinations.
This is pretty much duplicating other tasks, in process if not wording. Even though I am adding a solution, my vote would be for deletion as it doesn't really add anything to the other tasks; Combinations, Permutations, Subset sum problem and to a large extent 4-rings or 4-squares puzzle.
for <1 2 3 4 5>, 6
,<1 1 2 3 3 4 5>, 6
,<1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100>, 40
-> @items, $sum {
put "\n\nHow many combinations of [{ @items.join: ', ' }] sum to $sum?";
given ^@items .combinations.grep: { @items[$_].sum == $sum } {
.&display;
display .race.map( { Slip(.permutations) } ), '';
}
}
sub display ($list, $un = 'un') {
put "\nOrder {$un}important:\nCount: { +$list }\nIndices" ~ ( +$list > 10 ?? ' (10 random examples):' !! ':' );
put $list.pick(10).sort».join(', ').join: "\n"
}
- Output:
How many combinations of [1, 2, 3, 4, 5] sum to 6? Order unimportant: Count: 3 Indices: 0, 1, 2 0, 4 1, 3 Order important: Count: 10 Indices: 0, 1, 2 0, 2, 1 0, 4 1, 0, 2 1, 2, 0 1, 3 2, 0, 1 2, 1, 0 3, 1 4, 0 How many combinations of [1, 1, 2, 3, 3, 4, 5] sum to 6? Order unimportant: Count: 9 Indices: 0, 1, 5 0, 2, 3 0, 2, 4 0, 6 1, 2, 3 1, 2, 4 1, 6 2, 5 3, 4 Order important: Count: 38 Indices (10 random examples): 0, 4, 2 1, 2, 3 1, 2, 4 1, 5, 0 1, 6 2, 1, 3 2, 1, 4 2, 4, 0 3, 2, 0 6, 0 How many combinations of [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] sum to 40? Order unimportant: Count: 464 Indices (10 random examples): 0, 1, 2, 3, 5, 7, 10, 11 0, 1, 2, 3, 5, 8, 12 0, 1, 2, 3, 6, 7, 11, 13 0, 3, 5, 7, 9, 13 0, 3, 9, 10, 11 1, 2, 5, 7, 9, 13 4, 5, 10, 12, 13 5, 6, 7, 9, 10 5, 6, 10, 11, 12 5, 8, 10, 12 Order important: Count: 3782932 Indices (10 random examples): 0, 11, 3, 4, 7, 5, 6, 1, 2 1, 10, 5, 4, 6, 2, 0, 3, 7 2, 7, 13, 4, 1, 3, 5, 6, 0 2, 12, 4, 13, 10, 1 3, 0, 5, 4, 7, 13, 6, 2, 1 5, 7, 9, 4, 0, 1, 2, 3 6, 2, 7, 11, 0, 3, 5, 1, 4 10, 0, 12, 6, 5, 3, 4 13, 0, 1, 5, 7, 3, 2, 12 13, 6, 10, 1, 4, 3, 2, 0
Wren
Well, after some huffing and puffing, the house is still standing so I thought I'd have a go at it. Based on the Perl algorithm but modified to deal with the extra credit.
import "./fmt" for Fmt
import "./math" for Int
var cnt = 0 // order unimportant
var cnt2 = 0 // order important
var wdth = 0 // for printing purposes
var count // recursive
count = Fn.new { |want, used, sum, have, uindices, rindices|
if (sum == want) {
cnt = cnt + 1
cnt2 = cnt2 + Int.factorial(used.count)
if (cnt < 11) Fmt.print(" indices $*n => used $n", wdth, uindices, used)
} else if (sum < want && !have.isEmpty) {
var thisCoin = have[0]
var index = rindices[0]
var rest = have.skip(1).toList
var rindices = rindices.skip(1).toList
count.call(want, used + [thisCoin], sum + thisCoin, rest, uindices + [index], rindices)
count.call(want, used, sum, rest, uindices, rindices)
}
}
var countCoins = Fn.new { |want, coins, width|
System.print("Sum %(want) from coins %(coins)")
cnt = 0
cnt2 = 0
wdth = -width
count.call(want, [], 0, coins, [], (0...coins.count).toList)
if (cnt > 10) {
System.print(" .......")
System.print(" (only the first 10 ways generated are shown)")
}
System.print("Number of ways - order unimportant : %(cnt) (as above)")
System.print("Number of ways - order important : %(cnt2) (all perms of above indices)\n")
}
countCoins.call(6, [1, 2, 3, 4, 5], 9)
countCoins.call(6, [1, 1, 2, 3, 3, 4, 5], 9)
countCoins.call(40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 28)
- Output:
Sum 6 from coins [1, 2, 3, 4, 5] indices [0, 1, 2] => used [1, 2, 3] indices [0, 4] => used [1, 5] indices [1, 3] => used [2, 4] Number of ways - order unimportant : 3 (as above) Number of ways - order important : 10 (all perms of above indices) Sum 6 from coins [1, 1, 2, 3, 3, 4, 5] indices [0, 1, 5] => used [1, 1, 4] indices [0, 2, 3] => used [1, 2, 3] indices [0, 2, 4] => used [1, 2, 3] indices [0, 6] => used [1, 5] indices [1, 2, 3] => used [1, 2, 3] indices [1, 2, 4] => used [1, 2, 3] indices [1, 6] => used [1, 5] indices [2, 5] => used [2, 4] indices [3, 4] => used [3, 3] Number of ways - order unimportant : 9 (as above) Number of ways - order important : 38 (all perms of above indices) Sum 40 from coins [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] indices [0, 1, 2, 3, 4, 5, 6, 7, 10] => used [1, 2, 3, 4, 5, 5, 5, 5, 10] indices [0, 1, 2, 3, 4, 5, 6, 7, 11] => used [1, 2, 3, 4, 5, 5, 5, 5, 10] indices [0, 1, 2, 3, 4, 5, 6, 7, 12] => used [1, 2, 3, 4, 5, 5, 5, 5, 10] indices [0, 1, 2, 3, 4, 5, 6, 7, 13] => used [1, 2, 3, 4, 5, 5, 5, 5, 10] indices [0, 1, 2, 3, 4, 5, 6, 8] => used [1, 2, 3, 4, 5, 5, 5, 15] indices [0, 1, 2, 3, 4, 5, 6, 9] => used [1, 2, 3, 4, 5, 5, 5, 15] indices [0, 1, 2, 3, 4, 5, 7, 8] => used [1, 2, 3, 4, 5, 5, 5, 15] indices [0, 1, 2, 3, 4, 5, 7, 9] => used [1, 2, 3, 4, 5, 5, 5, 15] indices [0, 1, 2, 3, 4, 5, 10, 11] => used [1, 2, 3, 4, 5, 5, 10, 10] indices [0, 1, 2, 3, 4, 5, 10, 12] => used [1, 2, 3, 4, 5, 5, 10, 10] ....... (only the first 10 ways generated are shown) Number of ways - order unimportant : 464 (as above) Number of ways - order important : 3782932 (all perms of above indices)