Сочетания с повторениями

всем привет!
Объясните, как реализовать перебор сочетаний с повторениями.

 

под словом "перебор" понимайте получение на выходе списка вариантов. Для 3х переменных и 2х мест это будет:

Код (Text):

1. 11  22  33  
2. 12  23  13

 

Вообще-то есть формулы. Если же что-то действительно сложное, то иначе как запоминать состояния и искать совпадения, я не вижу. Пока перебираем, запоминаем и тут же проверяем.

 

Рекурсивная раздача мест.

То есть, во-первых, состояния надо описывать упорядоченным массивом, где для каждого элемента указывается количество занимаемых мест:
00 -> [2,0,0]
01 -> [1,1,0]
02 -> [1,0,1]
11 -> [0,2,0]
12 -> [0,1,1]
22 -> [0,0,2]

Во-вторых, рекурсивная функция с двумя параметрами: количество раздаваемых мест и индекс элемента. Функция должна раздать всеми способами указанное количество мест для всех элементов, чьи индексы больше или равны указанному индексу. Задача разбивается на подзадачи: раздать указанному индексу и всем оставшимся более старшим элементам через рекурсивный вызов. Случай с нулевым количеством мест проще тоже отдавать в рекурсию до тех пор, пока не дойдет до случая, когда нет более элементов с более старшими индексами, тогда вместо рекурсивного вызова выдвавть результат (т.к. в этот момент массив оказывается полностью заполненным):

Пусть N - количество элементов, M - количество мест

Код (Text):

1. int state[N];
2.  
3. void GivePlaces(num_places,index)
4. {
5.   if(index<N-1)
6.   {
7.     for(int i=0;i<=num_places;i++)
8.     {
9.       state[index]=i;
10.       GivePlaces(num_places-i,index+1)
11.     }
12.   }
13.   else
14.   {
15.     state[index]=num_places;
16.     YieldResult();
17.   }
18. }
19.  
20. GivePlaces(M,0);

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

 

Упс, в три часа ночи язык получился помесью С99 с жяваскриптом :-О Но суть не меняется

 

кому интересно, сделал совсем по другому (:
Тупо в цикле перебираю значения счетчика цикла, для приведенного примера:

Код (Text):

1. for i=1 to 200 do
2.   if (SUM(цифр i)=2) then "i подходит"

и парсим i.