Как объединить массивы с дубликатами в уникальные списки?

Question

[Александр Ф]

Есть множество массивов, в которых есть дублирующиеся элементы: [a,b], [c,d], [a, e], [e,f], [d,h], [h,o], [k,h]

Необходимо их объединить таким образом, чтобы в результате не было дубликатов, для данного примера получится:
[a,b,e,f], [c,d,h,o,k]. Т.е. [a,b] и [a,e] объединяются в [a,b,e], дальше есть массив с элементами [e,f], в итоге получается [a,b,e,f].

Количество элементов в массивах и количество самих массивов может быть любым. (в разумных пределах, пусть будет до 10шт)

Comments

[Lynn «Кофеман»]

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

[Александр Ф]

Алексей Тен, По принципу одинаковых элементов исходного множества массивов. Т.е. [a,b] и [a,e] объединяются в [a,b,e], дальше есть массив с элементами [e,f], в итоге получается [a,b,e,f].

[Lynn «Кофеман»]

Похоже на построение циклов в перестановке.
https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D...

Answer 1

[Wataru]

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

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

Суть в том, чтобы построить граф, где все различные элементы всех массивов будут вершинами. Ребра есть между двумя вершинами, если соответствующие им элементы присутствуют в одном и том же входном массиве.

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

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

Потом пройдитесь по всем элементам каждого входного массива и объединяйте его множество с множеством предыдущего элемента в том же массиве. Попутно, можете считать количество объединений, которые выполнились (множества были различными до выполнения операции union_sets). Так вы можете подсчитать, сколько массивов будет в ответе. В итоге все элементы для каждого массива в ответе будут в одном и том же множестве. Теперь, чтобы вывести ответ заведите массив списков с известным количеством элементов. Используйте ассоциативный массив, чтобы назначить каждому множеству один из списков в ответе. Пройдитесь по всем элементам и дописывайте их в соответствующий список.

Answer 2

[Griboks]

Очень странный вопрос. Это целых 2 вопроса:
1) как объединить массивы
2) как сделать массивы уникальными
Если у вас есть пример, то вы уже знаете ответ №1, значит ответ №2 будет: убрать повторяющиеся массивы. Если же вы не знаете ответ №1, то откуда у вас пример? Корректно поставленный вопрос - это уже половина ответа.