如何在组合序列中得到第N个排列,反之亦然？

Question

如何在3个不同的桶中安排4个难以区分的球的所有可能组合中获得第N个排列.if 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(即铲斗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

PS:序列的最大项数是 (B1 + Bk-1)C(Bk-1)其中C是组合/组合运算符.Obtained from stars and bars

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