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

Question

Do you know any way to get the kth element of a combination of m-elements in O (1)? The expected solution should work for any input size and any value of m.

Let me explain this problem with an 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 data The k-th (2nd in this example) element of the combination of m-elements abd . Is this possible (abd) without creating the entire combinational list?

I ask because I have data of ~ 1 000 000 characters, and it is impossible to create a complete combinatorial list of m-character length to get the k-th element.

The solution may be a pseudo-code or a link to a page describing this problem (unfortunately, I did not find it).

Thanks!

Answer 1

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

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

Answer 2

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

Take the source combination 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 lengths, we have n!/(nm)!m! complete combinations. We can use this fact to go 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) 

Answer 3

first compute r = !n/(!m*!(nm)) with n number of elements

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

delete it (slide everything to the left)

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

and repeat until m becomes 0 (hint when k is 0, just copy the following characters into the result)

Answer 4

I wrote a class to handle common functions for working with the binomial coefficient, which is the type of problem your problem gets into. It performs the following tasks:

• Prints all K-indices in a good format for any N that selects K to a file. K-indices can be replaced with more descriptive strings or letters. This method allows you to solve this type of problem is quite trivial.

• Converts K-indices to the corresponding record index in the table of sorted binomial coefficients. This method is much faster than older published iteration-based methods. He does this using the mathematical property inherent in the Pascal Triangle. My article talks about this. I believe that I am the first to discover and publish this technique, but I could be wrong.

• Converts an index into a sorted table of binomial coefficients into the corresponding K-indices. I believe this is also faster than other published methods.

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

• The class is written in .NET C # and provides a way to manage the objects associated with the problem (if any) using a common list. The constructor of this class takes a bool value called InitTable, which, when true, will create a general list for storing objects to be managed. If this value is false, then it will not create a table. You do not need to create a table to complete the methods described above. To access the table, access methods are provided.

• There is a related test class that shows how to use the class and its methods. It has been extensively tested with 2 cases and there are no known errors.

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

You cannot convert this class to Java, Python, or C ++.