确定一个符号是否是第 i 个组合 nCr 的一部分

Question

更新： 组合学和取消排名最终是我所需要的。 下面的链接有很大帮助：

http://msdn .microsoft.com/en-us/library/aa289166(v=vs.71).aspx

http://www.codeproject.com/Articles/21335/Combinations-in-C-Part-2

问题
给定一个包含 N 个符号的列表，例如 {0,1,2,3,4...}
以及这些的 NCr 组合，

例如。 NC3 将生成：

0 1 2  
0 1 3  
0 1 4  
...  
...  
1 2 3  
1 2 4  
etc...  

对于第 i 个组合 (i = [1 .. NCr])，我想确定符号是否是其中的一部分。
Func(N, r, i, s) = True/False 或 0/1
例如。从上面继续 第一个组合包含 0 1 2 但不包含 3

F(N,3,1,"0") = TRUE  
F(N,3,1,"1") = TRUE  
F(N,3,1,"2") = TRUE  
F(N,3,1,"3") = FALSE  

可能有帮助或相关的当前方法和技巧。
与矩阵的关系 对于 r = 2 例如。 4C2 组合是 2D 矩阵的上半部分（或下半部分）

    1,2 1,3 1,4  
    ----2,3 2,4  
    --------3,4  

对于 r = 3，它是 3D 矩阵或立方体的角 对于 r = 4 它是 4D 矩阵的“角”，依此类推。

另一种关系
理想情况下，解决方案的形式应类似于以下答案： 根据位置计算组合

长度为 r 的组合列表中的第 n 个组合（其中允许重复），可以计算第i个符号
使用整数除法和余数：

n/r^i % r = (0 表示第 0 个符号，1 表示第 1 个符号....等)

例如，对于 3 个符号的第 6 个梳，第 0 个、第 1 个和第 2 个符号是：

i = 0 => 6 / 3^0 % 3 = 0   
i = 1 => 6 / 3^1 % 3 = 2   
i = 2 => 6 / 3^2 % 3 = 0   

第 6 个梳将然后是 0 2 0

我需要类似的东西，但不允许重复。

感谢您到目前为止关注这个问题:]
凯文.

Answer 1

我相信您的问题是取消排名组合或子集的问题。

我将在 Mathematica 中为您提供一个实现，来自包 Combinatorica，但是 Google除非您熟悉语义，否则上面的链接可能是一个更好的起点。

UnrankKSubset::usage = "UnrankKSubset[m, k, l] gives the mth k-subset of set l, listed in lexicographic order."

UnrankKSubset[m_Integer, 1, s_List] := {s[[m + 1]]}
UnrankKSubset[0, k_Integer, s_List] := Take[s, k]
UnrankKSubset[m_Integer, k_Integer, s_List] := 
       Block[{i = 1, n = Length[s], x1, u, $RecursionLimit = Infinity}, 
             u = Binomial[n, k]; 
             While[Binomial[i, k] < u - m, i++]; 
             x1 = n - (i - 1); 
             Prepend[UnrankKSubset[m - u + Binomial[i, k], k-1, Drop[s, x1]], s[[x1]]]
       ]

用法如下：

UnrankKSubset[5, 3, {0, 1, 2, 3, 4}]

   {0, 3, 4}

产生集合 {0, 1, 2, 3, 4} 的第 6 个（从 0 开始索引）长度为 3 的组合。

Answer 2

对于这个问题有一个非常有效的算法，该算法也包含在最近出版的：
Knuth，计算机编程的艺术，第 4A 卷（第 7.2.1.3 节）中。

由于您不关心组合的生成顺序，因此我们使用组合的字典顺序，其中每个组合均按降序顺序列出。因此，对于 r=3，3 个符号的前 11 个组合将是：210、310、320、321、410、420、421、430、431、432、510。这种排序的优点是枚举独立于n;事实上，它是对 {0, 1, 2, …} 中 3 个符号的所有组合的枚举。

有一个标准方法可以直接生成给定i的第i个组合，因此可以测试符号s是否是的一部分第 i 个组合，您可以简单地生成它并检查。

方法

有多少种以特定符号 s 开头的 r 符号组合？好吧，剩下的 r-1 个位置必须来自 s 个符号 0, 1, 2, …, s-1，所以它是 (s 选择 r-1)，其中 (s 选择 r-1) 或 C(s,r -1) 是二项式系数，表示从 s 个对象中选择 r-1 个对象的方式数。由于这对于所有 s 都是如此，因此第 i 个组合的第一个符号是最小的 s，使得

Σ_k=0^s（k选择r-1）≥i。

一旦你知道了第一个符号，问题就简化为找到 r 的 (i - Σ_k=0^s-1(k select r-1))-th 组合-1 个符号，我们减去了那些以小于 s 的符号开头的组合。

Python代码

（你可以更有效地编写 C(n,r) ，但这对我们来说已经足够快了）：

#!/usr/bin/env python

tC = {}
def C(n,r):
    if tC.has_key((n,r)): return tC[(n,r)]
    if r>n-r: r=n-r
    if r<0: return 0
    if r==0: return 1
    tC[(n,r)] = C(n-1,r) + C(n-1,r-1)
    return tC[(n,r)]

def combination(r, k):
    '''Finds the kth combination of r letters.'''
    if r==0: return []
    sum = 0
    s = 0
    while True:
        if sum + C(s,r-1) < k:
            sum += C(s,r-1)
            s += 1
        else:
            return [s] + combination(r-1, k-sum)

def Func(N, r, i, s): return s in combination(r, i)

for i in range(1, 20): print combination(3, i)
print combination(500, 10000000000000000000000000000000000000000000000000000000000000000)

注意这有多快：它找到了第 100000000000000000000000000000000000000000000000000000000000000000 个 500 个字母的第 1000000000000000000 个组合（以542）不到 0.5 秒。

Answer 3

我编写了一个类来处理处理二项式系数的常用函数，这是您的问题所属的问题类型。它执行以下任务：

1. 以良好的格式将任意 N 选择 K 的所有 K 索引输出到文件中。 K 索引可以替换为更具描述性的字符串或字母。这种方法使得解决此类问题变得非常简单。

2. 将 K 索引转换为排序二项式系数表中条目的正确索引。该技术比依赖迭代的旧发布技术要快得多。它通过使用帕斯卡三角形固有的数学属性来实现这一点。我的论文谈到了这一点。我相信我是第一个发现并发布此技术的人，但我可能是错的。

3. 将排序二项式系数表中的索引转换为相应的 K 索引。

4. 使用Mark Dominus方法来计算二项式系数，这种方法不太可能溢出并适用于更大的数字。

5. 该类是用 .NET C# 编写的，并提供了一种使用通用列表来管理与问题相关的对象（如果有）的方法。该类的构造函数采用一个名为 InitTable 的布尔值，当该值为 true 时，将创建一个通用列表来保存要管理的对象。如果该值为 false，则不会创建该表。执行上述 4 种方法不需要创建该表。提供了访问器方法来访问表。

6. 有一个关联的测试类，它显示了如何使用该类及其方法。它已经通过 2 个案例进行了广泛的测试，没有已知的错误。

要了解此类并下载代码，请参阅制表二项式系数。

此类可以轻松应用于您的问题。如果您有二项式系数表的排名（或索引），则只需调用返回数组中的 K 索引的类方法即可。然后，循环访问返回的数组以查看是否有任何 K 索引值与您拥有的值匹配。非常简单...