Generate kth combination without generating/iterating previous

Question

Given a set of items, for example:

[ 1, 2, 3, 4, 5, 6 ]

I'd like to generate all possible combinations of a certain length with repetition. The twist is I'd like to start at a predetermined combination (a sort of offset into the list of combinations).

For example, starting with this:

[ 1, 5, 6 ]

The first (next) combination would be:

[ 1, 6, 6 ]

I've had success using itertools.combinations_with_replacement() to generate the combinations, but the project this is for will require working with a set that generates way too many combinations - creating them all first and iterating to the correct point is not possible.

I've found this example for generating kth combination which doesn't seem to be working very well for me. This answer seemed another possibility, but I can't seem to port it from C to Python.

Here's my code so far using the kth combination example:

import operator as op
items = [ 1,2,3,4,5,6 ]

# https://stackoverflow.com/a/4941932/1167783
def nCr(n, r):
    r = min(r, n-r)
    if r == 0: 
        return 1
    numer = reduce(op.mul, xrange(n, n-r, -1))
    denom = reduce(op.mul, xrange(1, r+1))
    return numer // denom

# https://stackoverflow.com/a/1776884/1167783
def kthCombination(k, l, r):
    if r == 0:
        return []
    elif len(l) == r:
        return l
    else:
        i = nCr(len(l)-1, r-1)
        if k < i:
            return l[0:1] + kthCombination(k, l[1:], r-1)
        else:
            return kthCombination(k-i, l[1:], r)

# get 1st combination of 3 values from list 'items' 
print kthCombination(1, items, 3)

# returns [ 1, 2, 4 ]

Any help would be great!

Centijo · Answer 1 · 2013-09-02T14:13:13.517

If you assume that all values in the array are digits in a base-n numbering system where n is the length of the array, the k-th combination will be the equivalent of k expressed in base-n.

If you are wanting to start with a given combination (i.e. [1,6,5]) and continue from there, simply read this starting point as a number in base-n. You can then start iterating through successive combinations by incrementing.

EDIT: Further explanation:

Let's start with the array. The array contains 6 values, so we are working in base-6. We will assume the index of each element in the array is the element's base-6 value.

Values in base-6 range from 0 to 5. This may get confusing because our example uses digits, but we could do this with combinations of anything. I will put 'quote' marks around the digits we are combining.

Given a combination ['1', '6', '5'], we first need to convert this to a base-6 value. '1' becomes 0, '6' becomes 5 and '5' becomes 4. Using their positions in the starting value as their powers in base-6, we get:

(0 * 6^0) + (5 * 6^1) + (4 * 6^2) = 174 (decimal)

If we want to know the next combination, we can add 1. If we want to know 20 combinations ahead, we add 20. We can also subtract to go backwards. Let's add 1 to 174 and convert it back to base-6:

175 (decimal) = (1 + 6^0) + (5 * 6^1) + (4 * 6^2) = 451 (base-6) = ['2', '6', '5'] (combination)

For more on number bases, see http://en.wikipedia.org/wiki/Radix and http://en.wikipedia.org/wiki/Base_%28exponentiation%29

As mentioned in the answer by Mario Rossi, my math isn't so good and I'm having trouble following this. Is this answer essentially the same as Mario's? — JeffThompson, Aug 30 '13 at 11:32
My answer is a general case for finding permutations. Mario's answer is specific to itertools. — Centijo, Sep 02 '13 at 01:08

score 2 · Accepted Answer · answered Aug 30 '13 at 01:49

2

Instead of inventing the wheel time number 37,289,423,987,239,489,826,364,653 (that's counting only human beings), you can map the numbers. itertools will return first combination [1,1,1], but you want [1,5,6]. Simply add [0,4,5] mod 6 to each position. You can also map back and forth between numbers, objects, and modulo, of course.

This works even if the number of elements in each position is different.

You will have more fun with what you started, though.

answered Aug 30 '13 at 01:49

Mario Rossi

7,651
27
37

because of the quadratic complexity? – pqnet Aug 30 '13 at 01:58
@pqnet According to the OP, the twist is starting at a predetermined combination, not performance. Besides, permutation generation is not cuadratic as you say, but n^m. Problem is, that's not the size of the **solution**, that's the size of the **problem**. In other words, the "N" of our problem is really n^m. From this point of view, all permutation-generation algorithms are really O(1) (or very close to it). – Mario Rossi Aug 30 '13 at 02:17
@pqnet Now, if you proposed me a problem with parameters `n` and `m` and in my solution I said "we need to generate these combinations/permutations", then yes: **my algorithm** in relation to **that problem** would be `n^m`. – Mario Rossi Aug 30 '13 at 02:20
since all the permutations are actually n^m it wouldn't be possible to generate them in a shorter time than it takes to print them out – pqnet Aug 30 '13 at 02:24
Interesting solution - my math is a bit too rusty to follow the comments here :) In simplified terms, the idea is to add the offset (starting) combination to the first combination (for example `[ 1, 1, 1 ]` and continue from there? I assume one would 'wrap around' where 7 = 0, etc? – JeffThompson Aug 30 '13 at 11:30

Generate kth combination without generating/iterating previous

2 Answers2

Linked