Início / coding / Perguntas / 79249078
Accepted
ariko stephen
Asked: 2024-12-04 04:23:15 +0800 CST

Algoritmo eficiente que retorna uma lista de listas únicas dada uma lista de listas como entrada

  • 772

Dada uma lista pythonlists = [ [1, 2], [2, 1], [3, 4] ] de listas contendo números ie , o problema é retornar uma lista de todas as listas exclusivas da lista de entrada. Uma lista é considerada uma duplicata se puder ser gerada de outra lista reordenando os itens na lista. ie [2, 1]é uma duplicata de [1, 2].Dada a entrada [ [1, 2], [2, 1], [3, 4] ], a saída deve ser [ [1, 2], [3, 4]]. Qualquer reordenação de [ [1, 2], [3, 4]] também está correta ie [1, 2], [4, 3]],

Minha abordagem é primeiro classificar todas as listas na lista de entrada, converter as listas em tuplas, usar uma estrutura de dados definida para filtrar tuplas duplicadas e, finalmente, converter as tuplas exclusivas de volta para listas. A complexidade de tempo para classificar todas as listas é O(m*nlogn)onde m é o número de listas e n é o tamanho de cada lista (assumindo listas do mesmo tamanho). Converter as listas em tuplas leva O(mn)tempo, criar um conjunto a partir das tuplas leva O(mn), converter o conjunto de tuplas exclusivas de volta para listas também leva, O(mn) tornando a complexidade de tempo total O (mnlogn + mn + mn + mn) = O(mnlogn).

Podemos fazer melhor do que O(mnlogn)?

Código:

def find_unique(lists):
  sorted_lists = [ sorted(lst) for lst in lists]
  tuples = [tuple(lst) for lst in sorted_lists]
  unique_tuples = set(tuples)
  return list(unique_tuples)
python

2 respostas

  1. Best Answer

    Você pode obter uma solução O(m*n) contanto que a "chave" que você esteja usando seja O(m*n). Isso pode ser feito de duas maneiras.

    Se as listas internas não puderem conter duplicatas, então um conjunto de conjuntos congelados é uma solução elegante. Note frozenset(mylist)que é O(n):

    def unique(lists):
    seen = set()
    result = []
    for sub in lists:
        key = frozenset(sub)
        if key not in seen:
            result.append(sub)
            seen.add(key)
    return result

    O acima retorna a primeira lista "única" vista que está realmente na entrada. Se qualquer ordem de uma lista única for válida, mesmo uma ordem não vista na entrada original (presumo que seja esse o caso porque é isso que sua solução faz), então talvez mais sucintamente:

    def unique(lists):
    return list(map(list, set(map(frozenset, lists))))

    Se as listas internas puderem conter duplicatas, o procedimento acima não funcionará, mas você pode usar um collections.Counterque pode atuar como um multiconjunto e, então, usar um frozent-set dos itens no contador:

    from collections import Counter

def unique(lists):
    seen = set()
    result = []
    for sub in lists:
        key = frozenset(Counter(sub).items())
        if key not in seen:
            result.append(sub)
            seen.add(key)
    return result

    Observe que, se nfor pequeno, aposto que a sortedsolução será mais rápida.

    • 3

  2. Aqui está uma abordagem da teoria dos grafos, usada igraphpara transformar uma lista de tuplas em um grafo não direcionado

    import igraph as ig
g = ig.Graph.TupleList(lists).simplify()
vnm = g.vs()["name"]
[[vnm[p], vnm[q]] for p, q in g.get_edgelist()]

    o que dá

    [[1, 2], [3, 4]]
    • 0

relate perguntas