Algorithm to get the number of sorted combinations?
algorithm, combinations, sorting
Solution
I fail to see how the sorting affects the result. For each possible combination with repetitions, there will be a corresponding sorted permutation.
Hence the question boils down to number of combinations of n elements taken p at a time with replacement. That is the straight forward formula, (n-1+p)C(p) = factorial(n-1+p) / (factorial(p) * factorial(n-1) )
Here is an explanation of the formula, and another one from wolfram.
Problem
Say there are "n" numbers from which we select "p" numbers (p less than n) such that the selected "p" numbers are sorted. A selected number can be repeated. How can we calculate the number of combinations we can select? For example if we have a set of numbers say {1,2,3,4,5,6} (n=6) and we are to select 3 numbers from the set (p=3) which are sorted. So we can have {1,2,3}, {1,1,2}, {2,3,6}, {4,5,5}, {5,5,5} ........ Since all of these combinations are sorted they are valid. How can we find the number of such sorted combinations we can get? What I mean from the word sorted, is that when we select p elements from a set of numbers of n elements, the selected p elements should be sorted. Take this small example: If the set is `{1,2,3,4}` (so n = 4) and we are to select 3 elements (p = 3), the number of ways we can select p elements (with replacement) will be `4*4*4=64`. So the selections will have `{1,1,1},{1,1,2},{1,1,3}{1,1,4},{1,2,1}.....{3,1,1}...{4,4,4}`. But in these selections, not all are sorted. In this example, `{1,2,1}` and `{3,1,1}` are not sorted. I want to get the number of sorted selections. Thanks.