Получение конкретных комбинаций

Обновить

April 2019

Просмотры

110 раз

1

Дано множество Integer, {х | 1 <= х <= п}. Рассмотрим сочетание, что-то вроде 50C6 (выбрать 6 из 50). Расчет количества комбинаций и итерацию над ними (в отсортированном порядке) легко.

Например, это делает трюк:

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);
    }
}

Для приведенного выше, вызывая комбо (новый INT [] {0, 0, 0, 0}, 0, 1, 9) будут перечислены все 9C4 комбинации в отсортированном порядке, все 126 из них.

То, что я хотел бы в следующем. Учитывая к, я хотел бы алгоритм, чтобы дать комбинацию.

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

Например, комбинированный (3,2,1) должен возвращать {1,2} и комбо (3,2,3) должен возвращать {2,3} (при условии, первая комбинация является 1, а не 0 - но это тривиально).

Делать это в O (Ncr) проста и занимает мало памяти ... Делать это в O (1) также легко, но это требует много памяти для больших комбинаций и требует предварительного расчета. Я не знаю, можно ли сделать это в лучшее время, чем O (Ncr) без использования таблицы поиска. Любое подтверждение / руководство будет оценено.

2 ответы

0

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

1

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.