list comprehention

[Mathijs]

Hi,

Python beginner here and very much enjoying it. I'm looking for a
pythonic way to find how many listmembers are also present in a reference
list. Don't count duplicates (eg. if you already found a matching member
in the ref list, you can't use the ref member anymore).

Example1:
ref=[2, 2, 4, 1, 1]
list=[2, 3, 4, 5, 3]
solution: 2

Example2:
ref=[2, 2, 4, 1, 1]
list=[2, 2, 5, 2, 4]
solution: 3 (note that only the first two 2's count, the third 2 in the
list should not be counted)

Any suggestions or comments?

Thanks.
M.


#my failing effort:
sum([min(r.count(n)-l[:i].count(n),l.cou nt(n)) for i,n in enumerate(l)])

#test lists
import random
#reference list
r=[random.randint( 1,5) for n in range(5)]
#list
l=[random.randint( 1,5) for n in range(5)]

[Tim Chase]

Re: list comprehention

> Python beginner here and very much enjoying it. I'm looking[color=blue]
> for a pythonic way to find how many listmembers are also
> present in a reference list. Don't count duplicates (eg. if
> you already found a matching member in the ref list, you can't
> use the ref member anymore).
>
> Example1:
> ref=[2, 2, 4, 1, 1]
> list=[2, 3, 4, 5, 3]
> solution: 2
>
> Example2:
> ref=[2, 2, 4, 1, 1]
> list=[2, 2, 5, 2, 4]
> solution: 3 (note that only the first two 2's count, the third
> 2 in the list should not be counted)[/color]

It sounds like you're looking for "set" operations: (using "ell"
for clarity)
[color=blue][color=green][color=darkred]
>>> from sets import Set
>>> a = [2,2,4,1,1]
>>> b = [2,3,4,5,3]
>>> setA = Set(a)
>>> setB = Set(b)
>>> results = setA.intersecti on(setB)
>>> results[/color][/color][/color]
Set([2,4])[color=blue][color=green][color=darkred]
>>> intersection = [x for x in results]
>>> intersection[/color][/color][/color]
[2,4]


I'm a tad confused by the help, as it sounds like sets are
supposed to be first-class citizens, but in ver2.3.5 that I'm
running here (or rather "there", on a friend's box), I have to
"import sets" which I didn't see mentioned in the reference manual.

-one of many tims on the list
tim = Set(["bald", "vegetarian ", "loving husband"])

:)

[markscala@gmail.com]

Re: list comprehention

def reference(alist 1,alist2):
counter = 0
for x in lis:
if x in ref:
ref.pop(ref.ind ex(x))
counter += 1
return counter

this works I think for your examples, but you should check it against
them and other cases.
good luck

[markscala@gmail.com]

Re: list comprehention

revision of previous:

def reference(refli st,alist2):
counter = 0
for x in alist2:
if x in reflist:
reflist.pop(ref list.index(x))
counter += 1
return counter

[markscala@gmail.com]

Re: list comprehention

another approach:

ref = [2,2,4,1,1]
lis = [2,2,5,2,4]

len([ref.pop(ref.ind ex(x)) for x in lis if x in ref])

[bonono@gmail.com]

Re: list comprehention


Tim Chase wrote:[color=blue][color=green]
> > Python beginner here and very much enjoying it. I'm looking
> > for a pythonic way to find how many listmembers are also
> > present in a reference list. Don't count duplicates (eg. if
> > you already found a matching member in the ref list, you can't
> > use the ref member anymore).
> >
> > Example1:
> > ref=[2, 2, 4, 1, 1]
> > list=[2, 3, 4, 5, 3]
> > solution: 2
> >
> > Example2:
> > ref=[2, 2, 4, 1, 1]
> > list=[2, 2, 5, 2, 4]
> > solution: 3 (note that only the first two 2's count, the third
> > 2 in the list should not be counted)[/color]
>
> It sounds like you're looking for "set" operations: (using "ell"
> for clarity)
>[color=green][color=darkred]
> >>> from sets import Set
> >>> a = [2,2,4,1,1]
> >>> b = [2,3,4,5,3]
> >>> setA = Set(a)
> >>> setB = Set(b)
> >>> results = setA.intersecti on(setB)
> >>> results[/color][/color]
> Set([2,4])[color=green][color=darkred]
> >>> intersection = [x for x in results]
> >>> intersection[/color][/color]
> [2,4]
>
>[/color]
won't set remove duplicates which he wants to preserve ? He is not just
looking for the 'values' that is in common, but the occurence as well,
if I understand the requirement correctly.

I would just build a dict with the value as the key and occurence as
the value then loop the list and lookup.

[Peter Otten]

Re: list comprehention

Mathijs wrote:
[color=blue]
> Python beginner here and very much enjoying it. I'm looking for a
> pythonic way to find how many listmembers are also present in a reference
> list. Don't count duplicates (eg. if you already found a matching member
> in the ref list, you can't use the ref member anymore).
>
> Example1:
> ref=[2, 2, 4, 1, 1]
> list=[2, 3, 4, 5, 3]
> solution: 2
>
> Example2:
> ref=[2, 2, 4, 1, 1]
> list=[2, 2, 5, 2, 4]
> solution: 3 (note that only the first two 2's count, the third 2 in the
> list should not be counted)
>
> Any suggestions or comments?[/color]

sum(min(list.co unt(n), ref.count(n)) for n in set(ref))

Is that it?

Peter

[Peter Otten]

Re: list comprehention

Tim Chase wrote:
[color=blue]
> I'm a tad confused by the help, as it sounds like sets are
> supposed to be first-class citizens, but in ver2.3.5 that I'm
> running here (or rather "there", on a friend's box), I have to
> "import sets" which I didn't see mentioned in the reference manual.[/color]

set and frozenset are a builtins starting with Python 2.4.

http://www.python.org/2.4/highlights.html

"""
New or upgraded built-ins

built-in sets - the sets module, introduced in 2.3, has now been implemented
in C, and the set and frozenset types are available as built-in types (PEP
218)
"""

Peter

[Matt]

Re: list comprehention


Tim Chase wrote:
<snip>[color=blue]
>
> I'm a tad confused by the help, as it sounds like sets are
> supposed to be first-class citizens, but in ver2.3.5 that I'm
> running here (or rather "there", on a friend's box), I have to
> "import sets" which I didn't see mentioned in the reference manual.
>
> -one of many tims on the list
> tim = Set(["bald", "vegetarian ", "loving husband"])
>
> :)[/color]

The builtin "set" was added in 2.4, I believe (note lowercase "s"):

http://docs.python.org/whatsnew/node2.html

print "vegetarian".re place("etari"," ")
:-)

[Tim Chase]

Re: list comprehention

>> >Python beginner here and very much enjoying it. I'm looking[color=blue][color=green][color=darkred]
>> > for a pythonic way to find how many listmembers are also
>> > present in a reference list. Don't count duplicates (eg. if[/color][/color][/color]

[snipped]
[color=blue]
> won't set remove duplicates which he wants to preserve ?[/color]

My reading was that the solution shouldn't count duplicates
("Don't count duplicates"). However, once you mentioned it, and
I saw other folks' responses that looked very diff. from my own,
I re-read the OP's comments and found that I missed this key bit:

"note that only the first *two* 2's count, the third 2
in the list should not be counted"
(*emphasis* mine)

and that the desired result was a count (though a len(Set())
would return the right count if the OP wanted the true
intersection, but that's beside the point).

My error. Sorry, ladies and gentlemen :)

I'm partial to the elegance of markscala's suggestion of:

len([ref.pop(ref.ind ex(x)) for x in lis if x in ref])

though it might need to come with a caveat that it doesn't leave
"ref" in the same state is it was originally, so it should be
copied and then manipulated thusly:

r = ref[:]
len([r.pop(r.index(x )) for x in (lis if x in r])

which would then leave ref undisturbed. As tested:

import random
ref = [random.randint( 1,5) for n in range(5)]
for x in range(1,10):
lis = [random.randint( 1,5) for n in range(5)]
r = ref[:]
print repr((r,lis))
print len([r.pop(r.index(x )) for x in lis if x in r])

seems to give the results the OP describes.

-tim

[Paddy]

Re: list comprehention

Hi,
I liked the twist at the end when you state that only the first two 2's
count. It reminded me
of my maths O'level revision where you always had to read the question
thoroughly.

Here is what I came up with:
[color=blue][color=green][color=darkred]
>>> ref[/color][/color][/color]
[2, 2, 4, 1, 1][color=blue][color=green][color=darkred]
>>> lst[/color][/color][/color]
[2, 2, 5, 2, 4][color=blue][color=green][color=darkred]
>>> tmp = [ [val]*min(lst.count( val), ref.count(val)) for val in set(ref)]
>>> tmp[/color][/color][/color]
[[], [2, 2], [4]][color=blue][color=green][color=darkred]
>>> answer = [x for y in tmp for x in y]
>>> answer[/color][/color][/color]
[2, 2, 4][color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

I took a lot from Peter Ottens reply to generate tmp then flattened the
inner lists.

After a bit more thought, the intermediate calculation of tmp can be
removed with a
little loss in clarity though, to give:
[color=blue][color=green][color=darkred]
>>> answer = [ val for val in set(ref) for x in range(min(lst.c ount(val), ref.count(val)) )]
>>> answer[/color][/color][/color]
[2, 2, 4]



- Cheers, Paddy.

[Duncan Booth]

Re: list comprehention

Mathijs wrote:
[color=blue]
> Python beginner here and very much enjoying it. I'm looking for a
> pythonic way to find how many listmembers are also present in a
> reference list. Don't count duplicates (eg. if you already found a
> matching member in the ref list, you can't use the ref member
> anymore).
>
> Example1:
> ref=[2, 2, 4, 1, 1]
> list=[2, 3, 4, 5, 3]
> solution: 2
>
> Example2:
> ref=[2, 2, 4, 1, 1]
> list=[2, 2, 5, 2, 4]
> solution: 3 (note that only the first two 2's count, the third 2 in
> the list should not be counted)[/color]

Here's the way I would do it:
[color=blue][color=green][color=darkred]
>>> def occurrences(it) :[/color][/color][/color]
res = {}
for item in it:
if item in res:
res[item] += 1
else:
res[item] = 1
return res
[color=blue][color=green][color=darkred]
>>> ref=[2, 2, 4, 1, 1]
>>> lst=[2, 2, 5, 2, 4]
>>> oref = occurrences(ref )
>>> sum(min(v,oref. get(k,0)) for (k,v) in occurrences(lst ).iteritems())[/color][/color][/color]
3[color=blue][color=green][color=darkred]
>>> lst=[2, 3, 4, 5, 3]
>>> sum(min(v,oref. get(k,0)) for (k,v) in occurrences(lst ).iteritems())[/color][/color][/color]
2[color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

Or in other words, define a function to return a dictionary containing
a count of the number of occurrences of each element in the list (this
assumes that the list elements are hashable). Then you just add up the
values in the test list making sure each count is limited to no higher than
the reference count.

[Bryan Olson]

Re: list comprehention

Duncan Booth wrote:[color=blue]
> Here's the way I would do it:
>[color=green][color=darkred]
>>>>def occurrences(it) :[/color][/color]
>
> res = {}
> for item in it:
> if item in res:
> res[item] += 1
> else:
> res[item] = 1
> return res[/color]

I slightly prefer:

def occurrences(it) :
res = {}
res[item] = res.get(item, 0) + 1
return res


[...][color=blue]
> Or in other words, define a function to return a dictionary containing
> a count of the number of occurrences of each element in the list (this
> assumes that the list elements are hashable). Then you just add up the
> values in the test list making sure each count is limited to no higher than
> the reference count.[/color]

Resulting in a linear-time average case, where the posted
list-comprehension-based solutions are quadratic. The title
of the thread is unfortunate.

The generalized problem is multiset (AKA "bag") intersection:

http://en.wikipedia.org/wiki/Bag_(mathematics)


--
--Bryan

[Mathijs]

Re: list comprehention

Op 19 jan 2006 vond "markscala@gmai l.com" :
[color=blue]
> another approach:
>
> ref = [2,2,4,1,1]
> lis = [2,2,5,2,4]
>
> len([ref.pop(ref.ind ex(x)) for x in lis if x in ref])
>[/color]

This is the type of solution I was hoping to see: one-liners, with no use
of local variables. As Tim Chase already wrote, it has only one less
elegant side: it alters the original ref list.

Thanks for your suggestion.

[Mathijs]

Re: list comprehention

Op 19 jan 2006 vond Peter Otten <__peter__@web. de> :
[color=blue]
> sum(min(list.co unt(n), ref.count(n)) for n in set(ref))
>
> Is that it?[/color]

Seems like this is it! Thanks.