2014 dxdy logo

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

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




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


26/09/17
322
Требуется получить список уникальных сочетаний с повторениями из нечетных чисел >3, причем сумма чисел набора не превосходит заданного натурального числа n.
Вариант реализации через функцию nchoosek с последующим отсевом не подходит - с увеличением n генерация не подходящих сочетаний растет слишком быстро. Как организовать генерацию только подходящих наборов? Буду признателен за любую помощь.

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


09/05/12
25179
А не на матлабе что бы вы стали делать? Задача в общем-то простая...

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


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

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


09/05/12
25179
Ну попробуйте для начала написать какие-то попытки решения.

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


26/09/17
322
Вот это точно надо делать (дальше торможу):
код: [ скачать ] [ спрятать ]
Используется синтаксис Matlab M
% Формируем список всех сочетаний с повторениями из нечетных чисел >3, сумма
% элементов набора не превышает заданного натурального r

% ====== Input argument ==========
r=15;

% ====== Algorithm ===============
if r>4
    a=5:2:r; % (1) получаем вектор множества возможных значений чисел в наборе
    b=zeros(1,size(a,2));% для каждого элемента а получаем максимальное число повторений в наборе
    for i=1:size(a,2)
        b(i)=floor(r/a(i));
    end
end
 

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


09/05/12
25179
Мда. Давайте-ка для начала четко поставим задачу, а то у нее условие, похоже, на ходу изменяется, изначально оно было другим. :-) И в нынешней постановке это не сочетания.

Заодно характерные желаемые масштабы $n$ укажите - от них зависит выбор между сложными и эффективными или простыми и неэффективными вариантами.

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


26/09/17
322
n до 10000 (нужен сложный, но эффективный вариант реализации)
Условия задачи готов пояснить и/или уточнить, но для этого нужен конкретный вопрос.
По всей видимости Вы правы и это не сочетания, а натуральные наборы с ограничениями для заданного n.
Может есть смысл поправить заголовок темы (правда мне это уже недоступно)?

-- 14.12.2020, 17:57 --
Матрица С тоже наверно нужна:
код: [ скачать ] [ спрятать ]
Используется синтаксис Matlab M
% Формируем список всех сочетаний с повторениями из нечетных чисел >3, сумма
% элементов набора не превышает заданного натурального r

% ====== Input argument ==========
r=15;

% ====== Algorithm ===============
if r>4
    a=5:2:r; % (1) получаем вектор множества возможных значений чисел в наборах
    b=zeros(1,size(a,2));% для каждого элемента а почучаем максимальное число повторений (коэффициент повторений)
    for i=1:size(a,2)
        b(i)=floor(r/a(i));
    end
    С=zeros(sum(b),2); % 1 столбец - элементы a, все возможные коэффициенты его повтотрений
    t=1;
    for i=1:size(a,2)
        for j=1:b(i)
            С(t,1)=a(i);
            С(t,2)=j;
            t=t+1;
        end
    end
end

С =

     5     1
     5     2
     5     3
     7     1
     7     2
     9     1
    11     1
    13     1
    15     1
 

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


05/09/16
11453
maximkarimov
Можете напечатать результат (список уникальных сочетаний с повторениями или чем оно теперь стало) для пары-тройки небольших $n$?
Например для $n=8$, $n=9$ и $n=10$

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


26/09/17
322
Для $n=8$ получим наборы:$\left\lbrace  5 \right\rbrace,\left\lbrace  7 \right\rbrace
Для $n=9$ получим наборы:$\left\lbrace  5 \right\rbrace,\left\lbrace  7 \right\rbrace,\left\lbrace  9 \right\rbrace
Для $n=10$ получим наборы: $\left\lbrace  5 \right\rbrace,\left\lbrace  5,5 \right\rbrace,\left\lbrace  7 \right\rbrace,\left\lbrace  9 \right\rbrace

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


01/09/13
4317
Как по Вашему, сколько таких наборов (примерно) будет для 10000 и что Вы с ними собираетесь делать?

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


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

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


01/09/13
4317
maximkarimov в сообщении #1496508 писал(а):
памяти может не хватить

На сколько порядков?
К примеру, число разбиений 1000 это 32 цифры...
Так что вопрос - а хватит ли времени?

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


26/09/17
322
Да, нужна последовательная генерация наборов, каждый их которых удовлетворяет заданным условиям (без генерации мусора). Мда, со временем тоже могут возникнуть проблемы... Что поделать, буду уменьшать потолок для n - в силу естественных, так сказать, причин.

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


05/09/16
11453
maximkarimov в сообщении #1496508 писал(а):
P.S. Начал с формирования полного списка чтобы не запутаться.

One-liner no-brainer на pari/gp, печатает все разбиения всех чисел от $1$ до $n$:
Код:
n=5;for(i=1,n,print(partitions(i)))

немного красивее:
Код:
all_part=List();n=5;for(i=1,n,v=partitions(i);for(j=1,#v,listput(all_part,Vec(v[j]))));
listsort(all_part);for(i=1,#all_part,print(all_part[i]))

Даёт все разбиения всех чисел от 1 до 5 на слагаемые в виде массивов слагаемых, в каком-то (странном) порядке.
Код:
[1]
[2]
[3]
[4]
[5]
[1, 1]
[1, 2]
[1, 3]
[1, 4]
[2, 2]
[2, 3]
[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 1, 1, 1]


Он-лайн интерпретатор pari/gp (вставить команду, нажать "Evaluate with PARI") https://pari.math.u-bordeaux.fr/gp.html

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


26/09/17
322
Geen в сообщении #1496510 писал(а):
maximkarimov в сообщении #1496508 писал(а):
памяти может не хватить

а хватит ли времени?

Кстати, вид матрицы С говорит о том, что ее строки можно получать последовательно в одном цикле. Это C для $n=21$:
код: [ скачать ] [ спрятать ]
Используется синтаксис Matlab M
C =

     5     1
     5     2
     5     3
     5     4
     7     1
     7     2
     7     3
     9     1
     9     2
    11     1
    13     1
    15     1
    17     1
    19     1
    21     1

Но как организовать последовательное получение наборов, которые содержат разные элементы (числа) и удовлетворяют условиям задачи - пока не догадываюсь...

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

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



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

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


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

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