Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Python (http://www.velocityreviews.com/forums/f43-python.html)
-   -   reduce expression to test sublist (http://www.velocityreviews.com/forums/t956172-reduce-expression-to-test-sublist.html)

 Asim 01-05-2013 06:25 PM

reduce expression to test sublist

Hi All

The following reduce expression checks if every element of list lst1 is present in list lst2. It works as expected for integer lists but for lists of strings, it always returns False.

reduce( lambda x,y: (x in lst2) and (y in lst2), lst1)

Moreover, for the lists of strings the following for-loop gives correct results when the above reduce expression doesn't.

isSublist = True
for i in lst1:
isSublist = isSublist and (i in lst2)
if not isSublist:
isSublist = False
break

Can someone help me understand why?

Asim

 Dave Angel 01-05-2013 06:58 PM

Re: reduce expression to test sublist

On 01/05/2013 01:25 PM, Asim wrote:
> Hi All
>
> The following reduce expression checks if every element of list lst1 is present in list lst2. It works as expected for integer lists but for lists of strings, it always returns False.
>
> reduce( lambda x,y: (x in lst2) and (y in lst2), lst1)
>
> Moreover, for the lists of strings the following for-loop gives correct results when the above reduce expression doesn't.
>
> isSublist = True
> for i in lst1:
> isSublist = isSublist and (i in lst2)
> if not isSublist:
> isSublist = False
> break
>
>
> Can someone help me understand why?
>
> Asim

reduce only makes sense if the value you're reducing to is of the same
type as the elements of the list you're iterating over. Since your
lambda expression returns a boolean (True or False), it'll seem to work
on some lists of ints. That's just a coincidence since the bools are
compatible with ints, and maybe you've got a 0 or 1 in the list. But if
your list has only strings, then True will never be that list.

If you're trying to make a faster loop, then I suggest you look into set
differences. Turn both lists into sets, and subtract them. Something
like (untested):

result = not bool( set(lst1) - set(lst2) )

--

DaveA

 chaouche yacine 01-05-2013 07:59 PM

Re: reduce expression to test sublist

Because reduce doesn't do what you want. You'd want "all".

L1 = [1,2,3]
L2 = ["A1","B2","C3",1,2,3]
print all((x in L2 for x in L1)) # prints True
L3 = ["A1","B2","C3"]
print all((x in L2 for x in L3)) # prints True

----- Original Message -----
From: Asim <asim.r.p@gmail.com>
To: python-list@python.org
Cc:
Sent: Saturday, January 5, 2013 7:25 PM
Subject: reduce expression to test sublist

Hi All

The following reduce expression checks if every element of list lst1 is present in list lst2.* It works as expected for integer lists but for lists of strings, it always returns False.

* reduce( lambda x,y: (x inlst2) and (y in lst2), lst1)

Moreover, for the lists of strings the following for-loop gives correct results when the above reduce expression doesn't.

* isSublist = True
* for i in lst1:
* * * isSublist = isSublist and (i in lst2)
* * * if not isSublist:
* * * * isSublist = False
* * * * break

Can someone help me understand why?

Asim
--
http://mail.python.org/mailman/listinfo/python-list

 Jussi Piitulainen 01-05-2013 08:41 PM

Re: reduce expression to test sublist

Asim writes:

> Hi All
>
> The following reduce expression checks if every element of list lst1
> is present in list lst2. It works as expected for integer lists but
> for lists of strings, it always returns False.
>
> reduce( lambda x,y: (x in lst2) and (y in lst2), lst1)

Possibly this:

>>> True in [3, 1, 4]

True
>>> True in ["3", "1", "4"]

False

Since reduce(f, [a, b, c]) == f(f(a,b),c), your x will be True or
False except in the innermost call where it is the first element of
the list being reduced.

It doesn't really work with integers either. Only in certain special
cases: very short lst1, or True in lst2.

> Moreover, for the lists of strings the following for-loop gives
> correct results when the above reduce expression doesn't.
>
> isSublist = True
> for i in lst1:
> isSublist = isSublist and (i in lst2)
> if not isSublist:
> isSublist = False
> break
>
> Can someone help me understand why?

Consider reduce(lambda x, y: x and (y in whatever), ys, True).

Maybe also consider all(y in whatever for y in ys).

 Terry Reedy 01-05-2013 09:55 PM

Re: reduce expression to test sublist

On 1/5/2013 1:58 PM, Dave Angel wrote:

> If you're trying to make a faster loop, then I suggest you look into set
> differences. Turn both lists into sets, and subtract them. Something
> like (untested):
>
> result = not bool( set(lst1) - set(lst2) )

This does not return False as soon as an item in set1 is found that is
not in set2.

set(lst1) < set(lst2)

will, and directly return False/True. The OP is trying to compute the
lst1 < lst2, where lst1 and lst2 are interpreted as sets, rather than as
sequences with the lexicographic ordering default.

--
Terry Jan Reedy

 Terry Reedy 01-05-2013 09:55 PM

Re: reduce expression to test sublist

On 1/5/2013 1:25 PM, Asim wrote:
> Hi All
>
> The following reduce expression checks if every element of list lst1
> is present in list lst2. It works as expected for integer lists but
> for lists of strings, it always returns False.
>
> reduce( lambda x,y: (x in lst2) and (y in lst2), lst1)

reduce(lambda x, y: x and (y in lst2), lst1, True)

would work, but as other have said, you want to stops at the first
False, which all() does, and if lst2 is a list of hashable items, x in
set for O(1) rather than O(n) check.

> Moreover, for the lists of strings the following for-loop gives
> correct results when the above reduce expression doesn't.

You should include data for testing.

>
> isSublist = True
> for i in lst1:
> isSublist = isSublist and (i in> lst2)

If isSublist remains True, there is no need to rebind it

> if not isSublist:
> isSublist = False

Setting isSublist False when it is False is redundant.

> break

Taking into account the comments:

def is_sublist(a, b):
b = set(b) # optional, depending on contents
for item in a:
if item not in b:
return False
else: # not needed because return above
return True

The code for all() is similar, except that all takes an iterable, so
that the testing is done as part of the input iterable.

def all(iterable):
it = iter(iterable):
for item in it:
if not it:
return False:
else:
return True

def issublist(a, b):
b = set(b)
return all(item in b for item in a)

--
Terry Jan Reedy

 Dave Angel 01-05-2013 10:05 PM

Re: reduce expression to test sublist

On 01/05/2013 04:55 PM, Terry Reedy wrote:
> On 1/5/2013 1:58 PM, Dave Angel wrote:
>
>> If you're trying to make a faster loop, then I suggest you look into set
>> differences. Turn both lists into sets, and subtract them. Something
>> like (untested):
>>
>> result = not bool( set(lst1) - set(lst2) )

>
> This does not return False as soon as an item in set1 is found that is
> not in set2.
>
> set(lst1) < set(lst2)
>
> will, and directly return False/True. The OP is trying to compute the
> lst1 < lst2, where lst1 and lst2 are interpreted as sets, rather than
> as sequences with the lexicographic ordering default.
>

Thanks. I wasn't aware that sets supported ordered comparison that way,
though it makes perfect sense now that you point it out.

--

DaveA

 All times are GMT. The time now is 10:37 PM.