algorithm - 获得特定的替换组合

Question

我知道如何计算一次取k的n个不同对象的组合总数，并进行替换：
（N+K-1）！/K！/（n-1）！
我需要的是一个公式或算法来从有序列表中恢复第i个这样的组合。
假设我有一个a，b，c的所有组合的有序列表，每次取3（所以n=3，k=3）：
1 aaa级
2个aab
3个AAC
4 abb公司
5 ABC
6行政协调会
7亿桶
8英国广播公司
公元前9年
10立方厘米
我如何计算这个列表中的第i个（比如说第7个）组合，而不首先枚举它们？如果我只对一些特定的组合感兴趣的话，枚举对于除了最简单的情况以外的任何情况都是非常低效的。例如，有119877472个组合，其中64个项目一次取6个。
不用说，我需要一个任意n，k和i的解。
反向函数（给定组合，如何计算其索引）也很有趣。
我发现了一个类似的问题，但它是关于排列，而不是组合：
I want to get a specific combination of permutation?
有很多方法可以列出所有的组合，比如这里提到的：
How to generate all permutations and combinations with/without replacement for distinct items and non distinct items (multisets)
但他们没有提供我需要的功能

Answer 1

你感兴趣的算法很容易实现。首先你应该明白为什么c（k，n+k-1）=c（n-1，n+k-1）=（n+k-1）！/K！/（n-1）公式有效。公式表明，从n中取出k项的方法与从n中取出n-k项的方法相同。
假设你的物体是某种颜色的球。从1到n有n种不同的颜色。你需要计算出有k个球的方法的数目。想象一下最初k个白色的球（没有任何颜色），所以你需要用不同的方式画它们。把球排成一排从左边选择一些k1≥0的球涂成颜色1，然后选择k2≥0的球涂成颜色2，依此类推我们有∑ki=k。一系列涂有1颜色的k1球，然后是2颜色的k2球，接着是3颜色的k3球，等等……
不过，我们可以用稍微不同的方式画同一幅画。为了分离ki-1-和ki-色球，我们将使用分隔符。总的来说，我们应该在球之间放置n-1这样的分隔符。分隔符是有序的，一个分隔1色和2色球的分隔符应该出现在另一个分隔2色和3色球的分隔符之前如果某些ki=0，则相应的分隔符将逐个出现。我们必须以某种方式排列分隔符和球。
有趣的是，现在我们可以想象N-1分隔符和K球都只是最初放置在一行中的对象。我们必须选择n-1来声明所选对象是分隔符，或者k对象是球。这就是著名的组合公式可以应用的地方。
您的案例示例：
o-球
.-分隔符
a, b, c-颜色
我们有：
ooo.. => aaa
oo.o. => aab
oo..o => aac
o.oo. => abb
o.o.o => abc
o..oo => acc
.ooo. => bbb
.oo.o => bbc
.o.oo => bcc
..ooo => ccc
注意分隔符如何从右向左移动的模式。
算法
现在讨论如何得到p-th安排的问题。下面是有效的算法描述。记住我们有k个球和nd=n-1分隔符我们将一个接一个地放置分隔符，首先尝试它们最右边的位置考虑将当前分隔符保留在其当前位置，计算将剩余对象放在右侧的组合数，让该数为N。将N与p比较，如果p大于或等于N，则将p减少N（p <- p - N），我们应将当前分隔符左移1否则，如果p小于n，则我们将不移动当前分隔符，而是继续下一个分隔符，尝试从最右边的位置再次移动它。注意p-th排列是基于零的。
将第i个对象“转换”为第j个分隔符后，我们有N=C（nd-j，nd+k-i）多种方法来排列剩余的k-i+j球和nd-j分隔符。
因为我们经常提到二项式系数，所以最好对它们进行预计算。
可相应地实现反向功能。每个分隔符都有位置累积将普通分隔符从最右边移动到其位置时排列剩余对象的方法数。
例子：
3球，2分隔符，查找7-th排列（即bbc或.oo.o）
将分隔符放在最右边的位置：ooo..让第一个分隔符为当前值。
计算n=c（1，1）=1，p≥n，我们用n减去p，得到p=6。同时，我们将当前分隔符左移1个位置，得到oo.o.。
计算n=c（1，2）=2，p≥n，用n减去p，得到p=6-2=4。移动gettingo.oo.。
再次计算n=c（1，3）=3，p≥n，移动并减小p，得到p=1且.ooo.。
计算n=c（1，4）=4，p 计算n=c（0,0）=1，p≥n，p=1-1=0，移动， .oo.o。
计算n=c（0,1）=1，p .oo.o=> bbc。
编辑1.更改了算法描述并添加了示例。