Question:

I have combinations like this:

1,2,3,4 //index 0<br /> 1,2,3,5 //index 1<br /> 1,2,3,6 //index 2

and so on until 7,8,9,10

So this will be n=10 k=4 from combinatorics

How calculate combination by index

For example when my index==1<br /> myCmb = func(index)<br /> returns 1,2,3,5

this is example i need this for bigest numbers, and for more params and without (if this possible) many loops

i find something like this to obtain position: <a href="http://answers.yahoo.com/question/index?qid=20110320070039AA045ib" rel="nofollow">http://answers.yahoo.com/question/index?qid=20110320070039AA045ib</a>

I want now reverse this...

I programming in C++ Thanks for any sugesstions or help

Answer1:It seems like you want to <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Combinatorial_number_system#Finding_the_k-combination_for_a_given_number" rel="nofollow">find the k-combination for a given number</a>.

Following the <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Combinatorial_number_system#Example" rel="nofollow">example</a>, here's something that should work:

```
#include <cstddef>
#include <iostream>
#include <string>
#include <boost/lexical_cast.hpp>
#include <boost/math/special_functions/binomial.hpp>
std::size_t Choose(double n, double k) {
using boost::math::binomial_coefficient;
if (n < k) return 0;
return static_cast<std::size_t>(binomial_coefficient<double>(n, k));
}
// Returns the largest n such that Choose(n, k) <= pos.
int CombinationElement(int k, int pos) {
int n = k;
int coeff = 1, prev_coeff = 0;
while (coeff <= pos) {
coeff = Choose(++n, k);
prev_coeff = coeff;
}
return n - 1;
}
// Returns an k-combination at position pos.
std::vector<int> Combination(int k, int pos) {
std::vector<int> combination;
for (; k > 0; --k) {
int n = CombinationElement(k, pos);
combination.push_back(n);
pos -= Choose(n, k);
}
return combination;
}
int main(int argc, char** argv) {
using std::cout;
using std::endl;
if (argc != 3) {
cout << "Usage: $ " << argv[0] << " K POS" << endl;
cout << "Prints the K-combination at position POS." << endl;
return 1;
}
int k = boost::lexical_cast<int>(argv[1]);
int pos = boost::lexical_cast<int>(argv[2]);
std::vector<int> combination = Combination(k, pos);
for (int i = 0; i < k; i++)
cout << combination[i] << " ";
cout << std::endl;
}
```

Note, for convenience, the code depends on <a href="http://www.boost.org/" rel="nofollow">Boost</a> to calculate binomial coefficients (`boost::math::binomial_coefficient<T>`

), and to parse strings into integers (`boost::lexical_cast`

).

Here is an implementation in Mathematica, from the package <a href="http://www.combinatorica.com/" rel="nofollow"><em>Combinatorica</em></a>. The semantics are fairly generic, so I think it is helpful. Please leave a comment if you need anything explained.

```
UnrankKSubset::usage = "UnrankKSubset[m, k, l] gives the mth k-subset of set l, listed in lexicographic order."
UnrankKSubset[m_Integer, 1, s_List] := {s[[m + 1]]}
UnrankKSubset[0, k_Integer, s_List] := Take[s, k]
UnrankKSubset[m_Integer, k_Integer, s_List] :=
Block[{i = 1, n = Length[s], x1, u, $RecursionLimit = Infinity},
u = Binomial[n, k];
While[Binomial[i, k] < u - m, i++];
x1 = n - (i - 1);
Prepend[UnrankKSubset[m - u + Binomial[i, k], k-1, Drop[s, x1]], s[[x1]]]
]
```

Usage is like:

```
UnrankKSubset[1, 4, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}]
```

<b> {1, 2, 3, 5}</b>
As you can see this function operates on sets.

<hr />Below is my attempt to explain the code above.

<h3>UnrankKSubset is a recursive function with three arguments, called (m, k, s):</h3> <ol><li>`m`

an Integer, the "rank" of the combination in lexigraphical order, starting from zero.</li>
<li>`k`

an Integer, the number of elements in each combination</li>
<li>`s`

a List, the elements from which to assemble combinations</li>
</ol><h3>There are two boundary conditions on the recursion:</h3>
<ol><li>for any rank `m`

, and any list `s`

, if the number of elements in each combination `k`

is `1`

, then:

return the `m + 1`

element of the list `s`

, itself in a list.

(`+ 1`

is needed because Mathematica indexes from one, rather than zero. I believe in C++ this would be s[m] )

if rank `m`

is `0`

then for any `k`

and any `s`

:

return the first `k`

elements of `s`

local variables: (`i`

, `n`

, `x1`

, `u`

)

`Binomial`

is binomial coefficient: `Binomial[7, 5]`

= 21

Do:

```
i = 1
n = Length[s]
u = Binomial[n, k]
While[Binomial[i, k] < u - m, i++];
x1 = n - (i - 1);
```

Then return:

```
Prepend[
UnrankKSubset[m - u + Binomial[i, k], k - 1, Drop[s, x1]],
s[[x1]]
]
```

That is, "prepend" the `x1`

element of list `s`

(remember Mathematica indexes from one, so I believe this would be the `x1 - 1`

index in C++) to the list returned by the recursively called UnrankKSubset function with the arguments:

`m - u + Binomial[i, k]`

</li>
<li>`k - 1`

</li>
<li>`Drop[s, x1]`

</li>
</ul>`Drop[s, x1]`

is the rest of list `s`

with the first `x1`

elements removed.

If anything above is not understandable, or if what you wanted was an explanation of the algorithm, rather than an explanation of the code, please leave a comment and I will try again.