Calculate Combination based on position

I 开发者_高级运维have combinations like this:

1,2,3,4 //index 0

1,2,3,5 //index 1

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

myCmb = func(index)

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: http://answers.yahoo.com/question/index?qid=20110320070039AA045ib

I want now reverse this...

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

It seems like you want to find the k-combination for a given number.

Following the example, 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 Boost 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 Combinatorica. 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}]

   {1, 2, 3, 5}

As you can see this function operates on sets.

Below is my attempt to explain the code above.

UnrankKSubset is a recursive function with three arguments, called (m, k, s):

1. m an Integer, the "rank" of the combination in lexigraphical order, starting from zero.
2. k an Integer, the number of elements in each combination
3. s a List, the elements from which to assemble combinations

There are two boundary conditions on the recursion:

1. 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] )

2. if rank m is 0 then for any k and any s:

   return the first k elements of s

The main recursive function, for any other arguments than ones specified above:

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]
• k - 1
• Drop[s, x1]

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.