Talk:Combinations: Difference between revisions
Content added Content deleted
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 |