Найти все возможные разбиения числа можно способом похожим на stars and bars, а добавив в алгоритм пару дополнительных проверок, получить требуемый результат - комбинации с заданным количеством слагаемых и неповторяющимися числами.

Удобнее объяснять графически:

1) берём число 9 и представляем его в виде восьмёрок (единицы слишком похожи на вертикальную черту, которая будет служить разделителем)

8 8 8 8 8 8 8 8 8

2) затем разделяем эти восьмёрки на правую и левую часть с помощью вертикальной черты (bar)

8 8 8 8 8 8 8 8 8 |  = 9 0
8 8 8 8 8 8 8 8 | 8  = 8 1
8 8 8 8 8 8 8 | 8 8  = 7 2
8 8 8 8 8 8 | 8 8 8  = 6 3
8 8 8 8 8 | 8 8 8 8  = 5 4
8 8 8 8 | 8 8 8 8 8  = 4 5
8 8 8 | 8 8 8 8 8 8  = 3 6
8 8 | 8 8 8 8 8 8 8  = 2 7
8 | 8 8 8 8 8 8 8 8  = 1 8

3) Если количество восьмёрок в правой части меньше 1, дальнейшее деление невозможно -> очередная комбинация найдена, иначе фиксируем левую часть и ищем варианты разбиений для правой части, то есть возвращаемся на пункт 1 и повторяем алгоритм для числа в правой части. Пример:

8 8 8 8 8 8 | 8 8 8  = 6 3

правая часть равна 3, фиксируем (запоминаем) левую часть и повторяем алгоритм для тройки

8 8 8 8 8 8      8 8 8       = 3 0
8 8 8 8 8 8      8 8 | 8    = 2 1
8 8 8 8 8 8      8 | 8 8    = 1 2

Рекурсивная реализация на Python:

def partition(new_comb, residue, combinations):
    if len(new_comb) > k:
        return

    if len(new_comb) == k and residue < 1:
        combinations.append('+'.join(map(str, new_comb)))
        return

    for cur_num in range(residue, 0, -1):
        if not new_comb or cur_num < new_comb[-1]:
            partition(new_comb + [cur_num], residue - cur_num, combinations)

combinations = []
num = 9 
k = 3 
partition([], num, combinations)
print(*combinations, sep='\n')

Спасибо)

Для n = 9 и k= 3 результат будет таким:

6+2+1
5+3+1
4+3+2

Английская статья на эту тему:

https://en.wikipedia.org/wiki/Partition_(number_theory)

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

Я наглядел себе пока два подхода. Попытаться реализовать мультиагентное моделирование и второй - всякие штуки а для job shop scheduling и ему подобное (но не очень пока понятно что именно под мою задачу лучше всего подходит)

Вопросы:
Что почитать/посмотреть про мою задачу? Там, по МАС, планированию всякому, теории расписаний.
Может у кого есть советы или сталкивался с таким?

Прошу прощения, только изучаю биг о нотацию. Я же правильно понимаю, что если есть два вложеных цикла и внешний цикл идёт по n итераций, а внутренний к примеру по 5 сложность будет О(n) ? Спасибо всем 😅

значит всего 5n операций. дальше по определению О найдется константа и тд. Да, асимптотика линейная

Спасибо Глеб ☺️

да

зато это интересно

Ну и зачем ты ответил на сообщение из 2018

Ребят, а какую структуру данных использовать для нахождения k ближайших соседей, если множество данных нужно изменять.

Ну например, есть геолокации, которые можно обновлять и нужны запросы на нахождения k ближайших соседей к заданной геолокации.

Смотрел KDTree в пайтоне, но там только query запросы есть, то есть рассчитано на статическое множество, по которому делают запросы.

потому что поимел опыт пихания перебора

а, не тебе хотел ответить, а Евгению. Но да ладно. Не серчай

bkd-tree, R*-tree?

А как тот же убер ищет ближайших водителей, когда юзер запрашивает поездку, если координаты водителей постоянно изменяются?
Тип для этого подойдёт R*-tree?

Скорее там соты

А это как?

local-sensitive-hashing

ну все равно после уменьшения размерности данных и группировании нужно же как-то находить k ближайших?

То есть юзер тоже мапится в какую-то соту, а потом по ней делают поиск ближайших не через k-d tree, но как?