Count the coins/0-1 is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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.
Contents
Go[edit]
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)
MiniZinc[edit]
- 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
Pascal[edit]
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[edit]
#!/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[edit]
sane way[edit]
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].
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}}
?apply(false,choices,tests)
- Output:
{3,5,33}
silly way[edit]
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")
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}}
?apply(false,silly,tests)
- Output:
{3,9,464}
very silly way[edit]
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")
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}}
?apply(false,very_silly,tests)
- Output:
{10,38,3782932}
Raku[edit]
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[edit]
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)
