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

Question

如何从将 4 个无法区分的球排列在 3 个不同的桶中的所有可能组合中得到 Nth 排列。如果 Bl = number of balls 且 Bk = number of buckets 例如对于 Bl = 4, Bk = 3 可能的排列是：

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

第一个排列(N=0)是004(即bucket 1 = 0 balls,bucket 2 = 0 balls, bucket 3 = 4 balls) 最后一个(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: max number of terms for the sequence is (Bl+Bk-1)C(Bk-1) where C is the combinatorics/combination operator. Obtained from stars and bars

Answer 1

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

我们简单地计算进入 selected 索引的每个桶的球数，一次处理一个桶。对于桶的每个可能分配，我们计算剩余球和桶的可能排列数。如果索引小于那个数，我们select那个排列；否则我们再往桶里放一个球，然后从索引中减去我们刚刚跳过的排列数。

这是一个 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;
}

Answer 2

可以进行一些有趣的双射。最后，对于正则的k-组合，我们可以使用ranking和unranking的方法，这是比较常识。

从每个桶中的球数到桶选择的有序多重集的双射；例如：[3, 1, 0] --> [1, 1, 1, 2]（三选1，一选2）。
通过将 {c_0, c_1...c_(k−1)} 映射到 [，从 {1...n} 的 k 个子集（有重复）到 {1...n + k − 1} 的 k 个子集（没有重复）的双射=16=]（参见 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]
"""

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

How to get the Nth arrangement in a Combinatoric sequence and vice-versa?

algorithm

math

combinations

sequences

combinatorics