根据位置计算组合

Question

我有这样的组合：

1,2,3,4 //index 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

似乎您想要查找给定数字的 k 组合。

按照示例，以下是应该有效的内容：

#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)，并将字符串解析为整数 (boost::lexical_cast)。

Answer 2

下面是 Mathematica 中的一个实现，来自 Combinatorica 包。语义相当通用，所以我认为它很有帮助。如果您需要任何解释，请发表评论。

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]]]
       ]

用法如下：

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

   {1, 2, 3, 5}

正如您所看到的，该函数在集合上运行。

---

下面是我尝试解释上面的代码。

UnrankKSubset 是一个具有三个参数的递归函数，称为 (m, k, s)：

1. m 是一个整数，是按字典顺序排列的组合的“排名”，从零开始。
2. k 一个整数，每个组合中的元素数量
3. s 一个列表，从中组装组合的元素

递归有两个边界条件：

1. 对于任何排名m，以及任何列表s，如果每个组合k中的元素数量为1，则：

   返回列表s的m + 1元素，它本身在列表中。

   (+ 1 是必需的，因为 Mathematica 从 1 开始索引，而不是从零开始。我相信在 C++ 中这将是 s[m] )

2. 如果排名 m 是 0 那么对于任何 k 和任何 s：

   返回 s

   的前 k 个元素

主递归函数，对于除上面指定的：

局部变量：(i, n, x1, u)

二项式 是二项式系数： Binomial[7, 5] = 21

执行：

i = 1
n = Length[s]
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]]
]

即“前置”列表 sx1 元素code> （记住 Mathematica 索引从 1 开始，所以我相信这将是 C++ 中的 x1 - 1 索引）到递归调用 UnrankKSubset 函数返回的列表，参数为：

• m - u + Binomial[i, k]
• k - 1
• Drop[s, x1]

Drop[s, x1] 是其余的列表 s 中删除了第一个 x1 元素。

---

如果以上任何内容无法理解，或者如果您想要的是算法的解释，而不是代码的解释，请发表评论，我会再试一次。