Count the coins/0-1: Difference between revisions

Count the coins/0-1 (view source)

Revision as of 11:37, 21 November 2023

43,773 bytes added , 6 months ago

m

→‎{{header|Wren}}: Minor tidy

PureFox

9,477

edits

Revision as of 12:54, 8 January 2021 (view source) rosettacode>Horst.h m (→‎{{header\|Pascal}}: added checking all weights not taking order into account) ← Older edit		Revision as of 11:37, 21 November 2023 (view source) PureFox (talk \| contribs) m (→‎{{header\|Wren}}: Minor tidy) Newer edit →
(19 intermediate revisions by 12 users not shown)
Line 26: *  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, nfactorial1(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"> ~~<lang MiniZinc>~~ %Subset sum. Nigel Galloway: January 6th., 2021. enum Items={a,b,c,d,e}; Line 36 ⟶ 639: var int: wSelected=sum(n in selected)(weight[n]); constraint wSelected=6; </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 60 ⟶ 663: </pre> ; coins = [1, 1, 2, 3, 3, 4, 5] and sum = 6 <syntaxhighlight lang="minizinc"> ~~<lang MiniZinc>~~ %Subset sum. Nigel Galloway: January 6th., 2021. enum Items={a,b,c,d,e,f,g}; Line 67 ⟶ 670: var int: wSelected=sum(n in selected)(weight[n]); constraint wSelected=6; </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 103 ⟶ 706: </pre> ; coins = [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] and sum = 40 <syntaxhighlight lang="minizinc"> ~~<lang MiniZinc>~~ %Subset sum. Nigel Galloway: January 6th., 2021. enum Items={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p}; Line 110 ⟶ 713: var int: wSelected=sum(n in selected)(weight[n]); constraint wSelected=40; </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 158 ⟶ 761: 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'. <~~lang~~syntaxhighlight lang="pascal">program Coins0_1; {$IFDEF FPC} {$MODE DELPHI} Line 271 ⟶ 955: CheckAll(High(coins3),40); end. </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 283 ⟶ 967: =={{header\|Perl}}== <~~lang~~syntaxhighlight lang="perl">#!/usr/bin/perl use strict; # https://rosettacode.org/wiki/Count_the_coins/0-1 Line 314 ⟶ 998: count( $want, $used, $sum, \@rest); } }</~~lang~~syntaxhighlight> {{out}} <pre> Line 329 ⟶ 1,013: =={{header\|Phix}}== === sane way === ~~This~~In the second test, this counts [1,2,3] as one way, ~~not~~to ~~counting~~get ~~[in~~6, ~~2nd~~not ~~test]~~counting the other [1,2,3] or the other [1,2,3] or the other [1,2,3]. <!--<syntaxhighlight lang="phix">(phixonline)--> ~~<lang Phix>function choices(sequence coins, integer tgt, cdx=1)~~ <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> ~~integer count = 0~~ <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> ~~if tgt=0 then~~ <span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> ~~count += 1~~ <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> ~~elsif tgt>0 and cdx<=length(coins) then~~ <span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> ~~object ci = coins[cdx]~~ <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> ~~integer {c,n} = iff(sequence(ci)?ci:{ci,1})~~ <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> ~~for j=0 to n do~~ <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> ~~count += choices(coins,tgt-jc,cdx+1)~~ <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> ~~end for~~ <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> ~~end if~~ <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> ~~return count~~ <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~end function~~ <span style="color: #008080;">return</span> <span style="color: #000000;">count</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> ~~constant tests = {{{1,2,3,4,5},6},~~ ~~{{{1,2},2,{3,2},4,5},6},~~ <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> ~~{{1,2,3,4,{5,4},{15,2},{10,4},25,100},40}}~~ <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> ~~?apply(false,choices,tests)</lang>~~ <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> Line 353 ⟶ 1,040: </pre> === silly way === ~~This~~In the second test, this counts [1,2,3] as four ways to get 6, since ~~[in 2nd test]~~ there are two 1s and two 3s... ("order unimportant") <!--<syntaxhighlight lang="phix">(phixonline)--> ~~<lang Phix>function silly(sequence coins, integer tgt, cdx=1)~~ <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> ~~integer count = 0~~ <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> ~~if tgt=0 then~~ <span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> ~~count += 1~~ <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> ~~elsif tgt>0 and cdx<=length(coins) then~~ <span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> ~~count += silly(coins,tgt-coins[cdx],cdx+1)~~ <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> ~~count += silly(coins,tgt,cdx+1)~~ <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> ~~end if~~ <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> ~~return count~~ <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~end function~~ <span style="color: #008080;">return</span> <span style="color: #000000;">count</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> ~~constant tests = {{{1,2,3,4,5},6},~~ ~~{{1,1,2,3,3,4,5},6},~~ <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> ~~{{1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100},40}}~~ <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> ~~?apply(false,silly,tests)</lang>~~ <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> Line 374 ⟶ 1,064: </pre> === very silly way === ~~This~~In the second test, this counts [1,2,3] as 24 ways to get 6, from 2 1s, 2 3s ~~[in 2nd test]~~, and 6 ways to order them ("order important") <!--<syntaxhighlight lang="phix">(phixonline)--> ~~<lang Phix>function very_silly(sequence coins, integer tgt, cdx=1, taken=0)~~ <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> ~~integer count = 0~~ <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> ~~if tgt=0 then~~ <span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> ~~count += factorial(taken)~~ <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> ~~elsif tgt>0 and cdx<=length(coins) then~~ <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> ~~count += very_silly(coins,tgt-coins[cdx],cdx+1,taken+1)~~ <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> ~~count += very_silly(coins,tgt,cdx+1,taken)~~ <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> ~~end if~~ <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> ~~return count~~ <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~end function~~ <span style="color: #008080;">return</span> <span style="color: #000000;">count</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> ~~constant tests = {{{1,2,3,4,5},6},~~ ~~{{1,1,2,3,3,4,5},6},~~ <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> ~~{{1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100},40}}~~ <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> ~~?apply(false,very_silly,tests)</lang>~~ <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 nfact(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}}== Line 400 ⟶ 1,122: This is pretty much duplicating other tasks, in process if not wording. Even though I am adding a solution, my vote would be for deletion as it doesn't really add anything to the other tasks; [[Combinations]], [[Permutations]], [[Subset sum problem]] and to a large extent [[4-rings or 4-squares puzzle]]. <syntaxhighlight lang="raku" ~~perl6~~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 Line 416 ⟶ 1,138: put "\nOrder {$un}important:\nCount: { +$list }\nIndices" ~ ( +$list > 10 ?? ' (10 random examples):' !! ':' ); put $list.pick(10).sort».join(', ').join: "\n" }</~~lang~~syntaxhighlight> {{out}} <pre>How many combinations of [1, 2, 3, 4, 5] sum to 6? Line 506 ⟶ 1,228: 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~~syntaxhighlight ~~ecmascript~~lang="wren">import "./fmt" for Fmt import "./math" for Int var cnt = 0 // order unimportant Line 545 ⟶ 1,267: 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~~syntaxhighlight> {{out}}