Wörterbuchzuordnung umkehren / umkehren

662

Bei einem Wörterbuch wie diesem:

my_map = {'a': 1, 'b': 2}

Wie kann man diese Karte umkehren, um zu erhalten:

inv_map = {1: 'a', 2: 'b'}
Brian M. Hunt
quelle

Antworten:

922

Für Python 2.7.x.

inv_map = {v: k for k, v in my_map.iteritems()}

Für Python 3+:

inv_map = {v: k for k, v in my_map.items()}
SilentGhost
quelle
4
In den letzten Python 2.7.x-Versionen my_map.items()funktioniert das auch
Valentin
29
Dies funktioniert mit der Ausnahme, dass es nicht funktioniert, wenn die Werte nicht einheitlich sind. In diesem Fall verlieren Sie einige Einträge
Gabuzo
2
Ja, als Implementierungsdetail. The order-preserving aspect of this new implementation is considered an implementation detail and should not be relied upon. Es gibt keine Garantie dafür, dass dies auch so bleibt. Schreiben Sie also keinen Code, der auf Dictdem gleichen Verhalten wie basiert OrderedDict.
Mattias
9
@ Mattias, dies gilt für Python 3.6. Für Version 3.7 ist die Auftragserhaltung offiziell: mail.python.org/pipermail/python-dev/2017-December/151283.html . BDFL sagte es.
InterDist
174

Angenommen, die Werte im Diktat sind eindeutig:

dict((v, k) for k, v in my_map.iteritems())
Rick unterstützt Monica
quelle
22
Die Werte müssen auch hashbar sein
John La Rooy
30
@ Buttons840: Wenn die Werte nicht eindeutig sind, gibt es ohnehin keine eindeutige Inversion des Wörterbuchs, oder mit anderen Worten, das Invertieren ist nicht sinnvoll.
Wrzlprmft
2
@ Buttons840 Für den Wert wird nur der letzte Schlüssel angezeigt. Es gibt wahrscheinlich keine Garantien für die iteritems()Ausgabe, die ausgegeben werden soll. Daher kann davon ausgegangen werden, dass ein beliebiger Schlüssel für einen nicht eindeutigen Wert zugewiesen wird, der unter bestimmten Bedingungen anscheinend reproduzierbar ist, im Allgemeinen jedoch nicht.
Evgeni Sergeev
2
Beachten Sie natürlich, dass es in Python 3 keine iteritems()Methode mehr gibt und dieser Ansatz nicht funktioniert. Verwenden Sie items()es stattdessen wie in der akzeptierten Antwort gezeigt. Ein Wörterbuchverständnis würde dies auch schöner machen als das Aufrufen dict.
Mark Amery
5
@Wrzlprmft Es gibt eine natürliche Definition für invers bei nicht eindeutigen Werten. Jeder Wert wird dem zu ihm führenden Schlüsselsatz zugeordnet.
Leo
135

Wenn die Werte in my_mapnicht eindeutig sind:

inv_map = {}
for k, v in my_map.iteritems():
    inv_map[v] = inv_map.get(v, [])
    inv_map[v].append(k)
Robert Rossney
quelle
56
... oder einfach inv_map.setdefault (v, []). append (k). Früher war ich ein Standarddict-Fan, aber dann wurde ich zu oft geschraubt und kam zu dem Schluss, dass explizit besser ist als implizit.
Alsuren
Diese Antwort ist falsch für Multi-Map, hier anhängen ist nutzlos, weil der Wert jedes Mal auf leere Liste zurückgesetzt wird, sollte set_default
Yaroslav Bulatov
1
@YaroslavBulatov nein, der hier gezeigte Code ist nicht fehlerhaft - inv_map.get(v, [])gibt die bereits hinzugefügte Liste zurück, falls vorhanden, sodass die Zuordnung nicht auf eine leere Liste zurückgesetzt wird. setdefaultwäre aber immer noch schöner.
Mark Amery
10
Ein Set wäre hier sinnvoller. Die Schlüssel sind (wahrscheinlich) hashbar und es gibt keine Reihenfolge. inv_map.setdefault(v, set()).add(k).
Artyer
1
Verwenden Sie in Python3 my_map.items()anstelle von my_map.iteritems().
Apitsch
42

So behalten Sie den Typ Ihres Mappings bei (vorausgesetzt, es handelt sich um eine dictoder eine dictUnterklasse):

def inverse_mapping(f):
    return f.__class__(map(reversed, f.items()))
fs.
quelle
4
Clever mag es sein, aber es funktioniert nicht, wenn mehr als ein Schlüssel den gleichen Wert im ursprünglichen Wörterbuch hat.
Rafael_Espericueta
1
@Rafael_Espericueta Das gilt für jede mögliche Antwort auf diese Frage, da eine Karte mit wiederholten Werten nicht invertierbar ist.
Mark Amery
2
@Mark_Amery Es kann in gewissem Sinne allgemeiner invertierbar sein. Zum Beispiel: D = {1: [1, 2], 2: [2, 3], 3: [1]}, Dinv = {1: [1, 3], 2: [1, 2], 3: [2]}. D ist ein Wörterbuch von zum Beispiel {Eltern: Kinder}, während Dinv das Wörterbuch {Kind: Eltern} ist.
Rafael_Espericueta
36

Versuche dies:

inv_map = dict(zip(my_map.values(), my_map.keys()))

(Beachten Sie, dass die Python-Dokumente in Wörterbuchansichten dies ausdrücklich garantieren .keys()und .values()ihre Elemente in derselben Reihenfolge haben, sodass der oben beschriebene Ansatz funktioniert.)

Alternative:

inv_map = dict((my_map[k], k) for k in my_map)

oder mit dem Diktatverständnis von Python 3.0

inv_map = {my_map[k] : k for k in my_map}
Sykora
quelle
1
Beachten Sie, dass dies nur funktioniert, wenn die Schlüssel eindeutig sind (was fast nie der Fall ist, wenn Sie sie invertieren möchten).
Gented
Laut python.org/dev/peps/pep-0274 sind Diktatverständnisse auch in Version 2.7+ verfügbar.
Kawu
24

Ein anderer, funktionalerer Weg:

my_map = { 'a': 1, 'b':2 }
dict(map(reversed, my_map.items()))
Brendan Maguire
quelle
3
Danke fürs Schreiben. Ich bin mir nicht sicher, ob dies vorzuziehen ist - um Guido Van Rossum in PEP 279 zu zitieren: " filterund mapsollte sterben und in Listenverständnisse subsumiert werden, nicht mehr Varianten wachsen lassen".
Brian M. Hunt
2
Ja, das ist ein fairer Punkt, Brian. Ich habe es nur als Gesprächspunkt hinzugefügt. Das Diktatverständnis ist für die meisten, die ich mir vorstellen kann, besser lesbar. (Und wahrscheinlich auch schneller, würde ich vermuten)
Brendan Maguire
3
Könnte weniger lesbar sein als andere, aber dieser Weg hat den Vorteil, dass er dictmit anderen Mapping-Typen wie collections.OrderedDictoder collections.defaultdict
Will S
10

Dies erweitert die Antwort von Robert und gilt für den Fall, dass die Werte im Diktat nicht eindeutig sind.

class ReversibleDict(dict):

    def reversed(self):
        """
        Return a reversed dict, with common values in the original dict
        grouped into a list in the returned dict.

        Example:
        >>> d = ReversibleDict({'a': 3, 'c': 2, 'b': 2, 'e': 3, 'd': 1, 'f': 2})
        >>> d.reversed()
        {1: ['d'], 2: ['c', 'b', 'f'], 3: ['a', 'e']}
        """

        revdict = {}
        for k, v in self.iteritems():
            revdict.setdefault(v, []).append(k)
        return revdict

Die Implementierung ist insofern eingeschränkt, als Sie nicht reversedzweimal verwenden und das Original zurückerhalten können. Es ist als solches nicht symmetrisch. Es wird mit Python 2.6 getestet. Hier ist ein Anwendungsfall, wie ich das resultierende Diktat drucke.

Wenn Sie lieber a setals a verwenden listmöchten und möglicherweise ungeordnete Anwendungen vorhanden sind, für die dies sinnvoll ist, anstatt sie zu setdefault(v, []).append(k)verwenden setdefault(v, set()).add(k).

Scharfsinn
quelle
Dies wäre auch ein guter Ort, um Mengen anstelle von Listen zu verwenden, dh revdict.setdefault(v, set()).add(k)
Mueslo
Natürlich, aber genau deshalb ist es ein guter Grund, es zu verwenden set . Es ist der intrinsische Typ, der hier gilt. Was ist, wenn ich alle Schlüssel finden möchte, bei denen die Werte nicht 1oder sind 2? Dann kann ich einfach d.keys() - inv_d[1] - inv_d[2](in Python 3)
Mueslo
9

Wir können ein Wörterbuch mit doppelten Schlüsseln auch umkehren, indem wir defaultdict:

from collections import Counter, defaultdict

def invert_dict(d):
    d_inv = defaultdict(list)
    for k, v in d.items():
        d_inv[v].append(k)
    return d_inv

text = 'aaa bbb ccc ddd aaa bbb ccc aaa' 
c = Counter(text.split()) # Counter({'aaa': 3, 'bbb': 2, 'ccc': 2, 'ddd': 1})
dict(invert_dict(c)) # {1: ['ddd'], 2: ['bbb', 'ccc'], 3: ['aaa']}  

Siehe hier :

Diese Technik ist einfacher und schneller als eine gleichwertige Technik dict.setdefault().

irudyak
quelle
6

Zum Beispiel haben Sie das folgende Wörterbuch:

dict = {'a': 'fire', 'b': 'ice', 'c': 'fire', 'd': 'water'}

Und du willst es in einer so umgekehrten Form bekommen:

inverted_dict = {'fire': ['a', 'c'], 'ice': ['b'], 'water': ['d']}

Erste Lösung . Verwenden Sie zum Invertieren von Schlüssel-Wert- Paaren in Ihrem Wörterbuch einen for-loop-Ansatz:

# Use this code to invert dictionaries that have non-unique values

inverted_dict = dict()
for key, value in dict.items():
    inverted_dict.setdefault(value, list()).append(key)

Zweite Lösung . Verwenden Sie einen Wörterbuchverständnisansatz für die Inversion:

# Use this code to invert dictionaries that have unique values

inverted_dict = {value: key for key, value in dict.items()}

Dritte Lösung . Verwenden Sie das Zurücksetzen des Inversionsansatzes (basiert auf der zweiten Lösung):

# Use this code to invert dictionaries that have lists of values

dict = {value: key for key in inverted_dict for value in my_map[key]}
Andy
quelle
4
dictist reserviert und sollte nicht für Variablennamen verwendet werden
crypdick
2
vergaß uns zu sagen was my_mapist
crypdick
dictio()? Meinten Sie dict()?
Georgy
5

Kombination aus Listen- und Wörterbuchverständnis. Kann doppelte Schlüssel verarbeiten

{v:[i for i in d.keys() if d[i] == v ] for k,v in d.items()}
SVJ
quelle
1
Wie stackoverflow.com/a/41861007/1709587 ist dies eine O (n²) -Lösung für ein Problem, das in O (n) mit ein paar zusätzlichen Codezeilen leicht gelöst werden kann.
Mark Amery
2

Wenn die Werte nicht eindeutig sind und Sie ein wenig Hardcore sind:

inv_map = dict(
    (v, [k for (k, xx) in filter(lambda (key, value): value == v, my_map.items())]) 
    for v in set(my_map.values())
)

Beachten Sie insbesondere bei einem großen Diktat, dass diese Lösung weitaus weniger effizient ist als die Antwort Python, die ein Mapping umkehrt / umkehrt, da es items()mehrere Schleifen durchläuft.

pcv
quelle
7
Dies ist einfach unlesbar und ein gutes Beispiel dafür, wie man keinen wartbaren Code schreibt. Ich werde nicht, -1weil es immer noch die Frage beantwortet, nur meine Meinung.
Russ Bradberry
1

Zusätzlich zu den anderen oben vorgeschlagenen Funktionen, wenn Sie Lambdas mögen:

invert = lambda mydict: {v:k for k, v in mydict.items()}

Oder Sie könnten es auch so machen:

invert = lambda mydict: dict( zip(mydict.values(), mydict.keys()) )
RussellStewart
quelle
2
-1; Alles, was Sie getan haben, ist, andere Antworten von der Seite zu nehmen und sie in ein Lambda zu setzen. Das Zuweisen eines Lambda zu einer Variablen ist ebenfalls eine PEP 8- Verletzung.
Mark Amery
1

Ich denke, der beste Weg, dies zu tun, besteht darin, eine Klasse zu definieren. Hier ist eine Implementierung eines "symmetrischen Wörterbuchs":

class SymDict:
    def __init__(self):
        self.aToB = {}
        self.bToA = {}

    def assocAB(self, a, b):
        # Stores and returns a tuple (a,b) of overwritten bindings
        currB = None
        if a in self.aToB: currB = self.bToA[a]
        currA = None
        if b in self.bToA: currA = self.aToB[b]

        self.aToB[a] = b
        self.bToA[b] = a
        return (currA, currB)

    def lookupA(self, a):
        if a in self.aToB:
            return self.aToB[a]
        return None

    def lookupB(self, b):
        if b in self.bToA:
            return self.bToA[b]
        return None

Lösch- und Iterationsmethoden sind bei Bedarf einfach zu implementieren.

Diese Implementierung ist weitaus effizienter als das Invertieren eines gesamten Wörterbuchs (was auf dieser Seite die beliebteste Lösung zu sein scheint). Ganz zu schweigen davon, dass Sie Ihrem SymDict beliebig viele Werte hinzufügen oder daraus entfernen können, und Ihr inverses Wörterbuch bleibt immer gültig - dies gilt nicht, wenn Sie das gesamte Wörterbuch einfach einmal umkehren.

NcAdams
quelle
Ich mag diese Idee, obwohl es gut wäre zu bemerken, dass sie zusätzlichen Speicher austauscht, um eine verbesserte Berechnung zu erreichen. Ein glücklicheres Medium kann den Spiegel zwischenspeichern oder träge berechnen. Es ist auch erwähnenswert, dass es mit z. B. Wörterbuchansichten und benutzerdefinierten Operatoren syntaktisch ansprechender gestaltet werden könnte.
Brian M. Hunt
@ BrianM.Hunt Es tauscht Speicher aus, aber nicht viel. Sie speichern nur zwei Sätze von Zeigern auf jedes Objekt. Wenn Ihre Objekte viel größer als einzelne Ganzzahlen sind, macht dies keinen großen Unterschied. Wenn Sie andererseits eine riesige Tabelle mit winzigen Objekten haben, müssen Sie möglicherweise diese Vorschläge berücksichtigen ...
NcAdams
Und ich stimme zu, hier gibt es noch mehr zu tun - ich könnte dies später in einen voll funktionsfähigen Datentyp
umwandeln
2
"Diese Implementierung ist viel effizienter als das Invertieren eines gesamten Wörterbuchs" - ähm, warum? Ich sehe keinen plausiblen Weg, wie dieser Ansatz einen signifikanten Leistungsvorteil haben kann. Auf diese Weise haben Sie noch zwei Wörterbücher. Wenn überhaupt, würde ich erwarten, dass dies langsamer ist als beispielsweise das Invertieren des Diktats mit einem Verständnis, denn wenn Sie das Diktat invertieren, kann Python plausibel im Voraus wissen, wie viele Buckets in der zugrunde liegenden C-Datenstruktur zugeordnet werden müssen, und die inverse Map erstellen ohne jemals anzurufen dictresize, aber dieser Ansatz verweigert Python diese Möglichkeit.
Mark Amery
1

Dies behandelt nicht eindeutige Werte und behält einen Großteil des Aussehens des eindeutigen Gehäuses bei.

inv_map = {v:[k for k in my_map if my_map[k] == v] for v in my_map.itervalues()}

Für Python 3.x, ersetzen itervaluesmit values.

Ersatz Kwisatz
quelle
3
Diese Lösung ist als Einzeiler recht elegant und verwaltet den Fall nicht eindeutiger Werte. Es hat jedoch eine Komplexität in O (n2), was bedeutet, dass es für mehrere Dutzend Elemente in Ordnung sein sollte, aber für den praktischen Gebrauch zu langsam wäre, wenn Sie mehrere Hunderttausend Elemente in Ihrem anfänglichen Wörterbuch haben. Die Lösungen, die auf einem Standarddiktat basieren, sind viel schneller als dieses.
Gabuzo
Gabuzo hat ganz recht. Diese Version ist (wohl) klarer als einige andere, eignet sich jedoch nicht für große Datenmengen.
Ersatz Kwisatz
0

Die Funktion ist für Werte der Typliste symmetrisch. Tupel werden in Listen verdeckt, wenn reverse_dict (reverse_dict (Wörterbuch)) ausgeführt wird.

def reverse_dict(dictionary):
    reverse_dict = {}
    for key, value in dictionary.iteritems():
        if not isinstance(value, (list, tuple)):
            value = [value]
        for val in value:
            reverse_dict[val] = reverse_dict.get(val, [])
            reverse_dict[val].append(key)
    for key, value in reverse_dict.iteritems():
        if len(value) == 1:
            reverse_dict[key] = value[0]
    return reverse_dict
Alf
quelle
0

Da Wörterbücher im Gegensatz zu Werten einen eindeutigen Schlüssel im Wörterbuch benötigen, müssen wir die umgekehrten Werte an eine Sortierliste anhängen, die in den neuen spezifischen Schlüsseln enthalten sein soll.

def r_maping(dictionary):
    List_z=[]
    Map= {}
    for z, x in dictionary.iteritems(): #iterate through the keys and values
        Map.setdefault(x,List_z).append(z) #Setdefault is the same as dict[key]=default."The method returns the key value available in the dictionary and if given key is not available then it will return provided default value. Afterward, we will append into the default list our new values for the specific key.
    return Map
EyoelD
quelle
0

Schnelle funktionale Lösung für nicht-bijektive Karten (Werte nicht eindeutig):

from itertools import imap, groupby

def fst(s):
    return s[0]

def snd(s):
    return s[1]

def inverseDict(d):
    """
    input d: a -> b
    output : b -> set(a)
    """
    return {
        v : set(imap(fst, kv_iter))
        for (v, kv_iter) in groupby(
            sorted(d.iteritems(),
                   key=snd),
            key=snd
        )
    }

Theoretisch sollte dies schneller sein als das Hinzufügen zur Menge (oder das Anhängen an die Liste) nacheinander, wie in der imperativen Lösung .

Leider müssen die Werte sortierbar sein, die Sortierung wird von groupby benötigt.

cjay
quelle
1
"Theoretisch sollte dies schneller sein, als das Set einzeln zu ergänzen (oder an die Liste anzuhängen)" - nein. Angesichts der nElemente im ursprünglichen Diktat ist Ihr Ansatz O(n log n)zeitlich komplex, da die Elemente des Diktats sortiert werden müssen, während der naive imperative Ansatz O(n)zeitlich komplex ist. Soweit ich weiß, ist Ihr Ansatz vielleicht schneller, bis er dictin der Praxis absurd groß ist , aber theoretisch ist er sicherlich nicht schneller.
Mark Amery
0

Versuchen Sie dies für Python 2.7 / 3.x.

inv_map={};
for i in my_map:
    inv_map[my_map[i]]=i    
print inv_map
dhvlnyk
quelle
-1

Ich würde es so in Python 2 machen.

inv_map = {my_map[x] : x for x in my_map}
Genghiscrade
quelle
Das gleichzeitige Iterieren von Schlüssel-Wert-Paaren über dict.items(oder iteritemsin Python 2) ist effizienter als das separate Extrahieren jedes Werts beim Iterieren von Schlüsseln.
Jpp
-1
def invertDictionary(d):
    myDict = {}
  for i in d:
     value = d.get(i)
     myDict.setdefault(value,[]).append(i)   
 return myDict
 print invertDictionary({'a':1, 'b':2, 'c':3 , 'd' : 1})

Dies liefert folgende Ausgabe: {1: ['a', 'd'], 2: ['b'], 3: ['c']}

RVR
quelle
Das gleichzeitige Iterieren von Schlüssel-Wert-Paaren über dict.items(oder iteritemsin Python 2) ist effizienter als das separate Extrahieren jedes Werts beim Iterieren von Schlüsseln. Außerdem haben Sie einer Antwort, die andere dupliziert, keine Erklärung hinzugefügt.
Jpp
-1
  def reverse_dictionary(input_dict):
      out = {}
      for v in input_dict.values():  
          for value in v:
              if value not in out:
                  out[value.lower()] = []

      for i in input_dict:
          for j in out:
              if j in map (lambda x : x.lower(),input_dict[i]):
                  out[j].append(i.lower())
                  out[j].sort()
      return out

Dieser Code gefällt so:

r = reverse_dictionary({'Accurate': ['exact', 'precise'], 'exact': ['precise'], 'astute': ['Smart', 'clever'], 'smart': ['clever', 'bright', 'talented']})

print(r)

{'precise': ['accurate', 'exact'], 'clever': ['astute', 'smart'], 'talented': ['smart'], 'bright': ['smart'], 'exact': ['accurate'], 'smart': ['astute']}
Shb8086
quelle
1
Im Allgemeinen sind Antworten viel hilfreicher, wenn sie eine Erklärung enthalten, was der Code tun soll und warum dies das Problem löst, ohne andere einzuführen.
Tom Aranda
1
Es ist sehr schön, aber viele ungeklärte Entscheidungen (zum Beispiel, warum Kleinbuchstaben für Schlüssel?)
Liudvikas Akelis
-2

Nicht etwas ganz anderes, nur ein bisschen umgeschriebenes Rezept aus dem Kochbuch. Es wird weiter optimiert, indem die setdefaultMethode beibehalten wird, anstatt sie jedes Mal durch die Instanz zu bringen:

def inverse(mapping):
    '''
    A function to inverse mapping, collecting keys with simillar values
    in list. Careful to retain original type and to be fast.
    >> d = dict(a=1, b=2, c=1, d=3, e=2, f=1, g=5, h=2)
    >> inverse(d)
    {1: ['f', 'c', 'a'], 2: ['h', 'b', 'e'], 3: ['d'], 5: ['g']}
    '''
    res = {}
    setdef = res.setdefault
    for key, value in mapping.items():
        setdef(value, []).append(key)
    return res if mapping.__class__==dict else mapping.__class__(res)

Entwarf, unter CPython 3.x ausgeführt zu werden, für 2.x zu ersetzen mapping.items()durchmapping.iteritems()

Auf meinem Computer läuft etwas schneller als andere Beispiele hier

thodnev
quelle
1
Das Ergebnis als dictzu erstellen und am Ende in die gewünschte Klasse zu konvertieren (anstatt mit einer Klasse des richtigen Typs zu beginnen), scheint mir hier einen völlig vermeidbaren Leistungseinbruch zu verursachen.
Mark Amery
-2

Ich habe dies mit Hilfe von Zyklus 'für' und Methode '.get ()' geschrieben und den Namen 'Karte' des Wörterbuchs in 'Karte1' geändert, weil 'Karte' eine Funktion ist.

def dict_invert(map1):
    inv_map = {} # new dictionary
    for key in map1.keys():
        inv_map[map1.get(key)] = key
    return inv_map
Taras Voitovych
quelle
-2

Wenn die Werte nicht eindeutig sind UND ein Hash sein kann (eine Dimension):

for k, v in myDict.items():
    if len(v) > 1:
        for item in v:
            invDict[item] = invDict.get(item, [])
            invDict[item].append(k)
    else:
        invDict[v] = invDict.get(v, [])
        invDict[v].append(k)

Und mit einer Rekursion, wenn Sie tiefer graben müssen als nur eine Dimension:

def digList(lst):
    temp = []
    for item in lst:
        if type(item) is list:
            temp.append(digList(item))
        else:
            temp.append(item)
    return set(temp)

for k, v in myDict.items():
    if type(v) is list:
        items = digList(v)
        for item in items:
            invDict[item] = invDict.get(item, [])
            invDict[item].append(k)
    else:
        invDict[v] = invDict.get(v, [])
        invDict[v].append(k)
mveith
quelle
Sie können Ihre Lösungen mithilfe eines Standarddikts verbessern: Es werden alle Zeilen invDict [item] = invDict.get (item, []) entfernt
gabuzo
Ihr erster Ansatz hier konvertiert {"foo": "bar"}zu {'b': ['foo'], 'a': ['foo'], 'r': ['foo']}und löst eine Ausnahme aus, wenn ein Wert in myDictnicht iterierbar ist. Ich bin mir nicht sicher, welches Verhalten Sie hier implementieren wollten, aber was Sie tatsächlich implementiert haben, wird so ziemlich niemand wollen.
Mark Amery