Das Konvertieren einer Liste in eine Menge ändert die Elementreihenfolge

Kürzlich habe ich festgestellt, dass beim Konvertieren von a listin setdie Reihenfolge der Elemente geändert und nach Zeichen sortiert wird.

Betrachten Sie dieses Beispiel:

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

Meine Fragen sind -

1. Warum passiert dies?
2. Wie kann ich Set-Operationen (insbesondere Set Difference) ausführen, ohne die ursprüngliche Reihenfolge zu verlieren?

1. A setist eine ungeordnete Datenstruktur, sodass die Einfügereihenfolge nicht beibehalten wird.

2. Dies hängt von Ihren Anforderungen ab. Wenn Sie eine normale Liste haben und einige Elemente entfernen möchten, während die Reihenfolge der Liste beibehalten wird, können Sie dies mit einem Listenverständnis tun:

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

   Wenn Sie eine Datenstruktur benötigen, die sowohl schnelle Mitgliedschaftstests als auch die Beibehaltung der Einfügereihenfolge unterstützt , können Sie die Schlüssel eines Python-Wörterbuchs verwenden, das ab Python 3.7 garantiert die Einfügereihenfolge beibehält:

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

   bmuss hier nicht wirklich bestellt werden - Sie können auch eine verwenden set. Beachten Sie, dass a.keys() - b.keys()die eingestellte Differenz als zurückgegeben wird set, sodass die Einfügereihenfolge nicht beibehalten wird.

   In älteren Versionen von Python können Sie collections.OrderedDictstattdessen Folgendes verwenden:

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

In Python 3.6, set()jetzt sollte die Reihenfolge halten, aber es gibt eine andere Lösung für Python 2 und 3:

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

Bei der Beantwortung Ihrer ersten Frage handelt es sich bei einem Satz um eine Datenstruktur, die für Satzoperationen optimiert ist. Wie eine mathematische Menge erzwingt oder behält sie keine bestimmte Reihenfolge der Elemente bei. Das abstrakte Konzept einer Menge erzwingt keine Reihenfolge, daher ist die Implementierung nicht erforderlich. Wenn Sie einen Satz aus einer Liste erstellen, kann Python die Reihenfolge der Elemente an die Anforderungen der internen Implementierung anpassen, die für einen Satz verwendet wird, der Satzoperationen effizient ausführen kann.

Entfernen Sie Duplikate und behalten Sie die Reihenfolge durch die unten stehende Funktion bei

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

Überprüfen Sie diesen Link

In der Mathematik gibt es Mengen und geordnete Mengen (Osets).

• set : ein ungeordneter Container mit eindeutigen Elementen (implementiert)
• oset : ein geordneter Container mit eindeutigen Elementen (NotImplemented)

In Python werden nur Mengen direkt implementiert. Wir können Osets mit regulären Diktiertasten ( 3.7+ ) emulieren .

Gegeben

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

Code

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

Demo

Replikate werden entfernt, die Einfügereihenfolge bleibt erhalten.

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

Set-ähnliche Operationen an Diktiertasten.

oset - b
# {1, 20, 210}

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

oset & b
# {2, 6}

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

Einzelheiten

Hinweis: Eine ungeordnete Struktur schließt geordnete Elemente nicht aus. Vielmehr ist eine aufrechterhaltene Bestellung nicht garantiert. Beispiel:

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

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

Man kann erfreut sein zu entdecken, dass eine Liste und ein Multiset (mset) zwei weitere faszinierende mathematische Datenstrukturen sind:

• Liste : Ein geordneter Container mit Elementen, der Replikate zulässt (implementiert)
• mset : Ein ungeordneter Container mit Elementen, der Replikate zulässt (NotImplemented) *

Zusammenfassung

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

^{* Ein Multiset kann indirekt mit collections.Counter()einer diktartigen Abbildung von Multiplizitäten (Zählungen) emuliert werden .}

Wie in anderen Antworten angegeben, sind Mengen Datenstrukturen (und mathematische Konzepte), die die Elementreihenfolge nicht beibehalten -

Durch die Verwendung einer Kombination aus Sätzen und Wörterbüchern ist es jedoch möglich, dass Sie das erreichen, was Sie möchten - versuchen Sie es mit folgenden Ausschnitten:

# 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

Aufbauend auf Svens Antwort fand ich die Verwendung von Sammlungen. OrderedDict hat mir so geholfen, das zu erreichen, was Sie wollen, und ich kann dem Diktat weitere Elemente hinzufügen:

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

Wenn Sie Elemente hinzufügen möchten, diese aber dennoch wie ein Set behandeln möchten, können Sie Folgendes tun:

z['nextitem']=None

Und Sie können eine Operation wie z.keys () für das Diktat ausführen und das Set erhalten:

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

Eine Implementierung des oben genannten Konzepts mit der höchsten Punktzahl bringt es zurück zu einer Liste:

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

Getestet (kurz) auf Python 3.6 und Python 2.7.

Wenn Ihre beiden Anfangslisten eine kleine Anzahl von Elementen enthalten, für die Sie eine Differenzoperation festlegen möchten, anstatt collections.OrderedDictdie Implementierung zu verwenden, die die Implementierung kompliziert und weniger lesbar macht, können Sie Folgendes verwenden:

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

Die zeitliche Komplexität ist nicht so gut, aber ordentlich und leicht zu lesen.

Es ist interessant, dass die Leute immer das Problem der realen Welt benutzen, um Witze über die Definition in der theoretischen Wissenschaft zu machen.

Wenn set die Reihenfolge hat, müssen Sie zuerst die folgenden Probleme herausfinden. Wenn Ihre Liste doppelte Elemente enthält, wie sollte die Reihenfolge sein, wenn Sie sie in ein Set verwandeln? Was ist die Reihenfolge, wenn wir zwei Mengen vereinen? Wie ist die Reihenfolge, wenn wir zwei Mengen mit unterschiedlicher Reihenfolge auf denselben Elementen schneiden?

Außerdem ist set bei der Suche nach einem bestimmten Schlüssel viel schneller, was bei der Set-Operation sehr gut ist (und deshalb benötigen Sie ein Set, aber keine Liste).

Wenn Sie sich wirklich für den Index interessieren, behalten Sie ihn einfach als Liste bei. Wenn Sie dennoch die Set-Operation für die Elemente in vielen Listen ausführen möchten, erstellen Sie am einfachsten ein Wörterbuch für jede Liste mit denselben Schlüsseln im Set sowie einen Listenwert, der den gesamten Index des Schlüssels in der ursprünglichen Liste enthält.

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}

Hier ist eine einfache Möglichkeit, dies zu tun:

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