Count the coins/0-1: Difference between revisions

Content added Content deleted
m (syntax highlighting fixup automation)
(Added 11l)
Line 26: Line 26:


*  Show an example of coins you used to reach the given sum and their indices. See Raku for this case.
*  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|Go}}==
=={{header|Go}}==
Retrieved from "https://rosettacode.org/wiki/Count_the_coins/0-1"