I've found a code to find number of possibilities to make change using given coins: How to count possible combination for coin problem. But how to count it, if we think about different permutations of the same sequence? I mean that, e.g. amount is 12, and "4 4 2 2" and "4 2 4 2" should be counted as 2, not 1.
Asked
Active
Viewed 1,125 times
1
-
Change of coins is a combination, not a permutation. – HelloWorld123456789 Mar 03 '14 at 19:31
-
So is there algorithm to count permutations? What's the name? – user132443 Mar 03 '14 at 19:34
-
Do you want to separate these [1 1 1] and [1 1 1] or just separate [1 2 3] and [1 3 2] for example? – Mohsen Kamrani Mar 03 '14 at 19:46
-
[1 1 1] and [1 1 1] are the same, [1 2 3] and [1 3 2] are different. I forgotten mention about it, thanks :) – user132443 Mar 03 '14 at 19:50
-
For each sequence ([1 1 2 3] for example) you can arrange it in (n1+n2+...+nk)! / (n1!*n2!*...*nk!) different ways where `ni` is the number of coins of this type. In the [1 1 2 3] example: n1=2,n2=1,n3=1 – amit Mar 03 '14 at 19:57
-
Yes, but how to "extract" these sequences? It is actually my main problem. – user132443 Mar 03 '14 at 19:59
-
It's said inside the link. Which part isn't clear to you? – Mohsen Kamrani Mar 03 '14 at 20:02
1 Answers
1
As you've mentioned inside your question you can count the possible combinations as stated in How to count possible combination for coin problem. But in order to include the permutations into your answer:
- If you distinguish the permutation of the same numbers [1 7 7] and [1 7 7] e.g. just count each sequence([1 7 7] here) as n! (n = # of elements in the sequence) [instead of 1]
- Otherwise : multiply each sequence by n!/(m!l!...) where m = number of equal elements of type 1, l is number of equal elements of type 2 and so on... . For example for sequence like [a b b c c c] you should count this 6!/(2!*3!) [instead of 1]
So use the algorithm inside that link, that I don't repeat again, but just instead of counting each combination as 1 use the formula that I said (depending on the case you desire).
(! is factorial.)
Community
- 1
- 1
Mohsen Kamrani
- 7,177
- 5
- 42
- 66
-
I think I don't understand algorithm in that code. I have no idea from what it depends it is counting that as 1... – user132443 Mar 03 '14 at 20:37
-
Take a look at [this](http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/) – Mohsen Kamrani Mar 03 '14 at 20:40
-
OK, I understood and successfully modified recursive version. But what about DP? Is it also possible to make that changes? – user132443 Mar 03 '14 at 21:58