Count the coins/0-1: Difference between revisions
m
→{{header|Wren}}: Minor tidy
No edit summary |
m (→{{header|Wren}}: Minor tidy) |
||
| (32 intermediate revisions by 16 users not shown) | |||
Line 13:
<br/>
;Task
Show the result
* coins = [1, 2, 3, 4, 5] and sum = 6
Line 25:
* 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.
=={{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) -> N
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}}==
{{trans|Wren}}
<syntaxhighlight lang="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)
}</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|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}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
The solutions presented in this section use generic `combinations` and `permutations`
functions defined as follows:
<syntaxhighlight lang="jq">
# 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 ;
</syntaxhighlight>
<syntaxhighlight lang="jq">
## 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;
</syntaxhighlight>
'''The task'''
<syntaxhighlight lang="jq">
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</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Julia}}==
<syntaxhighlight lang="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)
</syntaxhighlight>{{out}}
<pre>
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.
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight 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]] &</syntaxhighlight>
{{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>
=={{header|MiniZinc}}==
; coins = [1, 2, 3, 4, 5] and sum = 6
<syntaxhighlight lang="minizinc">
%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;
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
; coins = [1, 1, 2, 3, 3, 4, 5] and sum = 6
<syntaxhighlight lang="minizinc">
%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;
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
; coins = [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] and sum = 40
<syntaxhighlight lang="minizinc">
%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;
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Nim}}==
{{trans|Go}}
Using a solver object rather than global variables.
<syntaxhighlight lang="nim">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)</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|Pascal}}==
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}
{$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.
</syntaxhighlight>
{{out}}
<pre>
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 )
</pre>
=={{header|Perl}}==
<
use strict; # https://rosettacode.org/wiki/Count_the_coins/0-1
Line 35 ⟶ 974:
countcoins( 6, [1, 2, 3, 4, 5] );
countcoins( 6, [1, 1, 2, 3, 3, 4, 5] );
my $count;
sub countcoins
Line 41 ⟶ 982:
my ($want, $coins) = @_;
print "\nsum $want coins @$coins\n";
$count = 0;
count($want, [], 0, $coins);
print "Number of ways: $count\n";
}
Line 47 ⟶ 990:
{
my ($want, $used, $sum, $have) = @_;
if( $sum == $want ) {
elsif( $sum > $want or @$have == 0 ) {}
else
Line 55 ⟶ 998:
count( $want, $used, $sum, \@rest);
}
}</
{{out}}
<pre>
sum 6 coins 1 2 3 4 5
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
</pre>
=={{header|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].
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">cdx</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">ci</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">coins</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cdx</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ci</span><span style="color: #0000FF;">)?</span><span style="color: #000000;">ci</span><span style="color: #0000FF;">:{</span><span style="color: #000000;">ci</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">choices</span><span style="color: #0000FF;">(</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tgt</span><span style="color: #0000FF;">-</span><span style="color: #000000;">j</span><span style="color: #0000FF;">*</span><span style="color: #000000;">c</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;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">count</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</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;">6</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;">2</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</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;">6</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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
{3,5,33}
</pre>
=== 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")
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">cdx</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">silly</span><span style="color: #0000FF;">(</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tgt</span><span style="color: #0000FF;">-</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cdx</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;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">silly</span><span style="color: #0000FF;">(</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">,</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;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">count</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</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;">6</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;">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;">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;">6</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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
{3,9,464}
</pre>
=== 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")
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #7060A8;">factorial</span><span style="color: #0000FF;">(</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">cdx</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">very_silly</span><span style="color: #0000FF;">(</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tgt</span><span style="color: #0000FF;">-</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cdx</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;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">very_silly</span><span style="color: #0000FF;">(</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">,</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: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">count</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</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;">6</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;">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;">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;">6</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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
{10,38,3782932}
</pre>
=={{header|Python}}==
<syntaxhighlight lang="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()</syntaxhighlight>
{{out}}
<pre>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]</pre>
=={{header|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]].
<syntaxhighlight lang="raku" line>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"
}</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Wren}}==
{{trans|Perl}}
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.
<syntaxhighlight lang="wren">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)</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>
| |||