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

Question

我如何从所有可能的组合中得到N布局，将4个不可区分的球排列在3个不同的桶中。如果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。

第一个arrangement(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

序列的最大项数为(Bl+Bk-1)C(Bk-1)，其中C是组合算子/组合算子。Obtained from https://en.m.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

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

Answer 2

有一些有趣的双射可以做。最后，我们可以使用排序和非排序的方法对规则的k-组合，这是比较常见的知识。

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

下面是一些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]
"""