algorithm - 确定一个符号是否是第 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])我想判断一个符号(s)是否是其中的一部分。
Func(N, r, i, s) = 真/假或 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 组合是二维矩阵的上(或下)一半

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

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

另一种关系
理想情况下，解决方案的形式类似于以下问题的答案: Calculate Combination based on position

长度为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

我相信你的问题是 unranking combinations或子集。

我会给你一个 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 的组合。