Заменить список списка на "сокращенный" список списка при сохранении порядка

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

from collections import OrderedDict
def disjoint_set_find(djs, node): # disjoint set find, with path compression
    if node not in djs: # base case, node is a root of a set
        return node
    djs[node] = disjoint_set_find(djs, djs[node]) # recurse, caching results
    return djs[node]

def disjoint_set_union(djs, first, second):
    first = disjoint_set_find(djs, first)   # find root of first set
    second = disjoint_set_find(djs, second) # and of second set
    if first < second: # make smaller root the root of the new combined set
        djs[second] = first
    elif second < first:
        djs[first] = second
    # deliberately ignore the case where first == second (same set)

def condenseBK(*master_list):
    values = OrderedDict() # maps values to the first sublist containing them
    overlaps = {}  # maps sublist indexes to each other to form a disjoint set
    for i, sublist  in enumerate(master_list):
        for v in sublist:
            if v not in values: # no overlap, so just store value
                values[v] = i
            else: # overlap detected, do a disjoint set union
                disjoint_set_union(overlaps, values[v], i)
    output = [] # results
    output_map = {} # map from original indexes to output indexes
    for v, i, in values.items(): # iterate over values in order
        root = disjoint_set_find(overlaps, i)
        if root not in output_map:
            output_map[i] = len(output)
            output.append([]) # create new output sublists as necessary
        output[output_map[root]].append(v)
    return output

Пример вывода:

>>> a = [1,2,3]
>>> b = [3,4]
>>> c = [88,7,8]
>>> d = [3, 50]
>>> e = [5,4]
>>> f = [8,9]
>>> g = [9,10]
>>> h = [20,21]
>>> i = [21,22]
>>> lst = [a,b,c,i,e,d,f,g,h,a,c,i]*1000
>>> condenseBK(*lst)
[[1, 2, 3, 4, 5, 50], [88, 7, 8, 9, 10], [21, 22, 20]]

Объяснение алгоритма:

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

Первые две функции реализуют операции find и union непересекающегося множества . Структура данных реализована с помощью словаря сопоставление узлов с их родительскими узлами. Любой узел, который не является ключом словаря, является root множества. Операция find возвращает корневой узел множества, содержащего заданный node. Чтобы немного повысить производительность, я реализовал "сжатие пути", которое уменьшает количество рекурсивных шагов, необходимых с течением времени. Операция union объединяет множества, содержащие ее аргументы first и second. Основная функция

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

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

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

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

Чтобы устранить перекрытие, код выполняет объединение непересекающихся наборов, содержащих два подсписка.

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

Чтобы заполнить выходной список, мы перебираем значения, что происходит в том порядке, в котором они были добавлены благодаря использованию класса OrderedDict. Используя непересекающийся набор, он может правильно комбинировать перекрывающиеся списки.

Этот алгоритм имеет очень хорошую производительность, когда есть много списков, подлежащих обработке, которые не перекрываются сразу. Например, этот набор из 200 трехэлементных списков в конечном счете все перекрывает, но вы только начинаете видеть перекрытия появляются после обработки первых 100:

lst2 = [list(range(4*i,   4*(i+1)-1)) for i in range(100)] + \
       [list(range(4*i+2, 4*(i+1)+1)) for i in range(100)]

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

lookup = {}
out = []
index = 0
for grp in lst:
    keys = [lookup.get(num, None) for num in grp]
    keys = [key for key in keys if key is not None]
    if len(keys):
        if len(set(keys)) != 1:
            for num in grp:
                out[keys[0]].append(num)
            seen = set()
            keys = [key for key in keys if key not in seen and not seen.add(key)]
            for key in keys[1:]:
                out[keys[0]].extend(out[key])
                del out[key]
            seen = set()
            out[keys[0]] = [item for item in out[keys[0]] if item not in seen and not seen.add(item)]
        else:
            for num in grp:
                lookup[num] = keys[0]
            out[keys[0]].extend(grp)
            seen = set()
            out[keys[0]] = [item for item in out[keys[0]] if item not in seen and not seen.add(item)]
    else:
        out.append(grp)
        for num in grp:
            lookup[num] = index
        index += 1

print out

Спасибо @Steven за технику сокращения списка с набором.

Вывод

[[1, 2, 3, 4, 5, 50], [88, 7, 8, 9, 10], [21, 22, 20]]

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

В вашей программе набор всех списков образует неориентированный граф, где каждый список является узлом в графе. Мы говорим, что два списка связаны непосредственно, если они имеют общие элементы, и связаны косвенно, если существует третий список, к которому оба связаны прямо или косвенно. Учитывая, например, три списки [a, b], [b, c] и [c, d], то [a, b] и [b, c] связаны непосредственно, а также [b, c] и [c, d], но [a, b] и [c, d] связаны косвенно, так как, хотя они не имеют общих элементов, они оба имеют элементы с одним и тем же списком [b, c]. Группа узлов является связным компонентом, если все узлы в группе связаны (прямо или косвенно) и ни один другой узел в графе не связан ни с одним узлом в группе.

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

from itertools import imap, combinations_with_replacement
from collections import defaultdict

def connected_components(edges):
    neighbors = defaultdict(set)
    for a, b in edges:
        neighbors[a].add(b)
        neighbors[b].add(a)
    seen = set()
    def component(node, neighbors=neighbors, seen=seen, see=seen.add):
        unseen = set([node])
        next_unseen = unseen.pop
        while unseen:
            node = next_unseen()
            see(node)
            unseen |= neighbors[node] - seen
            yield node
    for node in neighbors:
        if node not in seen:
            yield component(node)

def condense(lists):
    tuples = combinations_with_replacement(enumerate(imap(tuple, lists)), 2)
    overlapping = ((a, b) for a, b in tuples
                          if not set(a[1]).isdisjoint(b[1]))
    seen = set()
    see = seen.add
    for component in connected_components(overlapping):
        yield [item for each in sorted(component)
                    for item in each[1]
                    if not (item in seen or see(item))]

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

Результат:

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

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

Два списка связаны непосредственно, если они имеют общие элементы. Мы можем изменить это отношение: два элемента связаны напрямую, если они принадлежат к одному и тому же списку, и связаны косвенно, если существует третий элемент, который связан (прямо или косвенно) с ними обоими. Учитывая, например, два списка [a, b] и [b, c], то a и b связаны непосредственно, а также b и c, и поэтому a и c связаны косвенно. Если мы также адаптируем идею Дж. Ф. Себастьяна о хранении положения каждого элемента первым возникновение, мы можем реализовать его следующим образом:

def condense(lists):
    neighbors = defaultdict(set)
    positions = {}
    position = 0
    for each in lists:
        for item in each:
            neighbors[item].update(each)
            if item not in positions:
                positions[item] = position
                position += 1
    seen = set()
    def component(node, neighbors=neighbors, seen=seen, see=seen.add):
        unseen = set([node])
        next_unseen = unseen.pop
        while unseen:
            node = next_unseen()
            see(node)
            unseen |= neighbors[node] - seen
            yield node
    for node in neighbors:
        if node not in seen:
            yield sorted(component(node), key=positions.get)

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

Я попытался написать быстрое и читаемое решение. Он никогда не бывает намного медленнее, чем другие решения, если я знаю, но иногда может быть намного быстрее, потому что он дополнительно оптимизирован для более длинного подсписка или для многих подсписков, которые являются подмножеством любой Еще существующей группы. (Это мотивировано текстом вопроса "у меня есть много списков, но не очень много разных списков.") Код использует меньше памяти только для сжатых данных, которые могут быть намного меньше исходных данных. Он может работать, например, с a генератор, собирающий данные из процесса реального времени. Оценка сложности равна O (N log n). Я думаю, что ни один алгоритм, использующий сортировку, не может быть линейной сложности.

def condense(lists):
    groups = {}         # items divided into groups {id(the_set): the_set,...}
    members = {}        # mapping from item to group
    positions = {}      # mapping from item to sequential ordering
    iposition = 0       # counter for positions
    for sublist in lists:
        if not sublist or members.get(sublist[0], set()).issuperset(sublist):
            continue    # speed-up condition if all is from one group
        common = set([x for x in sublist if x in members])
        if common:      # any common group can be a destination for merge
            dst_group = members[common.pop()]
            common = common - dst_group   # are more groups common for sublist?
            while common:
                grp = members[common.pop()]
                if len(grp) > len(dst_group):   # merge shorter into longer grp
                    grp, dst_group = dst_group, grp
                dst_group.update(grp)
                for item in grp:
                    members[item] = dst_group
                del groups[id(grp)]
                common = common - dst_group
        else:           # or create a new group if nothing common
            dst_group = set()
            groups[id(dst_group)] = dst_group
        newitems = []
        for item in sublist:    # merge also new items
            if item not in positions:
                positions[item] = iposition
                iposition += 1
                newitems.append(item)
                members[item] = dst_group
        dst_group.update(newitems)
    return [sorted(x, key=positions.get) for x in groups.values()]

Это быстрее, чем pillmuncher2 для подслистов длиной примерно 8 элементов, потому что он может работать с большим количеством элементов вместе. Это также очень быстро для списков со многими подобными подсписками или многими подсписками, которые являются подмножеством любой Еще существующей группы. Он быстрее на 25% по сравнению с pillmuncher2 для lst_OP, однако медленнее на 15% для lst_BK.

Примером тестовых данных с длинными подсписками является [list(range(30)) + [-i] for i in range(100)].

Я намеренно написал "common = common-dst_group" вместо использования оператора set -= или "set.difference_update", потому что обновление на месте не эффективно, если набор на правой стороне намного больше, чем на левой стороне.

---

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

# Modified pillmuncher's solution
from collections import defaultdict

def condense(lists):
    neighbors = defaultdict(set)  # mapping from items to sublists
    positions = {}                # mapping from items to sequential ordering
    position = 0
    for each in lists:
        for item in each:
            neighbors[item].update(each)
            if item not in positions:
                positions[item] = position
                position += 1
    seen = set()
    see = seen.add
    for node in neighbors:
        if node not in seen:
            unseen = set([node])      # this is a "todo" set
            next_unseen = unseen.pop  # method alias, not called now
            group = []                # collects the output
            while unseen:
                node = next_unseen()
                see(node)
                unseen |= neighbors[node] - seen
                group.append(node)
            yield sorted(group, key=positions.get)

class List(list): pass

rv = dict()

def condense_step():
    """find and merge one overlapping pair in rv"""
    for i, iv in rv.items():
        for j, jv in rv.items():
            if i != j and i.intersection(j):
                m = i.union(j)
                del rv[i]
                del rv[j]
                rv.setdefault(m, [])
                rv[m] += iv
                rv[m] += jv
                return True

def unique(l):
    """flatten list-of-lists excluding duplicates"""
    seen = set()
    for i in sum(l, []):
        if i not in seen:
            seen.add(i)
            yield i

def condense(inp):
    rv.clear()
    inp = map(List, inp)

    for i in range(len(inp)):
        inp[i].order = i
        rv.setdefault(frozenset(inp[i]), [])
        rv[frozenset(inp[i])].append(inp[i])

    while condense_step():
        pass

    for v in rv.values():
        v.sort(key=lambda x: x.order)

    return [list(unique(i)) for i in rv.values()]

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

from collections import OrderedDict
from copy import deepcopy

def treat(passed_list):
    L = deepcopy(passed_list)

    dic = OrderedDict()
    for subl in L:
        for x in subl:
            if x not in dic:
                dic[x] =  subl
    print 'dic at start'
    print '\n'.join('%-3s : %s' % (a,dic[a])
                    for a in dic) + '\n'

    for sublist in L:
        short = []
        short.extend(el for el in sublist
                     if el not in short)
        seen  = []
        for k,val in dic.iteritems():
            if val is sublist:
                break
            if k in short:
                if val not in seen:
                    seen.append(val)

        sumseen = []
        for elseen in seen:
            for y in elseen:
                sumseen.append(y)
                dic[y] = sumseen

        if seen:
            for el in sublist:
                if el not in sumseen:
                    sumseen.append(el)
                    dic[el] = sumseen

        sublist[:] = short

    cumul = []
    cumul.extend(lu for lu in dic.itervalues()
                 if lu not in cumul)
    return cumul


plus = [[1,2,3,2,1],[10,5,5,5,10],
        [8,5,3,3,5],[45,50,12,45,40,12]]

lst = [[1,2,3], [10,5], [3,8,5]]

for one_list in (plus,lst):
    print 'one_list before == %r\n' % one_list
    print 'treat(one_list) == %r\n' % treat(one_list)
    print 'one_list after  == %r\n' % one_list
    print '===================================='

Результат

one_list before == [[1, 2, 3, 2, 1], [10, 5, 5, 5, 10], [8, 5, 3, 3, 5], [45, 50, 12, 45, 40, 12]]

dic at start
1   : [1, 2, 3, 2, 1]
2   : [1, 2, 3, 2, 1]
3   : [1, 2, 3, 2, 1]
10  : [10, 5, 5, 5, 10]
5   : [10, 5, 5, 5, 10]
8   : [8, 5, 3, 3, 5]
45  : [45, 50, 12, 45, 40, 12]
50  : [45, 50, 12, 45, 40, 12]
12  : [45, 50, 12, 45, 40, 12]
40  : [45, 50, 12, 45, 40, 12]

treat(one_list) == [[1, 2, 3, 10, 5, 8], [45, 50, 12, 40]]

one_list after  == [[1, 2, 3, 2, 1], [10, 5, 5, 5, 10], [8, 5, 3, 3, 5], [45, 50, 12, 45, 40, 12]]

====================================
one_list before == [[1, 2, 3], [10, 5], [3, 8, 5]]

dic at start
1   : [1, 2, 3]
2   : [1, 2, 3]
3   : [1, 2, 3]
10  : [10, 5]
5   : [10, 5]
8   : [3, 8, 5]

treat(one_list) == [[1, 2, 3, 10, 5, 8]]

one_list after  == [[1, 2, 3], [10, 5], [3, 8, 5]]

====================================

Это решение имеет неудобство: оно в 2-3 раза медленнее, чем решение Дж.Ф. Себастьяна.