Talk:Count the coins/0-1

Latest comment: 2 years ago by Petelomax in topic Several problems

If the order matters, the last example could be very large.

In really life order doesn't matter.

I think we could considered that the order doesn't matter for the last example.

But seeing both cases when order matters and not would be great. --Blek (talk) 07:02, 6 January 2021 (UTC)

Algorithm

Can you show an algorithm? --Paddy3118 (talk) 07:09, 6 January 2021 (UTC)

I will provide an algorithm but I think it is not optimal in term of complexity and it is why I don't want it becomes the main implementation. --Blek (talk) 16:44, 6 January 2021 (UTC)

Several problems

1. What this task is asking for is a duplicate of Combinations, only different in that it is asking for a count of combinations that have some property rather than an enumeration of combinations. In Raku the task would literally be:
`say +[1, 2, 3, 4, 5].combinations.grep: *.sum == 6`
2. Order matters; Do you mean 1 + 5 is not the same as 5 + 1? Or do you mean that each coin of the same denomination should be treated separately? (This 1 unit coin is different from that 1 unit coin.) If that is the case there needs to be something that makes them unique.
3. 'Count the coins' is a poor name for the task anyway, especially if you are going to have a restriction that order matters. By definition order doesn't matter when making change. It isn't counting coins, it's counting sums.

Stated another way; say, for instance, you were assembling power packs from different canisters of highly reactive fuel. Once you opened a canister, you must use all of it and the power pack has a tightly defined capacity requirement. Your power pack needs to have a capacity of 6 power units and you have fuel canisters with [1, 2, 3, 4, 5] units of fuel. How many ways can you resupply the power pack? Now. How is that problem substantially different from the one you stated? And what does it have to do with counting coins? See why 'counting coins' is a bad name?

The order matters means 1 + 5 is different of 5 + 1. --Blek (talk) 16:32, 6 January 2021 (UTC)
We already have a task for finding all permutations of 1 and 5.--Nigel Galloway (talk) 16:50, 6 January 2021 (UTC)
Why would you want to count [1,2,3] as either 4 ("order unimportant") or 24 ("order important") different ways to get 6 - which is what all of the solutions so far do for the middle case ...??!! --Pete Lomax (talk) 17:29, 7 January 2021 (UTC)