如何获取组合序列中的第N个排列，反之亦然？

Question

我要如何从所有可能的将4个无法区分的球排列在3个不同桶中的组合中获取第N个排列。如果 Bl = 球的数量 和 Bk = 桶的数量，例如对于Bl = 4，Bk = 3，则可能的排列为：

004,013,022,031,040,103,112,121,130,202,211,220,301,310,400。

第一个排列（N=0）是004（即 桶1 = 0个球 ， 桶2 = 0个球 ， 桶3 = 4个球 ），最后一个（N=14）是400。所以，假设我有103，则 N 将等于 5 。我希望能够这样做

int Bl=4,Bk=3;
getN(004,Bl,Bk);// which should be = 0
getNthTerm(8,Bl,Bk);// which should be = 130

P.S: 序列中的最大项数为(Bl+Bk-1)C(Bk-1)，其中C是组合运算符。 获取自 stars and bars

注：本段内容涉及组合数学知识。

- LiNKeR

---

这些被称为整数组合，更具体地说是“受限整数组合”。我不确定如何获取第n个。 - Joseph Wood

谢谢Joseph，我会查一下的。 - linker

Answer 1

据我所知，没有比组合分解更快的方法，它大约需要O(Bl)时间。

我们只需计算选定索引下每个桶中装入的球数，逐个桶进行操作。对于每个可能的桶分配，我们计算剩余球和桶的可能排列数量。如果索引小于该数量，我们选择该排列；否则，我们将一个球放入桶中，并从索引中减去我们刚刚跳过的排列数。

以下是C语言实现。我没有在下面的实现中包括binom函数。通常最好在您感兴趣的值范围内预先计算二项式系数，因为通常不会太多。可以逐步进行计算，但这需要每一步进行乘法和除法运算；虽然这不会影响渐近复杂度，但它会使内部循环变得更慢（因为除法），并增加溢出的风险（因为乘法）。

/* Computes arrangement corresponding to index.
 * Returns 0 if index is out of range.
 */
int get_nth(long index, int buckets, int balls, int result[buckets]) {
  int i = 0;
  memset(result, 0, buckets * sizeof *result);
  --buckets;
  while (balls && buckets) {
    long count = binom(buckets + balls - 1, buckets - 1);
    if (index < count) { --buckets; ++i; }
    else { ++result[i]; --balls; index -= count; }
  }
  if (balls) result[i] = balls;
  return index == 0;
}

- rici

---

@mbo：或者 count = binom(... :). 我还错过了index -= count.现在我已经测试了一下，它似乎按照广告所述工作。谢谢。 - rici

Answer 2

有一些有趣的双射可以被制作。最后，我们可以使用排名和非排名方法来处理常见的正则k组合。

1. 每个桶中球数到选择桶的有序多重集的双射; 例如：[3, 1, 0] --> [1, 1, 1, 2]（三个1和一个2的选择）。
2. 从具有重复的{1...n}的k子集到不重复的{1...n + k − 1}的k子集的双射，通过将{c_0, c_1...c_(k−1)}映射到{c_0, c_(1+1), c_(2+2)...c_(k−1+k−1)}（参见here）。

这是一些Python代码：

from itertools import combinations_with_replacement

def toTokens(C):
  return map(lambda x: int(x), list(C))

def compositionToChoice(tokens):
  result = []
  for i, t in enumerate(tokens):
    result = result + [i + 1] * t
  return result

def bijection(C):
  result = []
  k = 0
  for i, _c in enumerate(C):
    result.append(C[i] + k)
    k = k + 1
  return result

compositions = ['004','013','022','031','040','103','112',
                '121','130','202','211','220','301','310','400']

for c in compositions:
  tokens = toTokens(c)
  choices = compositionToChoice(tokens)
  combination = bijection(choices)
  print "%s  -->  %s  -->  %s" % (tokens, choices, combination)

输出：

"""
[0, 0, 4]  -->  [3, 3, 3, 3]  -->  [3, 4, 5, 6]
[0, 1, 3]  -->  [2, 3, 3, 3]  -->  [2, 4, 5, 6]
[0, 2, 2]  -->  [2, 2, 3, 3]  -->  [2, 3, 5, 6]
[0, 3, 1]  -->  [2, 2, 2, 3]  -->  [2, 3, 4, 6]
[0, 4, 0]  -->  [2, 2, 2, 2]  -->  [2, 3, 4, 5]
[1, 0, 3]  -->  [1, 3, 3, 3]  -->  [1, 4, 5, 6]
[1, 1, 2]  -->  [1, 2, 3, 3]  -->  [1, 3, 5, 6]
[1, 2, 1]  -->  [1, 2, 2, 3]  -->  [1, 3, 4, 6]
[1, 3, 0]  -->  [1, 2, 2, 2]  -->  [1, 3, 4, 5]
[2, 0, 2]  -->  [1, 1, 3, 3]  -->  [1, 2, 5, 6]
[2, 1, 1]  -->  [1, 1, 2, 3]  -->  [1, 2, 4, 6]
[2, 2, 0]  -->  [1, 1, 2, 2]  -->  [1, 2, 4, 5]
[3, 0, 1]  -->  [1, 1, 1, 3]  -->  [1, 2, 3, 6]
[3, 1, 0]  -->  [1, 1, 1, 2]  -->  [1, 2, 3, 5]
[4, 0, 0]  -->  [1, 1, 1, 1]  -->  [1, 2, 3, 4]
"""

- גלעד ברקן