2014 dxdy logo

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

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




На страницу 1, 2, 3  След.
 
 Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение14.12.2020, 15:09 
Требуется получить список уникальных сочетаний с повторениями из нечетных чисел >3, причем сумма чисел набора не превосходит заданного натурального числа n.
Вариант реализации через функцию nchoosek с последующим отсевом не подходит - с увеличением n генерация не подходящих сочетаний растет слишком быстро. Как организовать генерацию только подходящих наборов? Буду признателен за любую помощь.

 
 
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение14.12.2020, 15:31 
А не на матлабе что бы вы стали делать? Задача в общем-то простая...

 
 
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение14.12.2020, 15:40 
Я понимаю, что алгоритм не зависит от языка реализации. Прошу и Вас понять, что задачи, которые для Вас просты, для других - сложны. Пробую организовать цикл - пока не получается, видимо что-то упускаю (не понимаю).

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

 
 
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение14.12.2020, 16:04 
Вот это точно надо делать (дальше торможу):
код: [ скачать ] [ спрятать ]
Используется синтаксис 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 
Мда. Давайте-ка для начала четко поставим задачу, а то у нее условие, похоже, на ходу изменяется, изначально оно было другим. :-) И в нынешней постановке это не сочетания.

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

 
 
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение14.12.2020, 16:31 
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 
maximkarimov
Можете напечатать результат (список уникальных сочетаний с повторениями или чем оно теперь стало) для пары-тройки небольших $n$?
Например для $n=8$, $n=9$ и $n=10$

 
 
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение14.12.2020, 17:09 
Для $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 
Аватара пользователя
Как по Вашему, сколько таких наборов (примерно) будет для 10000 и что Вы с ними собираетесь делать?

 
 
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение14.12.2020, 17:28 
Да, я понимаю что если формировать список, то памяти может не хватить, поэтому предполагаю что есть возможность организовать последовательную генерацию наборов. Каждый набор является входным аргументом некоторой функции и хранить сгенерированные наборы мне не нужно.
P.S. Начал с формирования полного списка чтобы не запутаться.

 
 
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение14.12.2020, 17:52 
Аватара пользователя
maximkarimov в сообщении #1496508 писал(а):
памяти может не хватить

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

 
 
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение14.12.2020, 17:56 
Да, нужна последовательная генерация наборов, каждый их которых удовлетворяет заданным условиям (без генерации мусора). Мда, со временем тоже могут возникнуть проблемы... Что поделать, буду уменьшать потолок для n - в силу естественных, так сказать, причин.

 
 
 
 Re: Матлаб: сочетания с повторениями и заданными ограничениями
Сообщение14.12.2020, 18:10 
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 
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  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group