Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > генератор размещений

Автор: 46&two 18.2.2004, 09:26

дело так: нада налепить алгоритм, который умеет генерировать все размещения (ну или очередное размещение) N различных элементов по M (M>N) ячейкам. так, чтобы запуск этой функции в цикле выдавал каждый раз новое размещение. ясно, что если N==M, получается генератор перестановок. такого добра навалом. Генератор размещений я не нашел и, честно говоря, затрудняюсь с построением алгоритма. если у кого завалялся реализованный алгоритм (на каком языке не важно, но лучше, разумеется C), то буду очень благодарен.....

Автор: neutrino 18.2.2004, 11:55

Ну вот алгоритм рекурсивный "на вскидку" написал, если нужно именно итеративный, скажи. Цитата #include <iostream.h> // Глобальные переменные: массив ячеек, количество ячеек, количество элементов. int *a, n, k; /* Функция выпечатывает массив на экран */ void prn(void) {    for (int i=0; i<n; i++)    {        cout<<a[i]<<" ";    }    cout<<endl; } /* Функция выборки в н ячеек к элементов. */ void D(int *a, int n, int k) {     // Если ячейка последняя, то ...    if (n == 1)    {        *a = k;  // разместить в нее оставшиеся элементы;        prn(); // напечатать результат;        return; //  и выйти.    }     // Иначе перебрать возможные комбинации...    for (int j=0; j<=k; j++)    {        *a = j;         D(a+1, n-1, k-j); // и заполнить следующую ячейку с оставшимися элементами.    } } void main() {    cin>>n>>k;    a = new int[n];    D(a, n, k); }

Автор: 46&two 19.2.2004, 09:44

Да, нехило. Только не соображу, как эту функцию преобразвать к формату вида Код int D(int *a, int n, int k) которая в *a запихивает очередное размещение, а возвращает ноль, если все варианты перебраны и 1 - если нет. чтобы ее можно было пускать в цикле вида Код while(D(a,n,k)) { //Делать что-нить с очередным размещением. }

Автор: neutrino 21.2.2004, 11:38

Чтобы использовать рекурсивную функцию это дело не пойдет. Надо писать итеративный способ решения задачи. Могу подсказать: количество размещений k элементов по n ячейкам = биномиальный коэффициент (n-1+k над n-1).

Автор: maxim1000 21.2.2004, 11:50

Цитата ясно, что если N==M, получается генератор перестановок. такого добра навалом если взять все перестановки и вырезать последние (M-N) элементов, то получим все размещения (только надо убрать одинаковые)

Автор: 46&two 24.2.2004, 09:42

Цитата если взять все перестановки и вырезать последние (M-N) элементов, то получим все размещения (только надо убрать одинаковые) ясное дело, что получим. вот только как вырезать? проблема в том, что: 1 - такой алгритм не оптимален - много действий 2 - как сравнивать - по совпадению? это надо быть бааальшим пофигистом, чтобы так по-варварски писать....

Автор: maxim1000 24.2.2004, 12:06

Цитата ясное дело, что получим. вот только как вырезать? проблема в том, что: 1 - такой алгритм не оптимален - много действий 2 - как сравнивать - по совпадению? это надо быть бааальшим пофигистом, чтобы так по-варварски писать.... иногда важна скорость работы алгоритма, а иногда - скорость его разработки, я же не знаю какой у тебя случай, вдруг тебе быстро надо а вырезать нужно просто последние M-N элементов и выкидывать повторяющиеся размещения а еще попробуй посмотреть http://forum.vingrad.ru/index.php?act=ST&f=13&t=17026, предложенную там функцию несложно переделать для размещений

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)