Talk:Combinations: Difference between revisions
m (→Dynamic programming for enumeration problems: Signature) |
(→Formula: new section) |
||
| Line 9: | Line 9: | ||
The gain of dynamic programming for a problem asking to list all solution rather than simply count them is much less than what is suggested by claims such as "The first solution is inefficient because it repeatedly calculates the same subproblem in different branches of recursion." (Haskell) for instance. The asymptotic complexity is the same, O(number of solutions * size of solution). [[User:Lyxia|Lyxia]] ([[User talk:Lyxia|talk]]) 01:30, 30 April 2017 (UTC) |
The gain of dynamic programming for a problem asking to list all solution rather than simply count them is much less than what is suggested by claims such as "The first solution is inefficient because it repeatedly calculates the same subproblem in different branches of recursion." (Haskell) for instance. The asymptotic complexity is the same, O(number of solutions * size of solution). [[User:Lyxia|Lyxia]] ([[User talk:Lyxia|talk]]) 01:30, 30 April 2017 (UTC) |
||
== Formula == |
|||
Strictlly speaking, combinations with repetiotions 5 of 5 give you 126 variants, just combinations give you just 1 variant |
|||
Formula for comb. with repet: http://hijos.ru/wp-content/ql-cache/quicklatex-7f6e17e6e05e9a62c1188bd95ff7e8ad.gif |
|||
Revision as of 09:28, 30 April 2017
Combinations with repetitions
The formula for combinations with repetitions is wrong. Can some body correct it with the right formula from http://en.wikipedia.org/wiki/Multiset_coefficient#Counting_multisets.
--Raghu (talk) 13:51, 23 May 2013 (UTC)
- We can't talk about correctness of the equation without also talking about the definitions of the terms which appear in those equations. A few quick tests show that both the equation on the page for combinations and some of the wikipedia expressions are using different definitions from what would be appropriate for the "3" and "5" used in the initial example for this task. For example, if we look at all the combinations of five things drawn from a set of 5, we would expect only one valid combination (all of them). If we believe that 5 is n and 5 is k, we come up with 11 factorial divided by 5 factorial times 6 factorial (which is a number different from 1). --Rdm (talk) 14:19, 23 May 2013 (UTC)
Dynamic programming for enumeration problems
The gain of dynamic programming for a problem asking to list all solution rather than simply count them is much less than what is suggested by claims such as "The first solution is inefficient because it repeatedly calculates the same subproblem in different branches of recursion." (Haskell) for instance. The asymptotic complexity is the same, O(number of solutions * size of solution). Lyxia (talk) 01:30, 30 April 2017 (UTC)
Formula
Strictlly speaking, combinations with repetiotions 5 of 5 give you 126 variants, just combinations give you just 1 variant Formula for comb. with repet: http://hijos.ru/wp-content/ql-cache/quicklatex-7f6e17e6e05e9a62c1188bd95ff7e8ad.gif
