Anonymous user
Talk:Combinations: Difference between revisions
→Dynamic programming for enumeration problems: new section
(→Dynamic programming for enumeration problems: new section) |
|||
Line 5:
: 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). --[[User:Rdm|Rdm]] ([[User talk: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).
| |||