[Trotil]

Необходимо придумать оптимальный алгоритм.

Суть задачи:

Даны N отсортированных массивов (элементы могут повторяться в разных массивах, в пределах одного элементы уникальны).
Отношение порядка введено только для элементов внутри каждого массива, элементы разных массивов несравнимы.
Если элементы a и b есть одновременно более чем в одном массиве, то везде одновременно они либо a < b, либо a > b.

Задача: склеить массивы в один так, чтобы порядок элементов не нарушился.

Пример 1:

A=(1,2,3,4,5)
B=(6,7,8,9,10)

Результирующий массив либо (1,2,3,4,5,6,7,8,9,10), либо (6,7,8,9,10,1,2,3,4,5), либо даже (1,2,6,3,7,4,8,9,10,5), но первые два варианта более предпочтительны.

Пример 2:
A=(1,6,7,8)
B=(2,4,9,10)
C=(3,5,6,7,9)

Результирующий набор, например, это (2,1,4,3,5,6,7,8,9,10).

Comments

[Kot Dymok]

Пункт 0: "

Если элементы a и b есть одновременно более чем в одном массиве

..." - неверная формулировка, элементы разных массивов, судя по остальной части задачи, считаются объектами независимых типов.
Пункт 1: А чем стандартные варианты конкатенации не угодили?
(Вторая часть п.1) Оптимальность - с точки зрения чего?
И глупый вопрос: подразумевается императивная логика?
В общем, кажется мне, что или задача примитивна, или не до конца расписано её условие.

[Trotil]

О, правильные вопросы. Попробовал по-другому формализовать задачу.

Зайдём с другого конца.
Имеется N упорядоченных контейнеров и мы их хотим перечислить в порядке упорядочения.
Мы передаём информацию несколько раз, но каждый раз это делаем с пропусками.

Пример: пусть мы расставили контейнеры так:
1,2,3,4,5,6,7,8,9,10.

Передаём информацию три раза:

A=1,6,7,8 (остальные в этом сообщении не указаны)
B=3,4,9,10 (остальные в этом сообщении не указаны)
C=2,5,7,8,9. (остальные в этом сообщении не указаны)

Фактически, у нас задано отношение порядка не на всех элементах множества контейнеров: умеем сравнивать 1 < = > 6, но, например не умеем 1 < = > 2.

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

[Mr.Freedom]

Trotil,спасибо за отличную задачу!
предлагаю что-то на подобии мердж сорта: выделаем элементы которые встречаются больше чем в одном списке: 7 8 9 - назовем их "особыми"
дальше бежим и записываем по А до особого, остановились, 1 6
проверили есть ли особый в В и С - если есть записали все что до него 1 6 + 2 5
записали особый 1 6 2 5 7
снова особый 8
проверим есть ли он в B, C (будем считать что мы убираем элементы из очереди. так что в С уже нет 2 5 7) -ничего нет
пишем 8
A закончилась бежим по В
записываем все что до особого 1 6 2 5 7 8 + 3 4
дошли до особого 9
других элементов нет в С так что 1 6 2 5 7 8 3 4 9
продолжаем бежать и записываем 10 - больше элементов нет 1 6 2 5 7 8 3 4 9 10


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

[Kot Dymok]

Trotil, Я всё еще не до конца понимаю. Можете сказать, что у нас на входе, и что должно быть на выходе?
Mr.Freedom, меня очень смутила фраза "

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

" в стартовом сообщении, а тогда стандартный merge здесь не очень применим.
Хотя если убрать именно это предложение, то действительно, именно этот алгоритм и кажется наиболее удобным.

[Trotil]

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

Я примерно так в итоге и попробовал решить, хотя на реальных данных ещё не тестировал.
Я составил списки следований для каждого элемента. В нашем примере 6 следует за 1; 7 следует за 6. Некоторые элементы следуют за несколькими объектами сразу: 7 следует и за 6, и за 5.

Обязательно будут элементы, которые ни за кем не следуют. (в нашем примере это 1,3,2).
Выбираем из них любой, записываем в результирующую цепочку, удаляем эту связь из списка, число следований уменьшилось на единицу, повторяем алгоритм.
Очевидно, что алгоритм завершится.

[Trotil]

согласен, неудачная формулировка. Ориентируйтесь на формулировку 2.

элементы разных массивов несравнимы

мы не знаем, как сравнить два разных элемента, если они взяты из двух разных массивов.
Два одинаковых элемента из разных массивов - это один и тот же элемент. Надо было вставить это уточнение в стартовое сообщение.
(1,5,10)
(2,5,6)
Мы можем из этого вывести, что 1 < 6, но ничего не знаем о сравнении элементов 1 и 2.

[Kot Dymok]

Trotil, Алгоритм понятен и, как мне кажется, корректен. Однако я не смогу сходу сказать, как собрать "списки следования" оптимально, а не каким-то полным пересравнением всех элементов.

[CD_Eater]

задача не всегда имеет решение:

Пример:
A=(x,y)
B=(y,z)
C=(z,x)

Условие "Если элементы a и b есть одновременно более чем в одном массиве, то везде одновременно они либо a < b, либо a > b." выполняются.
Решения не существует.