Блог пользователя RodionGork

Сочетания с ограниченными повторениями
Автор RodionGork, 10 лет назад, По-русски

Как генерировать сочетания K элементов из N при условии что среди исходного множества некоторые элементы одинаковы? Например:

[1, 1, 2, 3, 3, 3]
по 3
[1, 1, 2]
[1, 1, 3]
[1, 2, 3]
[1, 3, 3]
[2, 3, 3]
[3, 3, 3]

Несколько неуклюжий алгоритм можно вывести из обычной генерации сочетаний без повторений, однако "неуклюжесть" смущает и интересно есть ли другой путь. К сожалению "сочетания с повторениями" по интернетам в основном дают ссылки на несколько другую трактовку задачи, если я правильно понял, с произвольным количеством повторений для каждого элемента.

В общем, буду рад ссылкам / намёкам.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

Вру.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

А в чём неуклюжесть? Просто во время того, как хотите поставить очередной элемент, ещё перебрать, сколько этих элементов сразу поставить подряд. Всё остальное так же.

→ Ответить
»
10 лет назад, # |
← Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

Как и с обычными сочетаниями, достаточно реализовать фукнцию "следующее сочетание". Сочетание с ограничеными повторениями будем хранить как массив x[], к котором записано, сколько раз каждое число встречается, причём сумма всех чисел равна k (так же как и в обычных сочетаниях, только в обычных сочетаниях любой x[i] от 0 до 1, а здесь — от 0 до определённого числа d[i]).

Давайте найдём лексикографически следующее сочетание. Для этого надо найти ближайший к концу элемент, который можно увеличить на 1 (то есть, максимальное i такое, что x[i] < d[i], и хотя бы для какого-то j>i выполнено x[j] > 0) и сделать x[i]++. Ну а потом надо хвост массива сделать лексикографически минимальным. Пусть m — максимальное из встречающихся чисел, а sum — сумма всех x[j] для j>i (с учётом нового значения x[i]). Тогда делаем так:

for (int j = m; j > i; j--) {
    int t = min(sum, d[j]);
    x[j] = t;
    sum -= t;
}

Естественно, множество надо для начала сжать. Тогда амортизированное время одного выполнения функции next() будет O(1).

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Как и с обычными сочетаниями, достаточно реализовать фукнцию "следующее сочетание"

    Ну да, эту вот функцию я и имел в виду "неуклюжей" :)

    Но спасибо, конечно — действительно не так она и страшна, и альтернатив вроде не нашлось. :)

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Why not to use bitmasks?

Easily you can generate all possible subsets and work only with the subsets containing exactly k elements.

If you don't want to generate unnecessary subsets, I provide you a nice code I found in topcoder forums:

int next(int x) {
		int y = x + Integer.lowestOneBit (x);
		x = x & ~y;
		while ((x & 1) == 0)
			x >>= 1;
		x >>= 1;
		return y | x;
}

next(x) returns the next integer > x with the same number of bits turned on in O(logN).

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

ur problem can be reduced to the following:

given a vector (a1, a2, ... an), find the number of vectors (b1, b2, ... bn) such that:

  • 0 ≤ bi ≤ ai
  • b1 + b2 + ... + bn = k

on hindsight this looks to be solvable using dynamic programming, but i'm not very sure.

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Use backtracking, with an element, decide how many will it be appeared.

n=6, k=3;
b[] = {1, 2, 3}; // suppose that one-based
Count[] = {2, 1, 3};
int a[k]; // we build own array here

void backtrack(int u, int x){ // building a[u], use b[x..n]
    if (u==k+1) {
        cout << a[0] << a[1] << ... << a[k] << endl;
        return;
    }
    if (Count[x]) { // choose b[x]
        a[u]=b[x];
        Count[x]--;
        backtrack(u+1, x);
        Count[x]++;
    }
    backtrack(u, x+1);
}

Call backtrack(1, 1). All arrays above are one-based.

→ Ответить