c++ - 根据位置计算组合

Question

我有这样的组合:

1,2,3,4//索引0
1,2,3,5//索引 1
1,2,3,6//索引 2

以此类推直到7、8、9、10

所以这将是来自组合学的 n=10 k=4

如何通过索引计算组合

例如当我的索引==1
myCmb = func(索引)
返回 1,2,3,5

这是一个例子，我需要这个来获得最大的数字，更多的参数并且没有(如果可能的话)很多循环

我找到这样的东西来获得位置: http://answers.yahoo.com/question/index?qid=20110320070039AA045ib

我现在想扭转这个...

我用C++编程感谢您的任何建议或帮助

Answer 1

看来你想要find the k-combination for a given number .

在 example 之后，这是应该起作用的东西:

#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;
}

注意，为方便起见，代码依赖Boost计算二项式系数 ( boost::math::binomial_coefficient<T> )，并将字符串解析为整数 ( boost::lexical_cast )。