确定一个符号是否是第i个组合NCR公司的一部分 [英] Determine whether a symbol is part of the ith combination nCr
问题描述
更新： 组合数学和unranking最终被我所需要的。 以下链接帮助了很多：
UPDATE: Combinatorics and unranking was eventually what I needed. The links below helped alot:
http://msdn.microsoft.com /en-us/library/aa289166(v=vs.71).aspx
HTTP：//www.$c$ cproject.com/Articles/21335/Combinations-in-C-Part-2
问题
给定N个符号列表表示{0,1,2,3,4 ...}
以及这些NCR的组合
The Problem
Given a list of N symbols say {0,1,2,3,4...}
And NCr combinations of these
如。第三次通报会生成：
eg. NC3 will generate:
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
例如。从上面继续
第1组合中包含0 1 2而不是3
For the ith combination (i = [1 .. NCr]) I want to determine Whether a symbol (s) is part of it.
Func(N, r, i, s) = True/False or 0/1
eg. Continuing from above
The 1st combination contains 0 1 2 but not 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
当前的方法和tibits可能帮助或与此有关。
关系矩阵
当r = 2当量。 4C2的组合是一个二维矩阵的上（或下）半
Current approaches and tibits that might help or be related.
Relation to matrices
For r = 2 eg. 4C2 the combinations are the upper (or lower) half of a 2D matrix
1,2 1,3 1,4
----2,3 2,4
--------3,4
对于3D矩阵或立方体的R = 3的角落 为R = 4它是一个四维矩阵的角等。
For r = 3 its the corner of a 3D matrix or cube for r = 4 Its the "corner" of a 4D matrix and so on.
另一个关系
理想情况下，解决方案是一种形式的类似的答案是：
计算基于位置的组合
Another relation
Ideally the solution would be of a form something like the answer to this:
Calculate Combination based on position
在的长度r的组合（与repitition允许）时，第i个符号，可以计算
列表第n个组合
使用整数除法和余数：
The nth combination in the list of combinations of length r (with repitition allowed), the ith symbol can be calculated
Using integer division and remainder:
N / R ^ I％R =（0 0号标志，1月1日的象征....等）
n/r^i % r = (0 for 0th symbol, 1 for 1st symbol....etc)
例如，用于3个符号的第0个第一和第二符号第6梳子是：
eg for the 6th comb of 3 symbols the 0th 1st and 2nd symbols are:
i = 0 => 6 / 3^0 % 3 = 0
i = 1 => 6 / 3^1 % 3 = 2
i = 2 => 6 / 3^2 % 3 = 0
第六届梳然后将0 2 0
The 6th comb would then be 0 2 0
我需要的东西类似，但与repition不允许的。
I need something similar but with repition not allowed.
感谢你为这个远远以下这个问题：]
凯文。
Thank you for following this question this far :]
Kevin.
推荐答案
我相信你的问题是，的 unranking组合或子集。
I believe your problem is that of unranking combinations or subsets.
我会给你在数学的实施，从包的 Combinatorica 的，但上方谷歌的链接可能是一个更好的地方开始，除非你是熟悉的语义。
I will give you an implementation in Mathematica, from the package Combinatorica, but the Google link above is probably a better place to start, unless you are familiar with the semantics.
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]]]
]
使用方法是这样的：
Usage is like:
UnrankKSubset[5, 3, {0, 1, 2, 3, 4}]
{0, 3, 4}
屈服的第六（索引0）组长度为3的组合{0，1，2，3，4}
Yielding the 6th (indexing from 0) length-3 combination of set {0, 1, 2, 3, 4}.
这篇关于确定一个符号是否是第i个组合NCR公司的一部分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
