Talk:Count the coins/0-1
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)
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)
- 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
- 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.
- '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)
- 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)
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, they are different. They are different in many ways. At least you may have duplicated elements in the list of coins. --Blek (talk) 16:39, 6 January 2021 (UTC)
- Call the first coin 'alliance', the second coin 'archbishop', the third coin 'balm' etc. Write them in a list and they are exactly the same!!!!--Nigel Galloway (talk) 16:44, 6 January 2021 (UTC)
- 'archbishop' and 'balm' could both have value 5. Ordering here just means find all permutations of a solution. We have a task for finding all permutations of a set.--Nigel Galloway (talk) 17:07, 6 January 2021 (UTC)
- Here I am looking for an number as ouput and the problem you are talking about wants a set. Let say it is minor difference. The order matters here while it doesn't in the problem you are talking about. Let say also it is a minor difference. The target sum is always zero in the problem you are talking when it may change here. Let say also it is minor difference. Want zero as sum may cause algorithms to use the idea to split set in 2 sets (negative and positive numbers) not easily transferable in this case. Let say it is a minor difference. I won't say many minor differences give a minor difference. --Blek (talk) 17:27, 6 January 2021 (UTC)
- It is also very similar to Permutations_with_some_identical_elements with one extra condition. --Pete Lomax (talk) 22:32, 6 January 2021 (UTC)