Как выполнить свертку сочетаний?

Question

[Дмитрий]

У меня есть множество уникальных сочетаний по 3 числа из различных чисел от 1 до 100. Есть ли алгоритм нахождения таких наборов рядов чисел, которые при разложении на сочетания дадут исходное множество? Пример :
Дано :
1 2 3
1 2 4
1 3 4
2 3 4
Ответ: 1 2 3 4
Нужно найти такой набор новых рядов который минимизирует кол-во записей.

Comments

[longclaps]

Нужно найти такой набор новых рядов который минимизирует кол-во записей.

Каких ещё записей? Наборы в условии вижу, ряды вижу, сочетания вижу, множество есть - а записей нет!

[Дмитрий]

longclaps, количество элементов в исходном множестве = кол-во записей
Я ищу способ записать исходное множество через наборы рядов. Как бы "заархивировать" исходное множество.

[longclaps]

Дмитрий, то есть ты числа назвал записями? Ну ты затейник!

[Дмитрий]

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

Answer 1

[Wataru]

Странно задача сформулирована, но, кажется, надо просто найти все уникальные числа во входных данных.
Или какой-нибудь set используйте, или сложите все входные числа в массив, отсортируйте и потом удалите повторяющиеся подряд идущие элементы.

Answer 2

[Дмитрий]

Нет, не уникальные числа.
Есть простая функция, которая получает строку из чисел (например 7 разных чисел в диапазоне от 1 до 100), на выходе выдаёт множество сочетаний по 3 числа - всего 35 элементов.
А мне нужна функция обратная - по множеству сочетаний (не больше 10000 элементов) определить из каких строк чисел можно получить это множество. Это что-то вроде обратимого хеширования наверное.
Пока мысли останавливаются на том чтобы посчитать количество связей между всеми числами в множестве

Comments

[Wataru]

Тогда решение такое:
Зная количество троек (n), вы знаете, сколько изначально чисел было (x):
x(x-1)(x-2) = n

Проще всего просто увеличивать x по одному, считать сколько троек должно получится из такого количества изначальных чисел и сравнивать с тем, что у вас есть.

Потом отсортируйте ваши тройки по возрастанию в лексикографическом порядке.
Вы уже точно знаете, что первая тройка - это первые 3 минимальные числа в вашем исходном массиве. Вторая тройка обязательно - 2 первых числа и четвертое. Следующая тройка - 2 первых и пятое. И так далее. Т.е. сморите на первые x-2 тройки. Там первые 2 элемента в каждой тройке - первые 2 в ответе, а оставшиеся третьи элементы - это все остальные x-2 числа в ответе.

Вот вам пример для x=5: (a,b,c,d,e)
abc, abd, abe, bcd, bce ...

Не важно, что за числа a..e - важно что они в не убывающем порядке. Тогда тройка abc - точно будет самой первой.

Это все если вам на вход подаются ВСЕ тройки. Если же не все, то можно, например, взять все уникальные элементы и, если в какой-то тройке элементы повторяются, то брать эти элементы 2, или 3 раза, если вся тройка состоит из повторений.

[Дмитрий]

wataru, сортировка поможет, но множество троек не обязательно составит полное множество. Может быть например такое:
1 5 17
1 5 22
1 5 23
1 17 23
5 17 23
И ответом будут 2 ряда:
1 5 17 23
1 5 22

[Wataru]

Дмитрий, Так, стоп, надо уточнить. Задача такая: функция из списка чисел делает список всех сочетаний-по-три. Этой функции скормили несколько списков. ВСЕ тройки даются на вход, надо восстановить изначальные списки. Если вариантов несколько, выдать тот в котором общая длина списков минимальна. Так?

[Дмитрий]

функция из списка чисел делает список всех сочетаний-по-три.

Да

Этой функции скормили несколько списков.

Несколько списков разной длины. Минимальная длина списка - 3 числа, максимальная - больше 10 не должно быть.

ВСЕ тройки даются на вход, надо восстановить изначальные списки.

даются на вход другой функции, т.е. это как раз то что я и пытаюсь найти.

Если вариантов несколько, выдать тот в котором общая длина списков минимальна. Так?

Да

В общем случае: есть множество М1 сочетаний по 3. Есть функция которая разложит строку чисел в комбинации по 3 f1(). Я ищу функцию f2() которая даст мне множество строк чисел M2.
Причем, f2(M1)=M2 (искомая функция) и f1(M2)=M1 и M2 меньше M1 (кол-во элементов в множество M2 сильно меньше, чем кол-во элементов в M1).

[Wataru]

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

Если нужно не самое оптимальное решение, а просто что-то лучше "каждая тройка - свой изначальный список", то можете делать жадно. Изначально сделайте каждую тройку своим списком и потом пытайтесь к первому списку все остальные тройки (в случайном порядке!) добавить. Добавить можно, если все тройки из расширенного списка есть во входных данных (можно добавить {1,2,4} к {1,2,3}, если есть {1,3,4} и {2,3,4}). Если смогли тройку добавить то все покрытые этим новым списком тройки выбрасывайте из рассмотрения. Когда все тройки прошли, первый список выдавайте в ответ и выбрасывайте. Повторяйте процедуру на оставшихся тройках.

[Дмитрий]

wataru, пример про двойки натолкнул меня на идею, что нужно за 1 проход продвигаться на 1 шаг. Из 3 сделать 4ки, на втором круге из 4 сделать 5 ки, и это будет легко потому что не сильно усложняет функцию, и потому что из 4х по 3 всего 4 комбинации, из 5 по 4 всего 5, и т.д. Если шаг =1, то всё сильно упрощается. В отсортированном массиве это простая операция проверки следующих элементов

Answer 3

[xmoonlight]

1 5 17
1 5 22
1 5 23
1 17 23
5 17 23

И ответом будут 2 ряда:
1 5 17 23
1 5 22

1. Две и более одинаковых цифр в одной колонке по вертикали (1-1-1-1, 5-5-5, 17-17, 23-23-23) - помещаем в одно общее множество: 1 5 17 23.
2. Убираем все сочетания, которые содержат любые 3 цифры из общего множества.
3. Остаются только уникальные строки (1 5 22): именно уникальные сочетания. Их просто добавляем отдельно.

Comments

[Дмитрий]

1 5 17
1 5 22
1 5 23
1 17 23
6 17 23

не получается

[xmoonlight]

Дмитрий,
1 5 17 23
1 5 22
6 17 23

Так должно быть?
PS: Или с 6 должно вставляться в общий паттерн?