CODEWITHSUNDEEP
javaalgorithmcombinations
Jaco Van Niekerk
Jaco Van Niekerk

Reputation: 4192

Retrieving specific combinations

Given an Integer set, {x | 1 <= x <= n}. Consider a combination, something like 50C6 (select 6 from 50). Calculating the number of combinations and iterating over them (in sorted order) is easy.

For example, this does the trick:

public static void combo(int[] combo, int index, int f, int t) {
    if (index >= combo.length) {
        // display combination
        // ...
        return;
    }
    for (int i = f; i <= t - (combo.length - index) + 1; i++) {
        combo[index] = i;
        combo(combo, index + 1, i + 1, t);
    }
}

For the above, calling combo(new int[]{0, 0, 0, 0}, 0, 1, 9) will list all the 9C4 combinations in sorted order, all 126 of them.

What I would like is the following. Given k, I'd like the algorithm to give the combination.

// Select r from c and return combination k.
public static int[] combo(int c, int r, int k) {
}

For example, combo(3,2,1) should return {1,2} and combo(3,2,3) should return {2,3} (assuming the first combination is 1 and not 0 - but that's trivial).

Doing this in O(nCr) is easy and takes little memory... Doing it in O(1) is also easy, but is requires lots of memory for larger combinations and requires pre-calculation. I don't know whether it's possible to do this in better time than O(nCr) without using a lookup table. Any confirmation/guidance would be appreciated.

Upvotes: 1

Views: 157

Answers (2)

wckd
wckd

Reputation: 410

So you can find the value of nCp by the equation n!/(p!*(n-p)!). So say you're solving 4C3 and you're looking for the kth combo. If the first value is a 1 then that means that you have 3C2 left which calculates to 3. So if k < 3 the first value is a 1. If not you go to 3C2 + 3C1 for the second value. And you recuse down the line. No sure if it's actually faster (the calculation of nCp) but it's an interesting way to think about the problem.

Upvotes: 1

Jaco Van Niekerk
Jaco Van Niekerk

Reputation: 4192

Okay, I've worked it out and I am quite happy with the final result. The basic idea is as follows:

Let's say we want the k'th entry of nCr. Then, the number of combinations where we start with a 1 is (n-1)C(r-1) and a 2 is (n-2)C(r-2), etc. So, all you have to do is find out which digit needs to go at the first spot and then repeat the process for every one of the r spots.

For example, let's say we want the 30'th entry of 9C3. For 1, we have 8C2 = 28. That's not enough. For 2, 7C2 = 21. So, the first digit must be a 2 and the first entry that started with a 2 was entry 29. So now you simply repeat this process for the second and third entry.

The non-recursive solution is as follows:

public static int[] getCombo(int n, int r, int k) {
    int[] result = new int[r];
    int cur = 1;
    int sum =0;
    while (r > 0) {
        int tot = c(n - cur, r - 1);
        if (sum + tot < k) {
            sum += tot;
            cur++;
        } else {
            result[result.length - r] = cur++;
            r--;
        }
    }
    return result;
}

The function c() above, simply calculates "n select r". I particularly like this as it is O(r).

Upvotes: 1

Related Questions