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