python - example - Reemplace la lista de la lista con la lista "condensada" de la lista mientras mantiene el orden

product() python

Question

Tengo una lista de la lista como en el código que adjunto. Quiero vincular cada sub lista si hay valores comunes. Entonces quiero reemplazar la lista de la lista con una lista condensada de la lista. Ejemplos: si tengo una lista [[1,2,3],[3,4]] quiero [1,2,3,4] . Si tengo [[4,3],[1,2,3]] quiero [4,3,1,2] . Si tengo [[1,2,3],[a,b],[3,4],[b,c]] quiero [[1,2,3,4],[a,b,c]] o [[a,b,c],[1,2,3,4]] No me importa cuál.

Ya casi estoy allí...

Mi problema es cuando tengo un caso como [[1,2,3],[10,5],[3,8,5]] Quiero [1,2,3,10,5,8] pero con mi código actual que obtengo [1,2,3,8,10,5]

Aquí está mi código:

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

La salida de este script es:

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

Lo quiero así que las llaves están en el orden original como:

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

El 5 y el 50 se cambian en nuevo lst [2]

Soy algo nuevo en python. Agradecería cualquier solución al problema o comentarios sobre mi código actual. No soy un experto en informática, me imagino que puede haber algún tipo de algoritmo que haga esto rápidamente (¿tal vez de la teoría de conjuntos?). Si existe un algoritmo de este tipo, indíqueme la dirección correcta.

Puede que sea más complicado de lo que es ... ¡Gracias!

Answer 1

Aquí está mi enfoque. Utiliza el concepto de un "conjunto disjunto" para identificar primero qué sublistas se superponen entre sí, luego las une, eliminando los duplicados.

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

Salida de muestra:

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

Una explicación del algoritmo:

Por solicitud, aquí hay una explicación de cómo funciona mi código.

Las dos primeras funciones implementan las operaciones de find y union de un conjunto desunido . La estructura de datos se implementa con un diccionario que asigna nodos a sus nodos principales. Cualquier nodo que no sea una clave del diccionario es la root de un conjunto. La operación de find devuelve el nodo raíz del conjunto que contiene un node determinado. Para ayudar un poco al rendimiento, he implementado la "compresión de ruta", que reduce el número de pasos recursivos necesarios con el tiempo. La operación de union combina los conjuntos que contienen sus argumentos first y second .

La función de condense principal tiene dos partes. Primero, configura un par de estructuras de datos, luego las usa para construir la salida.

values es un OrderedDictionary que se asigna de cada valor al índice de la primera lista secundaria en la que se encuentra. El orden en que se agrega cada valor se utiliza para producir la salida en el orden correcto.

overlaps es el diccionario utilizado como para el conjunto disjoint. Sus nodos son los índices enteros de sublistas superpuestas.

Los primeros bucles llenan esas dos estructuras de datos. Recorren los sublistas y sus contenidos. Si un valor no se ha visto anteriormente, se agrega al diccionario de values . Si se ha visto, la sublista actual está superponiendo una sublista anterior que contiene ese valor.

Para resolver la superposición, el código hace una unión de los conjuntos disjuntos que contienen las dos sublistas.

La salida está incorporada en la lista de output . Debido a que es probable que haya menos sublistas de salida de las que había en la entrada, necesitamos un diccionario adicional para asignar entre los índices antiguos (de la entrada) a los nuevos índices que se aplican a la lista de salida.

Para completar la lista de resultados, iteramos sobre los valores, lo que sucede en el orden en que se agregaron gracias al uso de la clase OrderedDict. Usando el conjunto disjoint, puede combinar las listas superpuestas correctamente.

Este algoritmo tiene un rendimiento muy bueno cuando hay muchas listas para procesar que no se superponen inmediatamente. Por ejemplo, este conjunto de 200 listas de tres elementos en última instancia, todas se superponen, pero solo comienza a ver las superposiciones después de que se hayan procesado las primeras 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)]

Answer 2

Aquí hay un enfoque de fuerza bruta (podría ser más fácil de entender):

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

Ejemplo

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

Comparación de rendimiento

condense_*() funciones de condense_*() provienen de las respuestas a esta pregunta. lst_OP lista de entrada de la pregunta (tamaño diferente), lst_BK - la lista de prueba de la respuesta de @ Blckknght (tamaño diferente). Vea la fuente .

Las mediciones muestran que las soluciones basadas en conceptos de "conjuntos disjuntos" y "componentes conectados de gráficos no dirigidos" se comportan de manera similar en ambos tipos de entrada.

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

Para reproducir los resultados, clone gist y ejecute measure-performance-condense-lists.py

Answer 3

Esta solución utiliza solo un diccionario ordenado.
deepcopy () es necesario si uno quiere que la copia original permanezca sin cambios.

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 ''====================================''

resultado

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

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

Esta solución tiene un inconveniente: es 2 a 3 veces más lenta que la solución de JF Sebastian.

Answer 4

Estoy seguro de que hay una forma más limpia de hacerlo, pero empecé por un cierto camino e hice lo que tenía que hacer para que funcionara sin ninguna refactorización.

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

Gracias a @Steven por la técnica de reducción de lista con el set.

SALIDA

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

Answer 5

Intenté escribir una solución rápida y legible . Nunca sé que es mucho más lento que otras soluciones, pero a veces puede ser mucho más rápido porque además está optimizado para sublistas más largas o para muchos sublistas que son subconjuntos de cualquier grupo existente. (Esto está motivado por el texto de la pregunta "Tengo mucha lista pero no muchas listas diferentes"). El código utiliza menos memoria solo para datos condensados ​​que pueden ser mucho menos que los datos originales. Puede funcionar, por ejemplo, con un generador que recopila datos de un proceso en tiempo real. La estimación de complejidad es O (n log n). Creo que ningún algoritmo que usa ordenación puede ser de complejidad lineal.

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

Es más rápido que pillmuncher2 para subslists más largas que aproximadamente 8 elementos porque puede trabajar en más elementos juntos. También es muy rápido para listas con muchas sublistas similares o muchas sublistas que son subconjuntos de cualquier grupo existente. Es más rápido en un 25% sobre pillmuncher2 para lst_OP, pero más lento en un 15% para lst_BK.

Un ejemplo de datos de prueba con sublistas largos es [list(range(30)) + [-i] for i in range(100)] .

Intencionalmente escribí "common = common - dst_group" en lugar de usar el operador set -= o "set.difference_update", porque la actualización en el lugar no es efectiva si el conjunto del lado derecho es mucho más grande que el lado izquierdo.

Solución modificada de la pastilla para facilitar la lectura. La modificación es un poco más lenta que la original debido a la sustitución de un generador por list.append. Probablemente la solución rápida más legible.

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

Answer 6

Su problema es esencialmente una gráfica teórica, el problema de los componentes conectados, con un requisito adicional con respecto al orden de los elementos de cada componente.

En su programa, el conjunto de todas las listas forma un gráfico no dirigido, donde cada lista es un nodo en el gráfico. Decimos que dos listas están conectadas directamente si tienen elementos comunes y conectadas indirectamente, si existe una tercera lista a la que ambas están conectadas, directa o indirectamente. Dados, por ejemplo, tres listas [a, b], [b, c] y [c, d], entonces [a, b] y [b, c] están conectados directamente, así como [b, c] y [c, d], pero [a, b] y [c, d] están conectados indirectamente, ya que si bien no comparten elementos comunes, ambos comparten elementos con la misma lista [b, c].

Un grupo de nodos es un componente conectado si todos los nodos del grupo están conectados (directa o indirectamente) y ningún otro nodo en el gráfico está conectado a ningún nodo del grupo.

Existe un algoritmo de tiempo lineal bastante simple que genera todos los componentes conectados en un gráfico no dirigido. Usando eso, podemos definir una función que genere todas las listas de listas disjuntas condensadas, mientras mantenemos el orden de sus elementos:

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

Resultado:

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

La complejidad de tiempo de condense() es cuadrática, ya que cada lista debe compararse con todas las demás para descubrir si tienen elementos comunes. Por lo tanto, el rendimiento es horrible. ¿Podemos mejorarlo de alguna manera? Sí.

Dos listas se conectan directamente si tienen elementos comunes. Podemos cambiar esta relación: dos elementos se conectan directamente si pertenecen a la misma lista, y se conectan indirectamente si existe un tercer elemento que está conectado (directa o indirectamente) a ambos. Dados, por ejemplo, dos listas [a, b] y [b, c], entonces a y b están conectados directamente, así como b y c, y por lo tanto a y c están conectados indirectamente. Si también adaptamos la idea de JFSebastians de almacenar la posición de la primera aparición de cada elemento, podemos implementarlo de la siguiente manera:

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)

Todavía utiliza el algoritmo de componentes conectados, pero esta vez vemos los elementos como conectados, no como listas. Los resultados son los mismos que antes, pero como la complejidad del tiempo ahora es lineal, se ejecuta mucho más rápido.

Answer 7

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