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

У меня есть список списка, как в приведенном мной коде. Я хочу связать каждый дополнительный список, если есть общие значения. Затем я хочу заменить список списка сокращенным списком списка. Примеры:, если у меня есть список [[1,2,3],[3,4]] Я хочу [1,2,3,4]. Если у меня есть [[4,3],[1,2,3]], я хочу [4,3,1,2]. Если у меня есть [[1,2,3],[a,b],[3,4],[b,c]], я хочу [[1,2,3,4],[a,b,c]] или [[a,b,c],[1,2,3,4]] Мне все равно, какой из них.

Я почти там...

Моя проблема в том, что у меня есть случай вроде [[1,2,3],[10,5],[3,8,5]] Я хочу [1,2,3,10,5,8], но с моим текущим кодом я получаю [1,2,3,8,10,5]

Вот мой код:

import itertools

a = [1,2,3]
b = [3,4]
i = [21,22]
c = [88,7,8]
e = [5,4]
d = [3, 50]
f = [8,9]
g=  [9,10]
h = [20,21]

lst = [a,b,c,i,e,d,f,g,h,a,c,i]*1000  
#I have a lot of list but not very many different lists

def any_overlap(a, b):
  sb = set(b)
  return any(itertools.imap(sb.__contains__, a))

def find_uniq(lst):
    ''' return the uniq parts of lst'''
    seen = set()
    seen_add = seen.add
    return [ x for x in lst if x not in seen and not seen_add(x)]

def overlap_inlist(o_lst, lstoflst):
    '''
    Search for overlap, using "any_overlap", of a list( o_lst) in a list of lists (lstoflst).
    If there is overlap add the uniq part of the found list to the search list, and keep 
    track of where that list was found 
    '''
    used_lst =[ ]
    n_lst =[ ]
    for lst_num, each_lst in enumerate(lstoflst):
        if any_overlap(o_lst,each_lst):
            n_lst.extend(each_lst)
            used_lst.append(lst_num)
    n_lst= find_uniq(n_lst)
    return  n_lst, used_lst

def comb_list(lst):
    '''
    For each list in a list of list find all the overlaps using 'ovelap_inlist'.
    Update the list each time to delete the found lists. Return the final combined list. 
    '''
    for updated_lst in lst:
        n_lst, used_lst = overlap_inlist(updated_lst,lst)
        lst[:] = [x for i,x in enumerate(lst) if i not in used_lst]
        lst.insert(0,n_lst)
    return lst
comb_lst = comb_list(lst)
print comb_lst

Вывод из этого script:

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

Я хочу, чтобы ключ находился в исходном порядке, например:

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

5 и 50 переключаются в новый lst [2]

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

Я могу сделать этот способ более сложным, чем это... Спасибо!!

Ответы

Ответ 1

Здесь применяется грубая сила (это может быть проще понять):

from itertools import chain

def condense(*lists):
    # remember original positions
    positions = {}
    for pos, item in enumerate(chain(*lists)):
        if item not in positions:
            positions[item] = pos

    # condense disregarding order
    sets = condense_sets(map(set, lists))

    # restore order
    result = [sorted(s, key=positions.get) for s in sets]
    return result if len(result) != 1 else result[0]

def condense_sets(sets):
    result = []
    for candidate in sets:
        for current in result:
            if candidate & current:   # found overlap
                current |= candidate  # combine (merge sets)

                # new items from candidate may create an overlap
                # between current set and the remaining result sets
                result = condense_sets(result) # merge such sets
                break
        else:  # no common elements found (or result is empty)
            result.append(candidate)
    return result

Пример

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

Сравнение производительности

condense_*() функции взяты из ответов на этот вопрос. lst_OP список ввода из вопроса (разного размера), lst_BK - тестовый список из @Blckknght answer (разного размера). См. источник.

Измерения показывают, что решения, основанные на понятиях "непересекающихся множеств" и "связанных компонентов неориентированного графа", выполняются аналогично на обоих типах ввода.

name                       time ratio comment
condense_hynekcer     5.79 msec  1.00 lst_OP
condense_hynekcer2     7.4 msec  1.28 lst_OP
condense_pillmuncher2 11.5 msec  1.99 lst_OP
condense_blckknght    16.8 msec  2.91 lst_OP
condense_jfs            26 msec  4.49 lst_OP
condense_BK           30.5 msec  5.28 lst_OP
condense_blckknght2   30.9 msec  5.34 lst_OP
condense_blckknght3   32.5 msec  5.62 lst_OP


name                       time  ratio comment
condense_blckknght     964 usec   1.00 lst_BK
condense_blckknght2   1.41 msec   1.47 lst_BK
condense_blckknght3   1.46 msec   1.51 lst_BK
condense_hynekcer2    1.95 msec   2.03 lst_BK
condense_pillmuncher2  2.1 msec   2.18 lst_BK
condense_hynekcer     2.12 msec   2.20 lst_BK
condense_BK           3.39 msec   3.52 lst_BK
condense_jfs           544 msec 563.66 lst_BK


name                       time ratio comment
condense_hynekcer     6.86 msec  1.00 lst_rnd
condense_jfs          16.8 msec  2.44 lst_rnd
condense_blckknght    28.6 msec  4.16 lst_rnd
condense_blckknght2   56.1 msec  8.18 lst_rnd
condense_blckknght3   56.3 msec  8.21 lst_rnd
condense_BK           70.2 msec 10.23 lst_rnd
condense_pillmuncher2  324 msec 47.22 lst_rnd
condense_hynekcer2     334 msec 48.61 lst_rnd

Чтобы воспроизвести результаты clone gist и запустить measure-performance-condense-lists.py

Ответ 2

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

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 набора disjoint set. Структура данных реализована со сдвигом словаря узлов к их родительским узлам. Любой node, который не является ключом словаря, представляет собой root набора. Операция find возвращает корень node набора, содержащего заданный node. Чтобы немного помочь производительности, я реализовал "сжатие пути", что уменьшает количество рекурсивных шагов, необходимых с течением времени. Операция union объединяет множества, содержащие ее аргументы first и second.

Основная функция condense состоит из двух частей. Во-первых, он создает пару структур данных, а затем использует их для построения вывода.

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

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)]

Ответ 3

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

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 для метода сокращения списка с помощью набора.

OUTPUT

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

Ответ 4

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

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

Группа узлов является связной компонентой, если все узлы в группе связаны (прямо или косвенно), и никакая другая node в графе не связана с любым node в группе.

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

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 связаны косвенно. Если мы также адаптируем идею J.F.Sebastians о сохранении положения каждого первого элемента, мы можем реализовать его так:

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)

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

Ответ 5

Я попытался написать быстрое и читаемое решение . Он никогда не намного медленнее других решений, если я знаю, но иногда может быть намного быстрее, потому что он дополнительно оптимизирован для более длительного подсписок или для многих подписок, которые являются подмножествами любой из существующих групп. (Это мотивировано текстом вопроса "У меня много списков, но не очень много разных списков".) В коде используется меньше памяти только для сжатых данных, которые могут быть намного меньше исходных данных. Он может работать, например. с генератором, собирающим данные из процесса реального времени. Оценка сложности 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", потому что исправление на месте неэффективно, если набор с правой стороны намного больше, чем на с левой стороны.

Модифицированное решение pillmuncher для удобства чтения. Модификация немного медленнее оригинала из-за замены генератора на list.append. Вероятно, это наиболее читаемое быстрое решение.

# Modified pillmuncher 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)

Ответ 6

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()]

Ответ 7

В этом решении используется только упорядоченный словарь.
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 раза медленнее, чем решение Дж. Ф. Себастьяна.