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

[maximkarimov]

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

[Pphantom]

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

[maximkarimov]

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

[Pphantom]

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

[maximkarimov]

Вот это точно надо делать (дальше торможу):

Используется синтаксис 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
 

[Pphantom]

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

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

[maximkarimov]

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
 

[wrest]

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

[maximkarimov]

Для $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

[Geen]

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

[maximkarimov]

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

[Geen]

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

памяти может не хватить

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

[maximkarimov]

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

[wrest]

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

[maximkarimov]

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

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