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

[Paddy]

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:

ref [2, 2, 4, 1, 1] lst [2, 2, 5, 2, 4] tmp = [ [val]*min(lst.count( val), ref.count(val)) for val in set(ref)]
tmp [[], [2, 2], [4]] answer = [x for y in tmp for x in y]
answer [2, 2, 4]
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:
answer = [ val for val in set(ref) for x in range(min(lst.c ount(val), ref.count(val)) )]
answer

[2, 2, 4]

- Cheers, Paddy.

[Duncan Booth]

Mathijs wrote:

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)

Here's the way I would do it:

def occurrences(it) : res = {}
for item in it:
if item in res:
res[item] += 1
else:
res[item] = 1
return res
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()) 3 lst=[2, 3, 4, 5, 3]
sum(min(v,oref. get(k,0)) for (k,v) in occurrences(lst ).iteritems()) 2

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]

Duncan Booth wrote:

Here's the way I would do it:

def occurrences(it) :

res = {}
for item in it:
if item in res:
res[item] += 1
else:
res[item] = 1
return res

I slightly prefer:

def occurrences(it) :
res = {}
res[item] = res.get(item, 0) + 1
return res
[...] 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.

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]

Op 19 jan 2006 vond "ma*******@gmai l.com" :

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

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]

Op 19 jan 2006 vond Peter Otten <__*******@web. de> :

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

Is that it?

Seems like this is it! Thanks.

[Mathijs]

Op 19 jan 2006 vond "Paddy" <pa*******@nets cape.net>:

answer = [ val for val in set(ref) for x in
range(min(lst.c ount(val), ref.count(val)) )] answer

[2, 2, 4]

I don't think it's correct. Your algoritm with the ref and lst below gives
3 as answer. The answer should have been 2 (1,3).

ref=[3, 3, 1, 1, 3]
lst=[5, 1, 4, 5, 3]

[Mathijs]

Op 20 jan 2006 vond Duncan Booth <du**********@i nvalid.invalid> :

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.

Thanks. Though I don't know much about python (yet), this is more or less
the way I'de do it the language I'm more comfortable with (object pascal),
and I wouldn't label this as a pythonic solution. I could be wrong,
though:)

[Duncan Booth]

Mathijs wrote:

Op 20 jan 2006 vond Duncan Booth <du**********@i nvalid.invalid> :

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.

Thanks. Though I don't know much about python (yet), this is more or
less the way I'de do it the language I'm more comfortable with (object
pascal), and I wouldn't label this as a pythonic solution. I could be
wrong, though:)

I'm curious what you think isn't pythonic about this solution?

[Peter Otten]

Mathijs wrote:

Op 20 jan 2006 vond Duncan Booth <du**********@i nvalid.invalid> :

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.

Thanks. Though I don't know much about python (yet), this is more or less
the way I'de do it the language I'm more comfortable with (object pascal),
and I wouldn't label this as a pythonic solution. I could be wrong,
though:)

You *are* wrong. Also, as the lists grow, Duncan's approach scales *much*
better than, e. g., mine.

If picking a better algorithm were unpythonic there would not be much value
in striving for pythonic solutions.

Peter

[Steven D'Aprano]

On Mon, 23 Jan 2006 17:41:55 +0000, Mathijs wrote:

Op 19 jan 2006 vond "ma*******@gmai l.com" :

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

This is the type of solution I was hoping to see: one-liners, with no use
of local variables.

Because you like unreadable, incomprehensibl e, unmaintainable code?

*wink*

--
Steven.