Talk:Count the coins/0-1

From Rosetta Code

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 algirithm 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:30, 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?

--Thundergnat (talk) 11:13, 6 January 2021 (UTC)

The order matters means 1 + 5 is different of 5 + 1. --Blek (talk) 16:32, 6 January 2021 (UTC)

Duplicate Task?

Although written in English they look very different, logically this and Subset_sum_problem are the same task. For an algorithm you could try https://academyera.com/sum-of-subsets-problem#:~:text=sum%20of%20subsets%20problem%20is%20nothing%20but%20Suppose,set%20whose%20sum%20adds%20to%20a%20number%20K. I checked there are different. --Blek (talk) 16:34, 6 January 2021 (UTC) There different in many ways. 

At least you may have duplicated elements in the list of coins. --Blek (talk)
Retrieved from "https://rosettacode.org/wiki/Talk:Count_the_coins/0-1?oldid=306362"