Is it possible to get k-th element of m-character-length combination in O(1)?

Do you know any way to get k-th element of m-element combination in O(1)? Expected solution should work for any size of input data and any m value.

Let me explain this problem by example (python code):

>>> import itertools
>>> data = ['a', 'b', 'c', 'd']
>>> k = 2
>>> m = 3
>>> result = [''.join(el) for el in itertools.combinations(data, m)]
>>> print result
['abc', 'abd', 'acd', 'bcd']
>>> print result[k-1]
abd

For a given data the k-th (2-nd in this example) element of m-element combination is abd. Is it possible to that value (abd) without creating the whole combinatory list?

I'am asking because I h开发者_如何学编程ave data of ~1,000,000 characters and it is impossible to create full m-character-length combinatory list to get k-th element.

The solution can be pseudo code, or a link the page describing this problem (unfortunately, I didn't find one).

Thanks!

http://en.wikipedia.org/wiki/Permutation#Numbering_permutations

Basically, express the index in the factorial number system, and use its digits as a selection from the original sequence (without replacement).

Not necessarily O(1), but the following should be very fast:

Take the original combinations algorithm:

def combinations(elems, m):
    #The k-th element depends on what order you use for
    #the combinations. Assuming it looks something like this...
    if m == 0:
        return [[]]
    else:
        combs = []
        for e in elems:
            combs += combinations(remove(e,elems), m-1)

For n initial elements and m combination length, we have n!/(n-m)!m! total combinations. We can use this fact to skip directly to our desired combination:

def kth_comb(elems, m, k):
    #High level pseudo code
    #Untested and probably full of errors
    if m == 0:
        return []
    else:
        combs_per_set = ncombs(len(elems) - 1, m-1)
        i = k / combs_per_set
        k = k % combs_per_set
        x = elems[i]
        return x + kth_comb(remove(x,elems), m-1, k)

first calculate r = !n/(!m*!(n-m)) with n the amount of elements

then floor(r/k) is the index of the first element in the result,

remove it (shift everything following to the left)

do m--, n-- and k = r%k

and repeat until m is 0 (hint when k is 0 just copy the following chars to the result)

I have written a class to handle common functions for working with the binomial coefficient, which is the type of problem that your problem appears to fall 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. I believe it too is faster than other published techniques.

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.

It should not be hard to convert this class to Java, Python, or C++.