Count the coins/0-1: Difference between revisions
(J) |
m (→{{header|J}}: spelling) |
||
Line 132: | Line 132: | ||
ccoins=: {{ (#i), +/!x:+/"1 i=. x selcoins y }}</lang> |
ccoins=: {{ (#i), +/!x:+/"1 i=. x selcoins y }}</lang> |
||
<code>selcoins</code> identifies the valid selections of the coins. <code>ccoins</code> counts |
<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:<lang J> 6 ccoins 1 2 3 4 5 |
Task examples:<lang J> 6 ccoins 1 2 3 4 5 |
Revision as of 02:44, 7 July 2022
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.
Go
<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)
}</lang>
- 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:<lang J>selcoins=: {{ #:I.x=(#:i.2^#y)+/ .*y }} ccoins=: Template:(</lang>
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:<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</lang>
jq
Works with gojq, the Go implementation of jq
The solutions presented in this section use generic `combinations` and `permutations` functions defined as follows: <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 ;
</lang> <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; </lang>
The task <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</lang>
- 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
<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)
</lang>
- 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
<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[selAll, 2] == sum, Sow@<|"Coins" -> selAll, 2, "Indices" -> selAll, 1|> ] , {i, 0, max} ]; out = out2, 1; Print[Length@out]; out ]
CoinSums[{1, 2, 3, 4, 5}, 6] CoinSums[{1, 1, 2, 3, 3, 4, 5}, 6] CoinSums[{1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100}, 40] // Take[#, UpTo[10]] &</lang>
- 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
<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; </lang>
- 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
<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; </lang>
- 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
<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; </lang>
- 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. <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)</lang>
- 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'.
<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. </lang>
- 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
<lang 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); } }</lang>
- 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
<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()</lang>
- 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.
<lang perl6>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"
}</lang>
- 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. <lang ecmascript>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)</lang>
- 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)