Как объединить пересекающиеся списки в списке списков?

Question

У меня есть двумерный массив [[1, 2, 3], [2, 3, 4, 5], [2, 3, 4, 5, 6, 7]] (подмассивы отсортированы).

Нужно отсортировать его следующим образом: если в одном подмассиве есть часть другого, то они должны слиться в один массив, так чтобы не было повторяющихся элементов. Например: [[1, 2, 3], [2, 3, 4, 5],[2, 3, 4, 5, 6, 7]] должен слиться в массив [[1, 2, 3, 4, 5, 6, 7]]. Если пересекающихся элементов нет, как в массиве [[1, 2, 3],[5 ,6, 7]], то делать ничего не нужно.

Сложность ещё в том, что нужно использовать только ванильный python, без встроенных библиотек.

Answer 1

Факт пересечения отсортированных списков можно найти, используя алгоритм, похожий на процедуру Merge в MergeSort:

while ia < len(A) and ib < len(B):
   if A[ia] < B[ib]:
       ia += 1
   elif A[ia] > B[ib]:
       ib += 1
   else:
       нашли совпадение, слить списки

Объединение списков с удалением дубликатов (из вопроса не ясно, нужно ли оно), можно сделать таким же образом.

Answer 2

Можно вопользоваться рекурсией:

def fun(mat, ii=0):
    if ii >= len(mat) - 1:
        return mat
    for i in range(ii+1, len(mat)):
        if set(mat[i]) & set(mat[ii]):
            mat[ii] = sorted(list(set(mat.pop(i)) | set(mat[ii])))
            return fun(mat, ii)
    return fun(mat, ii+1)

тесты:

In [176]: fun([[1, 2, 3], [2, 3, 4, 5], [2, 3, 4, 5, 6, 7]])
Out[176]: [[1, 2, 3, 4, 5, 6, 7]]

In [177]: fun([[1,2,3], [4,5], [7,8], [5,6,9], [9,10]])
Out[177]: [[1, 2, 3], [4, 5, 6, 9, 10], [7, 8]]

In [178]: fun([[1,2], [4,5], [7,8]])
Out[178]: [[1, 2], [4, 5], [7, 8]]

БЛОГ НА HUSL

Как объединить пересекающиеся списки в списке списков?

Ответы (2 шт):