Печать страницы - Алгоритм генерации уникальных сочетаний C(n,k)

Господа,

Пожалуйста, помогите найти алгоритм (а лучше код) программы генерации сочетаний из n элементов по k (т.е. C(n,k)). Специфика задачи заключается в том, что среди n элементов могут быть одинаковые, а сочетания нужно получить только уникальные в смысле состава элементов (поэтому их может быть гораздо меньше, чем все C(n,k)).

К примеру, генерируя сочетания из 223 по 2, на выходе нужно получить только 22 и 23, а не 22, 23 и 23 (к чему придет общий алгоритм решения этой задачи).

Заранее благодарен.

Мдя... времени уже прошло много, так что автору ответ возможно и не понадобится, но может он поможет тем кто ищет сейчас.

Собственно, реализация алгоритма генерации следующего
уникального сочетания из N чисел по K в С:

Код:



void getNext()
{
    int i = K;

    while (C[i] + K - i + 1 > N)
        --i;

    C[i]++;

    for (int j = i + 1; j <= K; ++j)
        C[j] = C[j-1] + 1;
}

Как известно, количество таких сочетаний вычисляется по формуле:
С(N,K) = N! / (K!*(N-K)!)
Поскольку на множестве этих последовательностей определен лексикографический порядок, то для того чтобы получить все перестановки, необходимо начинать с 1, 2 ... K

Russian Qt Forum

Программирование => Алгоритмы => Тема начата: Aleksey от Июнь 27, 2004, 18:15