Count the coins/0-1: Difference between revisions
→{{header|jq}}
m (→{{header|Phix}}: added syntax colouring the hard way) |
|||
Line 125:
Number of ways - order unimportant : 464 (as above)
Number of ways - order important : 3782932 (all perms of above indices)
</pre>
=={{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:
<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>
{{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>
| |||