'inverting' a dict

Discussion in 'Python' started by Irmen de Jong, Dec 30, 2003.

  1. Hi
    I have this dict that maps a name to a sequence of other names.
    I want to have it reversed, i.e., map the other names each to
    the key they belong to (yes, the other names are unique and
    they only occur once). Like this:

    { "key1": ("value1", "value2"), "key2": ("value3,) }

    -->

    { "value1": "key1", "value2": "key1", "value3": "key2" }

    What I'm doing is using a nested loop:

    dict2={}
    for (key,value) in dict1.items():
    for name in value:
    dict2[name] = key

    which is simple enough, but I'm hearing this little voice in
    the back of my head saying "there's a simpler solution".
    Is there? What is it? ;-)

    Thanks
    --Irmen.
     
    Irmen de Jong, Dec 30, 2003
    #1
    1. Advertising

  2. Irmen de Jong

    anton muhin Guest

    Irmen de Jong wrote:
    > Hi
    > I have this dict that maps a name to a sequence of other names.
    > I want to have it reversed, i.e., map the other names each to
    > the key they belong to (yes, the other names are unique and
    > they only occur once). Like this:
    >
    > { "key1": ("value1", "value2"), "key2": ("value3,) }
    >
    > -->
    >
    > { "value1": "key1", "value2": "key1", "value3": "key2" }
    >
    > What I'm doing is using a nested loop:
    >
    > dict2={}
    > for (key,value) in dict1.items():
    > for name in value:
    > dict2[name] = key
    >
    > which is simple enough, but I'm hearing this little voice in
    > the back of my head saying "there's a simpler solution".
    > Is there? What is it? ;-)
    >
    > Thanks
    > --Irmen.
    >


    It's seems like rather nice Python for me ;). Two more variants:

    inverted = {}
    for k, vs in d.iteritems():
    inverted.update(dict([(v, k) for v in vs]))

    map(
    lambda (k, vs): inverted.update(dict([(v, k) for v in vs])),
    d.iteritems()
    )

    happy new year,
    anton.
     
    anton muhin, Dec 30, 2003
    #2
    1. Advertising

  3. Irmen de Jong

    Guest

    On Tue, 30 Dec 2003 18:30:56 +0100, Irmen de Jong
    <> wrote:

    >Hi
    >I have this dict that maps a name to a sequence of other names.
    >I want to have it reversed, i.e., map the other names each to
    >the key they belong to (yes, the other names are unique and
    >they only occur once). Like this:
    >
    >{ "key1": ("value1", "value2"), "key2": ("value3,) }
    >
    >-->
    >
    >{ "value1": "key1", "value2": "key1", "value3": "key2" }
    >
    >What I'm doing is using a nested loop:
    >
    >dict2={}
    >for (key,value) in dict1.items():
    > for name in value:
    > dict2[name] = key
    >
    >which is simple enough, but I'm hearing this little voice in
    >the back of my head saying "there's a simpler solution".
    >Is there? What is it? ;-)
    >
    >Thanks
    >--Irmen.


    I had a need for a 'reverse' dictionary also. This is how I approached
    it:

    source_dict = {'A': 1,'B': 2,'C': 3,'D': 4}
    target_dict = {}
    for item in source_dict.iteritems():
    target_dict[item[1]] = item[0]

    Or, a bit more contrived....

    source_dict = {'A': [[1,2,3],100],'B': [[4,5,6],200],'C':
    [[7,8,9],300]}
    target_dict = {}
    for item in source_dict.iteritems():
    target_dict[item[1][1]] = item[0]

    Disclaimer: I'm a newbie
    Norm
     
    , Dec 30, 2003
    #3
  4. Irmen de Jong

    Yermat Guest

    or even shorter
    >>> d = {'key1' : ('value1','value2'), 'key2': ('value3',) }


    >>> dict([(v,k) for k in d.iterkeys() for v in d[k]])

    {'value3': 'key2', 'value2': 'key1', 'value1': 'key1'}


    "anton muhin" <> a écrit dans le message de
    news:bssgf2$10nt3$-berlin.de
    > Irmen de Jong wrote:
    >> Hi
    >> I have this dict that maps a name to a sequence of other names.
    >> I want to have it reversed, i.e., map the other names each to
    >> the key they belong to (yes, the other names are unique and
    >> they only occur once). Like this:
    >>
    >> { "key1": ("value1", "value2"), "key2": ("value3,) }
    >>
    >> -->
    >>
    >> { "value1": "key1", "value2": "key1", "value3": "key2" }
    >>
    >> What I'm doing is using a nested loop:
    >>
    >> dict2={}
    >> for (key,value) in dict1.items():
    >> for name in value:
    >> dict2[name] = key
    >>
    >> which is simple enough, but I'm hearing this little voice in
    >> the back of my head saying "there's a simpler solution".
    >> Is there? What is it? ;-)
    >>
    >> Thanks
    >> --Irmen.
    >>

    >
    > It's seems like rather nice Python for me ;). Two more variants:
    >
    > inverted = {}
    > for k, vs in d.iteritems():
    > inverted.update(dict([(v, k) for v in vs]))
    >
    > map(
    > lambda (k, vs): inverted.update(dict([(v, k) for v in vs])),
    > d.iteritems()
    > )
    >
    > happy new year,
    > anton.
     
    Yermat, Dec 30, 2003
    #4
  5. Irmen de Jong

    Peter Otten Guest

    Irmen de Jong wrote:

    > I have this dict that maps a name to a sequence of other names.
    > I want to have it reversed, i.e., map the other names each to
    > the key they belong to (yes, the other names are unique and
    > they only occur once). Like this:


    [...]

    > What I'm doing is using a nested loop:
    >
    > dict2={}
    > for (key,value) in dict1.items():
    > for name in value:
    > dict2[name] = key
    >
    > which is simple enough, but I'm hearing this little voice in
    > the back of my head saying "there's a simpler solution".
    > Is there? What is it? ;-)


    Here's what I've come up with:

    import itertools

    original = {"key1": ("value1", "value2"), "key2": ("value3",)}

    def forInv(original):
    result = {}
    for (key, values) in original.iteritems():
    for val in values:
    result[val] = key
    return result

    def updateInv(original):
    result = {}
    for (key, values) in original.iteritems():
    result.update(dict.fromkeys(values, key))
    return result

    def iterInv(original):
    result = {}
    for (key, values) in original.iteritems():
    result.update(dict(itertools.izip(values, itertools.repeat(key))))
    return result

    def iterInv2(original):
    return dict(itertools.chain(*[itertools.izip(values,
    itertools.repeat(key))
    for key, values in original.iteritems()]))

    def compInv(original):
    return dict([(val, key) for (key, values) in original.iteritems() for
    val in values])

    wanted = { "value1": "key1", "value2": "key1", "value3": "key2" }

    for inv in globals().values():
    if callable(inv):
    print inv.__name__,
    if inv(original) == wanted:
    print "OK"
    else:
    print "FAILED"

    Conclusion: my favourite toys, itertools and list comprehensions, lead to
    clumsier code - well, me at least. So I would recommend that you don't
    listen to that voice.

    Peter
     
    Peter Otten, Dec 30, 2003
    #5
  6. Irmen de Jong

    Jeff Epler Guest

    Does this listcomp give the right result?
    dict([(v, k) for k, vs in original.iteritems() for v in vs])

    Jeff
     
    Jeff Epler, Dec 30, 2003
    #6
  7. Irmen de Jong <> wrote in message news:<3ff1b688$0$319$4all.nl>...
    > Hi
    > I have this dict that maps a name to a sequence of other names.
    > I want to have it reversed, i.e., map the other names each to
    > the key they belong to (yes, the other names are unique and
    > they only occur once). Like this:
    >
    > { "key1": ("value1", "value2"), "key2": ("value3,) }
    >
    > -->
    >
    > { "value1": "key1", "value2": "key1", "value3": "key2" }
    >
    > What I'm doing is using a nested loop:
    >
    > dict2={}
    > for (key,value) in dict1.items():
    > for name in value:
    > dict2[name] = key
    >
    > which is simple enough, but I'm hearing this little voice in
    > the back of my head saying "there's a simpler solution".
    > Is there? What is it? ;-)
    >
    > Thanks
    > --Irmen.



    def invert_dict(D):
    return dict([(y,x) for (x,y) in D.items()])

    -- Wade Leftwich
    Ithaca, NY
     
    Wade Leftwich, Dec 31, 2003
    #7
  8. Yermat wrote:

    > or even shorter
    >
    >>>>d = {'key1' : ('value1','value2'), 'key2': ('value3',) }

    >
    >
    >>>>dict([(v,k) for k in d.iterkeys() for v in d[k]])

    >
    > {'value3': 'key2', 'value2': 'key1', 'value1': 'key1'}


    Yep, thanks, that must have been the solution that I was looking for!
    I understand list comprehensions, but keep forgetting about the
    multiple-loop-kind.

    --Irmen.
     
    Irmen de Jong, Dec 31, 2003
    #8
  9. Jeff Epler wrote:
    > Does this listcomp give the right result?
    > dict([(v, k) for k, vs in original.iteritems() for v in vs])


    Yes it does, and it's even more concise than Yermat's solution

    dict([(v,k) for k in d.iterkeys() for v in d[k]])

    because it avoids a dict lookup every loop cycle. Thanks Jeff!

    --Irmen
     
    Irmen de Jong, Dec 31, 2003
    #9
  10. Wade Leftwich wrote:

    > def invert_dict(D):
    > return dict([(y,x) for (x,y) in D.items()])


    No, this one only works for non-sequence-type values.
    I wanted to map every item of a value (a sequence)
    to the corresponding key.

    --Irmen
     
    Irmen de Jong, Dec 31, 2003
    #10
  11. dict2=dict([(a,b) for b in dict1.keys() for a in dict1])

    HTH


    "Irmen de Jong" <> wrote in message
    news:3ff1b688$0$319$4all.nl...
    | Hi
    | I have this dict that maps a name to a sequence of other names.
    | I want to have it reversed, i.e., map the other names each to
    | the key they belong to (yes, the other names are unique and
    | they only occur once). Like this:
    |
    | { "key1": ("value1", "value2"), "key2": ("value3,) }
    |
    | -->
    |
    | { "value1": "key1", "value2": "key1", "value3": "key2" }
    |
    | What I'm doing is using a nested loop:
    |
    | dict2={}
    | for (key,value) in dict1.items():
    | for name in value:
    | dict2[name] = key
    |
    | which is simple enough, but I'm hearing this little voice in
    | the back of my head saying "there's a simpler solution".
    | Is there? What is it? ;-)
    |
    | Thanks
    | --Irmen.
    |
     
    Elaine Jackson, Jan 1, 2004
    #11
  12. This is sort of off topic for the thread, but I've got a similar
    problem. In this case I have a dict like:

    { 'key1': 'value1', 'key2': value2}

    and I sometimes need to find the key for the value. All values/keys are
    unique. I just use a loop:

    for a in dict:
    if dict[a]== targ:
    return a
    return None

    But it'd be nice to have something faster, etc.


    Elaine Jackson wrote:
    > dict2=dict([(a,b) for b in dict1.keys() for a in dict1])
    >
    > HTH
    >
    >
    > "Irmen de Jong" <> wrote in message
    > news:3ff1b688$0$319$4all.nl...
    > | Hi
    > | I have this dict that maps a name to a sequence of other names.
    > | I want to have it reversed, i.e., map the other names each to
    > | the key they belong to (yes, the other names are unique and
    > | they only occur once). Like this:
    > |
    > | { "key1": ("value1", "value2"), "key2": ("value3,) }
    > |
    > | -->
    > |
    > | { "value1": "key1", "value2": "key1", "value3": "key2" }
    > |
    > | What I'm doing is using a nested loop:
    > |
    > | dict2={}
    > | for (key,value) in dict1.items():
    > | for name in value:
    > | dict2[name] = key
    > |
    > | which is simple enough, but I'm hearing this little voice in
    > | the back of my head saying "there's a simpler solution".
    > | Is there? What is it? ;-)
    > |
    > | Thanks
    > | --Irmen.
    > |
    >
    >


    --
    Bob van der Poel ** Wynndel, British Columbia, CANADA **
    EMAIL:
    WWW: http://www.kootenay.com/~bvdpoel
     
    Bob van der Poel, Jan 1, 2004
    #12
  13. Irmen de Jong <> wrote in message news:<3ff2cba6$0$316$4all.nl>...
    > Wade Leftwich wrote:
    >
    > > def invert_dict(D):
    > > return dict([(y,x) for (x,y) in D.items()])

    >
    > No, this one only works for non-sequence-type values.
    > I wanted to map every item of a value (a sequence)
    > to the corresponding key.
    >
    > --Irmen


    Try a nested list comprehension:

    >>> data = { "key1": ("value1", "value2"), "key2": ("value3",) }
    >>> dict([(v,k) for k,vlist in data.iteritems() for v in vlist])

    {'value3': 'key2', 'value2': 'key1', 'value1': 'key1'}


    Raymond Hettinger

    P.S. In Py2.4, it will be possible to write this without the
    brackets. The resulting generator expression is faster and more
    memory friendly:

    >>> dict((v,k) for k,vlist in data.iteritems() for v in vlist)

    {'value3': 'key2', 'value2': 'key1', 'value1': 'key1'}
     
    Raymond Hettinger, Jan 1, 2004
    #13
  14. Irmen de Jong

    Peter Abel Guest

    Irmen de Jong <> wrote in message news:<3ff1b688$0$319$4all.nl>...
    > Hi
    > I have this dict that maps a name to a sequence of other names.
    > I want to have it reversed, i.e., map the other names each to
    > the key they belong to (yes, the other names are unique and
    > they only occur once). Like this:
    >
    > { "key1": ("value1", "value2"), "key2": ("value3,) }
    >
    > -->
    >
    > { "value1": "key1", "value2": "key1", "value3": "key2" }
    >
    > What I'm doing is using a nested loop:
    >
    > dict2={}
    > for (key,value) in dict1.items():
    > for name in value:
    > dict2[name] = key
    >
    > which is simple enough, but I'm hearing this little voice in
    > the back of my head saying "there's a simpler solution".
    > Is there? What is it? ;-)
    >
    > Thanks
    > --Irmen.


    .... and after all there is always a hacky one-liner:
    >>> org = {"key1": ("value1", "value2"), "key2": ("value3",)}
    >>> dict(reduce(lambda l,(k,v):l.extend(zip(v,(k,)*len(v))) or l,org.items(),[]))

    {'value3': 'key2', 'value2': 'key1', 'value1': 'key1'}
    >>>


    Happy new year
    Peter
     
    Peter Abel, Jan 1, 2004
    #14
  15. Irmen de Jong

    sdd Guest

    Bob van der Poel wrote:
    > This is sort of off topic for the thread, but I've got a similar
    > problem. In this case I have a dict like:
    >
    > { 'key1': 'value1', 'key2': value2}
    >
    > and I sometimes need to find the key for the value. All values/keys are
    > unique. I just use a loop:
    >
    > for a in dict:
    > if dict[a]== targ:
    > return a
    > return None

    For a few hunts, I'd do:
    for key,value in dictionary.iteritems():
    if value == target:
    return key
    return None

    Of course, if it probed a lot between changes, it's better to

    reversedictionary = dict([(v,k) for k,v in dictionary.items()])

    -Scott David Daniels
     
    sdd, Jan 1, 2004
    #15
  16. Irmen de Jong

    Nick Vargish Guest

    Irmen de Jong <> writes:

    > I have this dict that maps a name to a sequence of other names.
    > I want to have it reversed, i.e., map the other names each to
    > the key they belong to (yes, the other names are unique and
    > they only occur once). Like this:


    That's almost spooky, I'm working on a project for which I needed
    something like this. I've just read the entire thread and my solution
    seems pretty naive:

    def invertdict(d):
    """Returns a dict whose key-value pairs are the value-key pairs of d."""
    ret = {}
    for k in d:
    ret[d[k]] = k
    return ret

    I only need to do it once or twice, at program start-up, so time-
    efficiency wasn't a critical factor. I'm guessing the list
    comprehension tactics are faster, though.

    Sorry about being late to the party, I've been away from Usenet for
    about three weeks...

    Nick

    --
    # sigmask || 0.2 || 20030107 || public domain || feed this to a python
    print reduce(lambda x,y:x+chr(ord(y)-1),' Ojdl!Wbshjti!=obwAcboefstobudi/psh?')
     
    Nick Vargish, Jan 8, 2004
    #16
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. arctan
    Replies:
    6
    Views:
    1,038
    arctan
    Oct 16, 2003
  2. MWells
    Replies:
    1
    Views:
    665
    spalding
    Jan 28, 2005
  3. spalding
    Replies:
    1
    Views:
    439
    Peter Blum
    Jan 28, 2005
  4. Niels Dybdahl

    inverting custom cursor

    Niels Dybdahl, Nov 21, 2005, in forum: Java
    Replies:
    0
    Views:
    416
    Niels Dybdahl
    Nov 21, 2005
  5. Gary Wessle

    inverting a string

    Gary Wessle, Aug 17, 2006, in forum: C++
    Replies:
    2
    Views:
    511
    Jerry Coffin
    Aug 18, 2006
Loading...

Share This Page