小编典典

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

algorithm

更新:我最终需要组合和排序。以下链接提供了很多帮助:

http://msdn.microsoft.com/zh-
CN/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

第六梳将是0 2 0

我需要类似的东西,但不允许有声望。

到目前为止,谢谢您提出这个问题:]
凯文。


阅读 346

收藏
2020-07-28

共1个答案

小编典典

我相信您的问题是组合或子集的排序问题。

我将通过 Combinatorica
包为您提供Mathematica的实现,但是除非您熟悉语义,否则上面的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组合。

2020-07-28