2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение14.12.2020, 20:04 


05/09/16
11453
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-а не привожу.

 Профиль  
                  
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение14.12.2020, 20:21 


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

 Профиль  
                  
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение14.12.2020, 20:50 
Заслуженный участник
Аватара пользователя


01/09/13
4317
maximkarimov в сообщении #1496528 писал(а):
Да, число наборов от $n$ мне тоже непонятно как вычислить.

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

 Профиль  
                  
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение14.12.2020, 21:08 


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

 Профиль  
                  
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение14.12.2020, 21:35 
Заслуженный участник
Аватара пользователя


01/09/13
4317
maximkarimov в сообщении #1496536 писал(а):
Но я в самом начале отметил, что нужен максимально эффективный способ генерации.

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

 Профиль  
                  
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение14.12.2020, 21:44 


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

 Профиль  
                  
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение15.12.2020, 12:51 


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

 Профиль  
                  
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение15.12.2020, 13:10 


21/05/16
4292
Аделаида

(Оффтоп)

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

 Профиль  
                  
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение15.12.2020, 13:18 


26/09/17
322

(Оффтоп)

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

 Профиль  
                  
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение16.12.2020, 20:19 


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

 Профиль  
                  
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение16.12.2020, 20:37 


05/09/16
11453
maximkarimov в сообщении #1496798 писал(а):
Вообще говоря, задача сводится к следующей: требуется последовательно перебрать все подмножества элементов заданного вектора таких

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

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

 Профиль  
                  
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение16.12.2020, 21:17 


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

 Профиль  
                  
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение16.12.2020, 21:45 


05/09/16
11453
maximkarimov в сообщении #1496814 писал(а):
Если указать, что для "вектора такого-то будем перебирать так", то это не пример, а решение - алгоритм! :D

Вот именно.
maximkarimov в сообщении #1496814 писал(а):
Перебор с генерацией кучи мусора и последующим отсевом - не подходит.

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

 Профиль  
                  
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение16.12.2020, 22:26 


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

 Профиль  
                  
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение16.12.2020, 22:39 


05/09/16
11453

(погуглите)

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group