Алгоритм генерации сочетаний

stm7583298

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

Dasar

Рекурсивные алгоритмы - гадость, используй лучше лексикографические.

alexkravchuk

Такое подойдёт? В STL есть аналог, а это я когда-то писал...



#include <stdio.h>

///////////////////

template <class T> int my_next_permutation(T *mass, int sz)

{

int a,b,c,d;

T ttt, tc;

//   Ищем такой последний из элементов, что его значение

// меньше последующего. 

for(a=sz-2;  a>=0 && mass[a]>=mass[a+1];  a--);

//   Массив отсортирован, дальше переставлять уже некуда.

if(a<0) return 0;

//   Записываем в c номер найденого элемента, а в tc -

// значение этого элемента.

c=a;

tc=mass[a];

//   Ищем среди элементов, следующих за c, элемент,

// наименьший по значению среди больших чем tc. Используем,

// что хвост отсортирован по убыванию. Также помним, что

// такой элемент обязательно существует.

for(a=sz-1; mass[a]<=tc;  a--);

//  меняем местами найденый элемент и элемент c

mass[c]=mass[a];

mass[a]=tc;

//  Меняем упорядоченность хвоста с убывания на возрастание

for(b=c+1, d=sz-1;  b<d;  b++,d--)

   { ttt=mass[b];  mass[b]=mass[d]; mass[d]=ttt; }

//  Перестановка успешно произведена.

return 1;

}

///////////////////

void main(void)

{

int mmm[4]={1,1,3,4};

int a,b;

while (my_next_permutation(mmm,4 

     printf("\n%d%d%d%d",mmm[0],mmm[1],mmm[2],mmm[3]);

}

//////////////////////

Dasar

каждый символ можно считать уникальным? или необходимо учитывать, что один и тот же символ несколько раз встречается в подмножествах?

stm7583298

Насколько я понял, это алгоритм генерации перестановок, а не сочетаний. Но все равно спасибо

Видимо, придется мне применять лексикографический алгоритм дважды, сначала для каждого из подмножеств, а потом для полученных массивов... уф... видимо, уже не сегодня

stm7583298

Символ (а точнее число) является уникальным только внутри подмножества.
Сами подмножества вида a{1,2,3,4...50}, b{1,2,3,4,...20}, и т.д.

alexkravchuk

Поясни на каком-нибудь примере, что тебе нужно найти...

stm7583298

Например, если есть 2 массива, А[1..50] и B[1..20], нужно найти все сочетания 2-х элементов из A и 3-х из B, т.е. от [a1,a2,b1,b2,b3] до [a49,a50,b18,b19,b20].

Dasar

И в чем проблема?
перебираешь все подмножества размера 2 из A, далее перебираешь все подмножества размера 3 из Б.

stm7583298

Пасиб, уже разобрался

А проблема была в том, что я тупил, как сделать для произвольных размеров подмножеств и произвольного числа массивов

alexkravchuk

Тогда проще всего поступить так:
1) получить все перестановки относительно a,b без индексов, пусть их будет N штук (10 в данном примере)
2) получить все перестановки внутри A,B , пусть число таких будет Ma(50*49/2 Mb(20*19*18/6)
Тогда итоговая функция перестановки будет принимать 3 параметра, координату общей перестановки от 0 до N-1, и координаты частных перестановок Ma, Mb. После этого, она строит первую перестановку, смотрит первый встречающийся элемент a, подставляет из массива перестановки Ma соответствующий элемент, ищет следующий, и т.д. Ну понятно, в общем... Как раз то, что ты и описал, только поправка - если внутри классов Ma, Mb нет дублирующихся элементов, то тот алгоритм перестановок использовать не нужно, нужно сразу по номеру перестановки генерировать. Так значительно проще и удобнее.
PS: все, вижу, что уже не актуально...

Оставить комментарий