Velocity Reviews > Dict to "flat" list of (key,value)

# Dict to "flat" list of (key,value)

Nicolas Girard
Guest
Posts: n/a

 07-30-2003
Hi,

Forgive me if the answer is trivial, but could you tell me how to achieve
the following:

{k1:[v1,v2],k2:v3,...} --> [[k1,v1],[k1,v2],[k2,v3],...]

The subtle point (at least to me) is to "flatten" values that are lists.

Nicolas

----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---

Bengt Richter
Guest
Posts: n/a

 07-30-2003
On Wed, 30 Jul 2003 21:26:19 +0200, Nicolas Girard <(E-Mail Removed)> wrote:

>Hi,
>
>Forgive me if the answer is trivial, but could you tell me how to achieve
>the following:
>
>{k1:[v1,v2],k2:v3,...} --> [[k1,v1],[k1,v2],[k2,v3],...]
>
>The subtle point (at least to me) is to "flatten" values that are lists.
>

Assuming v3 and others like it can't be references to lists
(or how could you tell it from the format of k1's list?):

(I quoted your names to avoid haing to define them separately)

>>> d = {'k1':['v1','v2'],'k2':'v3'}
>>> flat = []
>>> for k,v in d.items():

... if isinstance(v,list):
... for v2 in v:
... flat.append([k,v2])
... else:
... flat.append([k,v])
...
>>> flat

[['k2', 'v3'], ['k1', 'v1'], ['k1', 'v2']]

Or would you prefer an inscrutable one-liner

Note that there is no guarantee of any particular order in d.items(),
though you could sort them:

>>> d = {'k1':['v1','v2'],'k2':'v3'}
>>> flat = []
>>> items = d.items()
>>> items.sort() # on keys
>>> for k,v in items:

... if isinstance(v,list):
# Note that v is a list here, but does have pre-existing order you might want to keep.
# If you wanted to guarantee sorted output of the v2's, you could
# do v.sort() here, though you might surprise others holding references
# to those lists, since they would see the sorting. To avoid that, make a copy first, e.g.,
# v = v[:]; v.sort() #(untested, but I think it should work

... for v2 in v:
... flat.append([k,v2])
... else:
... flat.append([k,v])
...
>>> flat

[['k1', 'v1'], ['k1', 'v2'], ['k2', 'v3']]

Regards,
Bengt Richter

Brandon Beck
Guest
Posts: n/a

 07-30-2003
Someone will definitely come up with a better solution than this, but
this could work for you at least as a first try

import types
def flatten(d, iterables=(types.ListType, types.TupleType)):
rv = []
for k, v in d.items():
if type(v) in iterables:
rv += [[k,x] for x in v]
else:
rv += [[k,v]]
return rv

If you want to change the types of things that get iterated over, just
pass in a second parameter of your own.

Hope that helps,
Brandon

"Nicolas Girard" <(E-Mail Removed)> wrote in
message news(E-Mail Removed) m.net...
> Hi,
>
> Forgive me if the answer is trivial, but could you tell me how to

achieve
> the following:
>
> {k1:[v1,v2],k2:v3,...} --> [[k1,v1],[k1,v2],[k2,v3],...]
>
> The subtle point (at least to me) is to "flatten" values that are

lists.
>
> Nicolas
>
>
>
> ----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet

News==----
> http://www.newsfeed.com The #1 Newsgroup Service in the World!
>100,000 Newsgroups
> ---= 19 East/West-Coast Specialized Servers - Total Privacy via

Encryption =---

David C. Fox
Guest
Posts: n/a

 07-30-2003
Nicolas Girard wrote:
> Hi,
>
> Forgive me if the answer is trivial, but could you tell me how to achieve
> the following:
>
> {k1:[v1,v2],k2:v3,...} --> [[k1,v1],[k1,v2],[k2,v3],...]
>
> The subtle point (at least to me) is to "flatten" values that are lists.

Well, I can get you at least part way, but there is an ambiguity in your
original data structure which causes problems:

1. d.items() will get you

[(k1, [v1, v2]), (k2, v3), ...]

2. Now, you want to expand out the list elements where the second part
of each tuple is a list, which you can do with.

flatten = lambda u: map(lambda x: (u[0], x), u[1])

or, if the double lambda expression is confusing:

def flatten(u):
return map(lambda x: (u[0], x), u[1])

(I've used a tuple (u[0], x) instead of a list, because your [k1, vn]
are always pairs, but you can use a list if you prefer)

Then flatten will take the nested element

(k1, [v1, v2])

and convert it to a list of tuples

[(k1, v1), [k2, v2])]

3. You want to apply flatten to each element of d.items(), which you
can do with

lol = map(flatten, d.items())

which will give you a list of lists of tuples,

4. and then reduce that to a list of tuples with

Unfortunately, this doesn't quite work with your example above, because
flatten won't work properly when applied to (k2, v3). If v3 is a
sequence, it will instead give you [(k2, v3[0]), (k2, v3[1]), ...],
which is probably not what you want (especially if v3 is a string - try
flatten manually and see what happens). If v3 is not a sequence, you'll
get a TypeError saying that argument 2 to map() must support iteration.

If you *know* that v3 will NEVER be a list, you can modify flatten to
handle the special case like so:

def flatten(u):
if isinstance(u[1], type([])):
return (u[1], [u[2]])
return map(lambda x: (u[0], x), u[1])

Alternatively, if you can modify how the initial dictionary is generated
to ensure that cases where a key has a single value always appear as
k2: [v3] instead of k2: v3, then you can use the steps above without
modification. This is probably better if it is feasible, because your
original data structure is inherently ambiguous unless you know that v3
will never be a list.

David

>
> Nicolas
>
>
>
> ----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
> http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
> ---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---

David C. Fox
Guest
Posts: n/a

 07-30-2003
David C. Fox wrote:

Oops - a mistake and an omission

> 4. and then reduce that to a list of tuples with
>

You need to import the operator module first.

> def flatten(u):
> if isinstance(u[1], type([])):
> return (u[1], [u[2]])
> return map(lambda x: (u[0], x), u[1])

I got my cases reversed - that should be "if not isinstance...

Mike Rovner
Guest
Posts: n/a

 07-31-2003
Nicolas Girard wrote:
> Forgive me if the answer is trivial, but could you tell me how to
> achieve the following:
>
> {k1:[v1,v2],k2:v3,...} --> [[k1,v1],[k1,v2],[k2,v3],...]

[list(i) for i in d.items()]

Mike

Mike Rovner
Guest
Posts: n/a

 07-31-2003
Mike Rovner wrote:
> Nicolas Girard wrote:
>> Forgive me if the answer is trivial, but could you tell me how to
>> achieve the following:
>>
>> {k1:[v1,v2],k2:v3,...} --> [[k1,v1],[k1,v2],[k2,v3],...]

>
>[list(i) for i in d.items()]

Sorry, I missed v1,v2 flattening.

Raymond Hettinger
Guest
Posts: n/a

 08-02-2003

"Nicolas Girard" <(E-Mail Removed)> wrote in message
news(E-Mail Removed) m.net...
> Hi,
>
> Forgive me if the answer is trivial, but could you tell me how to achieve
> the following:
>
> {k1:[v1,v2],k2:v3,...} --> [[k1,v1],[k1,v2],[k2,v3],...]
>
> The subtle point (at least to me) is to "flatten" values that are lists.

by showing a loop that differentiated the two cases
of inner lists vs single values. One further thought,
is that the original data structure could be improved
by building it so that every value is in a list:

{k1:[v1,v2],k2:[v3],...}

This is typically done by building the values with setdefault:

index = {}
for pagenum in range(len(pages)):
page = pages[pagenum]
for word in page:
index.setdefault(word, []).append(pagenum)

The new structure is much more easily flattened:

[(k,v) for k, values in newstruct.iteritems() for v in values]

it-all-starts-with-a-good-data-structure-ly yours,

Raymond Hettinger

John Machin
Guest
Posts: n/a

 08-03-2003
On Sat, 02 Aug 2003 12:41:19 GMT, "Raymond Hettinger"
<(E-Mail Removed)> wrote:

>it-all-starts-with-a-good-data-structure-ly yours,

Amen, brother.

Even worse: I recall seeing code somewhere that had a data structure
like this:

{k1: [v1,v2], k2: v3, k3: None, ...}
{k1: [v1,v2], k2: [v3], k3: [], ...}

I liked the elegant code example for building a book index. However in
practice the user requirement would be not to have duplicated page
numbers when a word occurs more than once on the same page. If you can
achieve that elegantly, please post it!

Cheers,
John

Scott David Daniels
Guest
Posts: n/a

 08-03-2003
John Machin wrote:

> On Sat, 02 Aug 2003 12:41:19 GMT, "Raymond Hettinger"
> <(E-Mail Removed)> wrote:
>>

[a perfectly fine chunk of code]
>>it-all-starts-with-a-good-data-structure-ly yours,

>
> I liked the elegant code example for building a book index. However in
> practice the user requirement would be not to have duplicated page
> numbers when a word occurs more than once on the same page. If you can
> achieve that elegantly, please post it!

OK, I'll bite:
def genindex(pages):
index = {}
for pagenum in range(len(pages)):
page = pages[pagenum]
for word in page:
index.setdefault(word, {})[pagenum] = None

or with 2.3:
def genindex(pages):
index = {}
for pagenum, page in enumerate(pages):
for word in page:
index.setdefault(word, {})[pagenum] = None
return index

With either one, flattening looks like:
def flatten(index):
flattened = [(word, list(pages)) for word, pages
in index.items()]
for word, pages in flattened:
pages.sort()
flattened.sort()
return flatten

For fun, try:

book = ['this is a test'.split(),
'this is only a test'.split(),
'had this been a real function, you care a bit'.split()]
for word, pages in flatten(index(book)):
print word, pages

-Scott David Daniels
http://www.velocityreviews.com/forums/(E-Mail Removed)