Нужен алгоритм упаковки(группировки)

Тут определённо что-то про кластеризацию, только непонятно, почему группы должны быть равными по размеру.

как известно, правильная формулировка задачи — половина её решения. Сформулируй строго математически, что ты хочешь, и я уверен, ты получишь почти готовый алгоритм решения

https://en.wikipedia.org/wiki/Simulated_annealing

Я предсиавил числа как элементы графа, связи между ними как ребра. И потом бы искал изолированные подграфы. Ну или там по минимуму соединённые. Алгоритмы есть в книжках.

Нужно этот набор зарделить на N примерно равных групп

Сортировки вполне хватит.

Какому порядку по?

Не хватит. У меня такие выборки где эвристика в виде сортировки не работает.

эвристика в виде сортировки не работает.

Приведи пример.

Не обязательно равные зависит от размера группы. Ну например ести колличество пар 20 то можно разбить на 13 и 7 или 5 и 15

как известно, правильная формулировка задачи

Задачи и так сформулирована паксимально математически. Если интересно как она изначально сформулирована то на самом деле там не пары чисел, а набор предикатов у которых по два аргумента и их нужно разделить на группы в которых как можно меньше будет одинаковых аргументов. Например:

predicate1 arg1 arg2

predicate2 arg2 arg3

predicate3 arg4 arg5

predicate4 arg6 arg7

Приведи пример.

Тогда напиши способ сортировки который ты предлагаешь. Т.е. как конкретно эти пары изначально отсортировать?

Я предсиавил числа как элементы графа

Можно и так представлять, только в данном случае задача не пройти по граф а построить граф с минимальным количеством ребер.

Т.е. как конкретно эти пары изначально отсортировать?

Полностью, поперёк, потом вдоль.

Полностью, поперёк, потом вдоль.

думаю это не сработает, т.к. пары представляют из себя изначально группы из 2 3 или 4 пар которые стоят рядом и имеют связи, сортировка нарушает эти локальные группы. Грубо говоря если просто в лоб разрезать поровну без сортировка это всегда будет лучше чем если вначале отсортировать.

это всегда будет лучше чем если вначале отсортировать.

Доминошки никогда в пирамидки не выстраивал? Выстрой, не поленись.

Посчитать количество каждых чисел. И на основе этого знания делить по N группам. Каждую подгруппу из неуникальных отрезков в одну группу: отрезки с 3 - в первую группу, отрезки с 4 - другую. Потом для добить уникальными для равенства групп.

По твоей формулировке оптимальным решением будет класть каждую пару в свою отдельную группу.

В ОП же [3, 4][4, 7] и [5, 6] [1, 2] оптимальное, а не [3, 4], [4, 7], [5, 6] и [1, 2], что согласуется с критерием.

По твоей формулировке оптимальным решением будет класть каждую пару в свою отдельную группу.

Обычно количество пар 20-50 нужно разрезать примерно по 10 пар

Разве это не собрат алгоритма составления оптимального расписания ? решаешь задачу составления оптимального расписания по сути сортировкой левого конца и либо по его критерию берёшь самые ранее заканчивающиеся работы, либо свой критерий делаешь.

Можешь попробовать например разделённые множества тут использовать - объединешь по концам отрезка, а затем полученные разделённые множества разбиваешь по оптимальному размеру или просто реши как задачу о минимальном разрезе или как задачу разбиения на компоненты сильной связности графа.

Разве это не собрат алгоритма составления оптимального расписания

Не в курсе про него почитаю.

У меня пока идея использовать оптимизационный алгоритм т.н. Алгоритм имитации отжига.

Сначала делить на нужное количество групп, а потом пробовать менять местами 2 пары в 2х разных группах и смотреть стало хуже или лучше.

концам отрезка
оптимального расписания

Вроде нет никаких отрезков, речь просто о парах чисел, которые нужно по отдельности рассматривать.

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

А ещё можете попробовать для каждой пары посчитать количество связей и просто вычленять пары у которых их больше всех(и соседей у которых больше 2-3 связей), пока не разобъёте в удобной пропорции(правда может получиться, что если это полносвязный граф, то его разбить проблемно)

да знаю, поторопился, тут графовая задача, дан то массив рёбер.

А необычно ненужно? По одной паре это подходит под «примерно по 10»? Вам уже сказали, научитесь формулировать задачи.

Там не сказано что это самое оптимальное, там сказано что это более оптимальное чем [3, 4] [5, 6] и [1, 2] [4, 7] и нет никаких ограничений на размеры групп.

Есть набор пар чисел.

То есть набор двумерных векторов, лежащих в первом квадранте. Хотя, для критерия удобнее работать с неупорядоченными парами. Тогда — двумерный вектор, лежащий в первом октанте.

где критерием является количество одинаковых чисел в группах

То есть две точки лежат либо на одной вертикали, либо на одной горизонтали. Похоже на задачу расстановки ладьей на половинке шахматной доски.

Там буквально написано

Оптимальный будет: [3, 4][4, 7] и [5, 6] [1, 2]

Это никак не противоречит тому что [[1, 2]] [[3, 4]] [[5, 6]] [[4,7]] также будет оптимальным. В любом случае, задача описывается формулировкой, а не примерами.

То решение оптимальное из-за отсутствия связей, а в [[1, 2]] [[3, 4]] [[5, 6]] [[4,7]] есть одна связь между [3, 4] и [4, 7]. Т.е. другие оптимальные это:

• [[1, 2] [3, 4] [5, 6] [4,7]]
• [[1, 2]] [[3, 4] [5, 6] [4,7]]
• [[5, 6]] [[3, 4] [1, 2] [4,7]]

На пистоне пойдёт?

from random import randint

def get_pairs(n=50, minmax=(1,10)):
    p = []
    for _ in range(n):
        a = randint(*minmax)
        while True:
            b = randint(*minmax)
            if b != a:
                break
        p += [(a,b)]
    return p
    
def make_dict(p):
    d = {}
    for i,(a,b) in enumerate(p):
        d[a] = d.get(a, []) + [i]
        d[b] = d.get(b, []) + [i]
    return d

def get_group(d, p):
    g = []
    n = []
    for k in d:
        for i in d[k]:
            a,b = p[i]
            if a in n or b in n:
                continue
            d[a].remove(i)
            d[b].remove(i)
            g.append((a,b))
            n += [a,b]
            break
    return g

p = get_pairs()
d = make_dict(p)
while True:
    g = get_group(d,p)
    if not g:
        break
    print(g)

Вывод:

[(3, 9), (4, 2), (7, 8), (10, 5)]
[(7, 3), (9, 2), (8, 6), (4, 10), (1, 5)]
[(6, 3), (8, 9), (1, 2), (4, 7), (5, 10)]
[(9, 3), (2, 1), (7, 10), (5, 8)]
[(9, 3), (2, 6), (5, 7), (10, 8), (4, 1)]
[(7, 3), (2, 9), (10, 8), (1, 5)]
[(4, 9), (7, 2), (8, 6), (10, 5)]
[(9, 6), (5, 2), (7, 1), (8, 10)]
[(2, 9), (6, 7), (4, 10)]
[(9, 7), (2, 4), (5, 10)]
[(7, 9), (1, 2)]
[(2, 9), (6, 7)]
[(2, 9), (5, 7)]
[(2, 1), (5, 7)]
[(6, 7)]

:3

Задачи и так сформулирована паксимально математически.

N примерно равных групп

Ну ты понял.

По твоей размытой формулировке подходит алгоритм, по которому ты просто рассматриваешь числа одно за другим и вносишь в группу, если есть совпадение (жесткость критериев подбираешь сам).

Пример: группы g1, g2… проверяем [a,b]. Если a in gi, b in gi, a in gj, b in gj and |gi|<|gj| — добавляешь в gi. Для оставшихся 2х случаев придумай сам.

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

Паросочетание © — > жадный алгоритм © — > profit!

что если это полносвязный граф, то его разбить проблемно)

чаще всего полносвязный, со скоплениями узлов и между этими скоплениями есть по 1-2 связям. Также бывает присутствуют звезды, когда есть пара к которой есть связи из всех групп.

То есть две точки лежат либо на одной вертикали

Можно числа заменить иероглифами разницы нет. Я просто для упрощения ниписал числа вот тут я написал как на самом деле все выглядит Нужен алгоритм упаковки(группировки) (комментарий)

[[1, 2]] [[3, 4]] [[5, 6]] [[4,7]] также будет оптимальным.

где же оно оптимальное если межнду второй и четвертой группой есть связь.

Т.е. другие оптимальные это:

Они менее оптимальны т.к. группы отличаются в 2 раза друг от друга, нужно примерно одинаковые. нужно чтобы были примерно одинаковые. А у вас в 3 раза разница получается.

Они менее оптимальны

Введи badness = кол-во внешних связей. И примени «разделяй и строй».

Почитайте лучше разделённые множества

Вы имеете в виду задачу об «Упаковке множеств» ? Вы знаете алгоритмы которые могут её решать?

Введи badness = кол-во внешних связей. И примени «разделяй и строй».

Ну это похоже на Имитацию отжига. Делишь на части переставляешь пары между множествами а потом смотришь «badness» или «goodness» (смотря что есть) т.е. лучше/хуже

Пример: группы g1, g2… проверяем [a,b]. Если a in gi, b in gi, a in gj, b in gj and |gi|<|gj| — добавляешь в gi. Для оставшихся 2х случаев придумай сам.

Так работать не будет, в результате все в одну группу попадет, т.к. результате разделения нужно минимизировать связи, варианта когда связей нет совсем не будет.

У меня есть небольшое непонимание как натянуть мою задачу на теорию графов. Получается что изначально мой грав состоит из связей 2-х типов «разрывных»(между парами) и «неразрывных»(внутри пар). Задача получается в нахождении соседей с максимальным количеством «разрывных» связей. Можно для условности покрасить ребра разными цветами например зеленым(разрывные) и красным(неразрывные)

Прокоментируйте, правильно я свожу задачу к теории графов?

тогда просто бить на компоненты сильной связности разбить или разделённые множества подкрутить.

Я имел ввиду 1 и 2 в первом случае придётся подкрутить критерий объединения - например по числу связей, а по-второму поискать алгоритмы

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

Они менее оптимальны

Да, я хотел пример по связям показать и проигнорировал размеры.

У меня есть небольшое непонимание как натянуть мою задачу на теорию графов.

Так а зачем пары разбивать (представлять двумя точками), если их всё равно нельзя делить? Пусть каждая пара будет одной вершиной с рёбрами от обоих чисел.

Пусть каждая пара будет одной вершиной с рёбрами от обоих чисел.

тогда как понимать почему они связаны с другими точками?

В общем пока сделаю имитацию отжига, если поможет улучшить группы, то оставлю.

тогда как понимать почему они связаны с другими точками?

Так известно же, что это за пары на обоих концах ребёр.

Или можно аннотировать ребра отдельно. Просто увеличивать размерность графа кажется здесь лишним.