Convertir una lista en un orden de elementos de cambios establecidos

Recientemente noté que cuando estoy convirtiendo lista, setel orden de los elementos cambia y se ordena por carácter.

Considere este ejemplo:

x=[1,2,20,6,210]
print x 
# [1, 2, 20, 6, 210] # the order is same as initial order

set(x)
# set([1, 2, 20, 210, 6]) # in the set(x) output order is sorted

Mis preguntas son:

1. ¿Por qué está pasando esto?
2. ¿Cómo puedo realizar operaciones de set (especialmente Set Difference) sin perder el orden inicial?

1. A setes una estructura de datos desordenada, por lo que no conserva el orden de inserción.

2. Depende de sus requisitos. Si tiene una lista normal y desea eliminar algún conjunto de elementos conservando el orden de la lista, puede hacerlo con una lista de comprensión:

   >>> a = [1, 2, 20, 6, 210]
   >>> b = set([6, 20, 1])
   >>> [x for x in a if x not in b]
   [2, 210]

   Si necesita una estructura de datos que admita tanto las pruebas de membresía rápidas como la preservación del orden de inserción , puede usar las claves de un diccionario de Python, que a partir de Python 3.7 garantiza preservar el orden de inserción:

   >>> a = dict.fromkeys([1, 2, 20, 6, 210])
   >>> b = dict.fromkeys([6, 20, 1])
   >>> dict.fromkeys(x for x in a if x not in b)
   {2: None, 210: None}

   brealmente no es necesario pedirlo aquí, también podría usar un set. Tenga en cuenta que a.keys() - b.keys()devuelve la diferencia establecida como a set, por lo que no conservará el orden de inserción.

   En versiones anteriores de Python, puede usar collections.OrderedDicten su lugar:

   >>> a = collections.OrderedDict.fromkeys([1, 2, 20, 6, 210])
   >>> b = collections.OrderedDict.fromkeys([6, 20, 1])
   >>> collections.OrderedDict.fromkeys(x for x in a if x not in b)
   OrderedDict([(2, None), (210, None)])

En Python 3.6, set()ahora debería mantener el orden, pero hay otra solución para Python 2 y 3:

>>> x = [1, 2, 20, 6, 210]
>>> sorted(set(x), key=x.index)
[1, 2, 20, 6, 210]

Respondiendo a su primera pregunta, un conjunto es una estructura de datos optimizada para operaciones de conjuntos. Como un conjunto matemático, no impone ni mantiene ningún orden particular de los elementos. El concepto abstracto de un conjunto no impone el orden, por lo que no se requiere la implementación. Cuando crea un conjunto a partir de una lista, Python tiene la libertad de cambiar el orden de los elementos según las necesidades de la implementación interna que utiliza para un conjunto, que puede realizar operaciones de conjunto de manera eficiente.

eliminar duplicados y preservar el orden mediante la siguiente función

def unique(sequence):
    seen = set()
    return [x for x in sequence if not (x in seen or seen.add(x))]

revisa este enlace

En matemáticas, hay conjuntos y conjuntos ordenados (osets).

• conjunto : un contenedor desordenado de elementos únicos (implementado)
• oset : un contenedor ordenado de elementos únicos (No implementado)

En Python, solo los conjuntos se implementan directamente. Podemos emular osets con claves de dictado regulares ( 3.7+ ).

Dado

a = [1, 2, 20, 6, 210, 2, 1]
b = {2, 6}

Código

oset = dict.fromkeys(a).keys()
# dict_keys([1, 2, 20, 6, 210])

Manifestación

Se eliminan las réplicas, se conserva el orden de inserción.

list(oset)
# [1, 2, 20, 6, 210]

Operaciones tipo set en claves dictadas.

oset - b
# {1, 20, 210}

oset | b
# {1, 2, 5, 6, 20, 210}

oset & b
# {2, 6}

oset ^ b
# {1, 5, 20, 210}

Detalles

Nota: una estructura desordenada no excluye los elementos ordenados. Más bien, el orden mantenido no está garantizado. Ejemplo:

assert {1, 2, 3} == {2, 3, 1}                    # sets (order is ignored)

assert [1, 2, 3] != [2, 3, 1]                    # lists (order is guaranteed)

Uno puede estar satisfecho al descubrir que una lista y conjunto múltiple (mset) son dos más fascinantes, estructuras de datos matemáticos:

• lista : un contenedor ordenado de elementos que permite réplicas (implementado)
• mset : un contenedor desordenado de elementos que permite réplicas (NotImplemented) *

Resumen

Container | Ordered | Unique | Implemented
----------|---------|--------|------------
set       |    n    |    y   |     y
oset      |    y    |    y   |     n
list      |    y    |    n   |     y
mset      |    n    |    n   |     n*  

^{* Un multiset se puede emular indirectamente con collections.Counter()un mapeo de multiplicidades (recuentos) similar a un dictado .}

Como se indica en otras respuestas, los conjuntos son estructuras de datos (y conceptos matemáticos) que no conservan el orden de los elementos:

Sin embargo, al usar una combinación de conjuntos y diccionarios, es posible que pueda lograr lo que quiera; intente usar estos fragmentos:

# save the element order in a dict:
x_dict = dict(x,y for y, x in enumerate(my_list) )
x_set = set(my_list)
#perform desired set operations
...
#retrieve ordered list from the set:
new_list = [None] * len(new_set)
for element in new_set:
   new_list[x_dict[element]] = element

Sobre la base de la respuesta de Sven, encontré que el uso de collections.OrderedDict me ayudó a lograr lo que quieres y además me permite agregar más elementos al dict:

import collections

x=[1,2,20,6,210]
z=collections.OrderedDict.fromkeys(x)
z
OrderedDict([(1, None), (2, None), (20, None), (6, None), (210, None)])

Si desea agregar elementos pero aún así tratarlo como un conjunto, puede hacer lo siguiente:

z['nextitem']=None

Y puede realizar una operación como z.keys () en el dict y obtener el conjunto:

z.keys()
[1, 2, 20, 6, 210]

Una implementación del concepto de puntuación más alta anterior que lo devuelve a una lista:

def SetOfListInOrder(incominglist):
    from collections import OrderedDict
    outtemp = OrderedDict()
    for item in incominglist:
        outtemp[item] = None
    return(list(outtemp))

Probado (brevemente) en Python 3.6 y Python 2.7.

En caso de que tenga una pequeña cantidad de elementos en sus dos listas iniciales en las que desee realizar una operación de diferenciación de conjuntos, en lugar de usar lo collections.OrderedDictque complica la implementación y lo hace menos legible, puede usar:

# initial lists on which you want to do set difference
>>> nums = [1,2,2,3,3,4,4,5]
>>> evens = [2,4,4,6]
>>> evens_set = set(evens)
>>> result = []
>>> for n in nums:
...   if not n in evens_set and not n in result:
...     result.append(n)
... 
>>> result
[1, 3, 5]

Su complejidad temporal no es tan buena, pero es ordenada y fácil de leer.

Es interesante que la gente siempre use "problema del mundo real" para bromear sobre la definición en ciencia teórica.

Si el conjunto tiene orden, primero debe resolver los siguientes problemas. Si su lista tiene elementos duplicados, ¿cuál debería ser el orden cuando la convierta en un conjunto? ¿Cuál es el orden si unimos dos conjuntos? ¿Cuál es el orden si intersecamos dos conjuntos con diferente orden en los mismos elementos?

Además, el conjunto es mucho más rápido en la búsqueda de una clave en particular, lo cual es muy bueno en el funcionamiento de conjuntos (y es por eso que necesita un conjunto, pero no una lista).

Si realmente le importa el índice, guárdelo como una lista. Si aún desea realizar la operación de conjunto en los elementos en muchas listas, la forma más sencilla es crear un diccionario para cada lista con las mismas claves en el conjunto junto con un valor de lista que contiene todo el índice de la clave en la lista original.

def indx_dic(l):
    dic = {}
    for i in range(len(l)):
        if l[i] in dic:
            dic.get(l[i]).append(i)
        else:
            dic[l[i]] = [i]
    return(dic)

a = [1,2,3,4,5,1,3,2]
set_a  = set(a)
dic_a = indx_dic(a)

print(dic_a)
# {1: [0, 5], 2: [1, 7], 3: [2, 6], 4: [3], 5: [4]}
print(set_a)
# {1, 2, 3, 4, 5}

He aquí una forma sencilla de hacerlo:

x=[1,2,20,6,210]
print sorted(set(x))