Матлаб: сочетания с повторениями и заданными ограничениями

[wrest]

maximkarimov
Я тут прикинул на коленке, количество нужных вам наборов зависит от $n$ так:

(Оффтоп)

n;part_odd_greater_3
1;0
2;0
3;0
4;0
5;1
6;1
7;2
8;2
9;3
10;4
11;5
12;6
13;7
14;9
15;11
16;13
17;15
18;18
19;21
20;25
21;29
22;34
23;39
24;45
25;52
26;60
27;69
28;79
29;90
30;103
31;117
32;133
33;151
34;171
35;194
36;219
37;247
38;278
39;313
40;352
41;395
42;443
43;496
44;555
45;621
46;693
47;773
48;861
49;959
50;1067
51;1186
52;1317
53;1461
54;1620
55;1795
56;1987
57;2198
58;2429
59;2683
60;2962

Наборы для $n=30$ (всего 103)

(Оффтоп)

[5], [5, 5], [5, 5, 5], [5, 5, 5, 5], [5, 5, 5, 5, 5], [5, 5, 5, 5, 5, 5], [5, 5, 5, 5, 7], [5, 5, 5, 5, 9], [5, 5, 5, 7], [5, 5, 5, 7, 7], [5, 5, 5, 9], [5, 5, 5, 11], [5, 5, 5, 13], [5, 5, 5, 15], [5, 5, 7], [5, 5, 7, 7], [5, 5, 7, 9], [5, 5, 7, 11], [5, 5, 7, 13], [5, 5, 9], [5, 5, 9, 9], [5, 5, 9, 11], [5, 5, 11], [5, 5, 13], [5, 5, 15], [5, 5, 17], [5, 5, 19], [5, 7], [5, 7, 7], [5, 7, 7, 7], [5, 7, 7, 9], [5, 7, 7, 11], [5, 7, 9], [5, 7, 9, 9], [5, 7, 11], [5, 7, 13], [5, 7, 15], [5, 7, 17], [5, 9], [5, 9, 9], [5, 9, 11], [5, 9, 13], [5, 9, 15], [5, 11], [5, 11, 11], [5, 11, 13], [5, 13], [5, 15], [5, 17], [5, 19], [5, 21], [5, 23], [5, 25], [7], [7, 7], [7, 7, 7], [7, 7, 7, 7], [7, 7, 7, 9], [7, 7, 9], [7, 7, 11], [7, 7, 13], [7, 7, 15], [7, 9], [7, 9, 9], [7, 9, 11], [7, 9, 13], [7, 11], [7, 11, 11], [7, 13], [7, 15], [7, 17], [7, 19], [7, 21], [7, 23], [9], [9, 9], [9, 9, 9], [9, 9, 11], [9, 11], [9, 13], [9, 15], [9, 17], [9, 19], [9, 21], [11], [11, 11], [11, 13], [11, 15], [11, 17], [11, 19], [13], [13, 13], [13, 15], [13, 17], [15], [15, 15], [17], [19], [21], [23], [25], [27], [29]

Но поскольку это решение "на двойку", текст one-liner-а не привожу.

[maximkarimov]

Спасибо. Да, число наборов от $n$ мне тоже непонятно как вычислить.

[Geen]

maximkarimov в сообщении #1496528 писал(а):

Да, число наборов от $n$ мне тоже непонятно как вычислить.

Вот начните с этого, и убедитесь, что даже для $n=1000$ количество наборов порядка $10^{21}$ - считая, что набор обрабатывается за миллисекунду, получим возраст Вселенной....

[maximkarimov]

Да, растет быстро и даже до $n=1000$ в разумное время скорее всего не дотянуть. Но я в самом начале отметил, что нужен максимально эффективный способ генерации.

[Geen]

maximkarimov в сообщении #1496536 писал(а):

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

Вы прикалываетесь? Или порядки считать не умеете?

[maximkarimov]

Green, спасибо за то, что обратили мое внимание на потолок для $n$. И вообще спасибо.

[maximkarimov]

Похоже на то, что необходимо внутри обычного цикла (по нечетным числам) рекурсивный вызов делать. Такую конструкцию самостоятельно еще не доводилось реализовывать, прошу помочь.
P.S. С учетом замечания Geen любопытно какой практический потолок будет у $n$.

[kotenok gav]

(Оффтоп)

А когда Geen переименовался в Green?

[maximkarimov]

(Оффтоп)

Сорри!) Исправился.

[maximkarimov]

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

[wrest]

maximkarimov в сообщении #1496798 писал(а):

Вообще говоря, задача сводится к следующей: требуется последовательно перебрать все подмножества элементов заданного вектора таких

В каком порядке перебирать будем?

И ещё совет. Словесное описание довольно трудно воспринимать, особенно когда неясно сформулировано, поэтому рекомендую сразу давать пример. Типа "например, для вектора такого-то будем перебирать так...".

[maximkarimov]

Конкретный порядок перебора (какой набор за каким будем получать) не имеет значения, разве что с точки зрения удобства реализации и эффективности. Если указать, что для "вектора такого-то будем перебирать так", то это не пример, а решение - алгоритм!
P.S. Перебор с генерацией кучи мусора и последующим отсевом - не подходит.

[wrest]

maximkarimov в сообщении #1496814 писал(а):

Если указать, что для "вектора такого-то будем перебирать так", то это не пример, а решение - алгоритм!

Вот именно.

maximkarimov в сообщении #1496814 писал(а):

Перебор с генерацией кучи мусора и последующим отсевом - не подходит.

А что подходит? Не ну правда -- возьмите небольшое что-то и поясните.

[maximkarimov]

Любой алгоритм, который дает верный результат без генерации в процессе своей работы кучи мусора - подходит.
Не понимаю что тут может быть непонятного.
Или Вы хотите пример алгоритма, который дает верный результат, но при этом в ходе выполнения генерирует кучу мусора - то есть пример не подходящего алгоритма? Извольте - это алгоритм с использованием функций repmat и nchoosek с последующим перебором и отсевом неудовлетворительных наборов. Его приводит С.П.Иглин (погуглите) - кстати, Матлаб он неплохо знает. Вот ему наверно и напишу!

[wrest]

(погуглите)

maximkarimov в сообщении #1496835 писал(а):

(погуглите)

Это в крайней степени неуважительно с вашей стороны. Здесь же вы хотите получить помощь, верно?