Determine whether a symbol is part of the ith comb

问题:

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.codeproject.com/Articles/21335/Combinations-in-C-Part-2

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...  

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  

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  

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

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 for 0th symbol, 1 for 1st symbol....etc)

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   

The 6th comb would then be 0 2 0

I need something similar but with repition not allowed.

Thank you for following this question this far :]
Kevin.

回答1:

I believe your problem is that of unranking combinations or subsets.

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}

Yielding the 6th (indexing from 0) length-3 combination of set {0, 1, 2, 3, 4}.

回答2:

There's a very efficient algorithm for this problem, which is also contained in the recently published:
Knuth, The Art of Computer Programming, Volume 4A (section 7.2.1.3).

Since you don't care about the order in which the combinations are generated, let's use the lexicographic order of the combinations where each combination is listed in descending order. Thus for r=3, the first 11 combinations of 3 symbols would be: 210, 310, 320, 321, 410, 420, 421, 430, 431, 432, 510. The advantage of this ordering is that the enumeration is independent of n; indeed it is an enumeration over all combinations of 3 symbols from {0, 1, 2, …}.

There is a standard method to directly generate the ith combination given i, so to test whether a symbol s is part of the ith combination, you can simply generate it and check.

Method

How many combinations of r symbols start with a particular symbol s? Well, the remaining r-1 positions must come from the s symbols 0, 1, 2, …, s-1, so it's (s choose r-1), where (s choose r-1) or C(s,r-1) is the binomial coefficient denoting the number of ways of choosing r-1 objects from s objects. As this is true for all s, the first symbol of the ith combination is the smallest s such that

∑_k=0^s(k choose r-1) ≥ i.

Once you know the first symbol, the problem reduces to finding the (i - ∑_k=0^s-1(k choose r-1))-th combination of r-1 symbols, where we've subtracted those combinations that start with a symbol less than s.

Code

Python code (you can write C(n,r) more efficiently, but this is fast enough for us):

#!/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)

Note how fast this is: it finds the 10000000000000000000000000000000000000000000000000000000000000000th combination of 500 letters (it starts with 542) in less than 0.5 seconds.

回答3:

I have written a class to handle common functions for working with the binomial coefficient, which is the type of problem that your problem falls under. It performs the following tasks:

1. Outputs all the K-indexes in a nice format for any N choose K to a file. The K-indexes can be substituted with more descriptive strings or letters. This method makes solving this type of problem quite trivial.

2. Converts the K-indexes to the proper index of an entry in the sorted binomial coefficient table. This technique is much faster than older published techniques that rely on iteration. It does this by using a mathematical property inherent in Pascal's Triangle. My paper talks about this. I believe I am the first to discover and publish this technique, but I could be wrong.

3. Converts the index in a sorted binomial coefficient table to the corresponding K-indexes.

4. Uses Mark Dominus method to calculate the binomial coefficient, which is much less likely to overflow and works with larger numbers.

5. The class is written in .NET C# and provides a way to manage the objects related to the problem (if any) by using a generic list. The constructor of this class takes a bool value called InitTable that when true will create a generic list to hold the objects to be managed. If this value is false, then it will not create the table. The table does not need to be created in order to perform the 4 above methods. Accessor methods are provided to access the table.

6. There is an associated test class which shows how to use the class and its methods. It has been extensively tested with 2 cases and there are no known bugs.

To read about this class and download the code, see Tablizing The Binomial Coeffieicent.

This class can easily be applied to your problem. If you have the rank (or index) to the binomial coefficient table, then simply call the class method that returns the K-indexes in an array. Then, loop through that returned array to see if any of the K-index values match the value you have. Pretty straight forward...