Anonymous user
Count the coins/0-1: Difference between revisions
→{{header|Nim}}
Line 352:
Finished in 207msec
</pre>
=={{header|Nim}}==
{{trans|Go}}
Using a solver object rather than global variables.
<lang Nim>import math, strutils, sugar
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 = collect(for i in 0..coins.high: i)
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>
{{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}}==
| |||