дело так:



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

Ну вот алгоритм рекурсивный "на вскидку" написал, если нужно именно итеративный, скажи.

Цитата

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

Да, нехило.
Только не соображу, как эту функцию преобразвать к формату вида

Код

int D(int *a, int n, int k)

которая в *a запихивает очередное размещение, а возвращает ноль, если все варианты перебраны и 1 - если нет.
чтобы ее можно было пускать в цикле вида

Код

while(D(a,n,k)) { //Делать что-нить с очередным размещением. }

Это сообщение отредактировал(а) 46&two - 19.2.2004, 09:45

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

Цитата

ясно, что если N==M, получается генератор перестановок. такого добра навалом

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

Цитата

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

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

Цитата

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

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