Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #36197 > unrolled thread

reduce expression to test sublist

Back to article view | Back to comp.lang.python

Contents

  reduce expression to test sublist Asim <asim.r.p@gmail.com> - 2013-01-05 10:25 -0800
    Re: reduce expression to test sublist Dave Angel <d@davea.name> - 2013-01-05 13:58 -0500
    Re: reduce expression to test sublist chaouche yacine <yacinechaouche@yahoo.com> - 2013-01-05 11:59 -0800
    Re: reduce expression to test sublist Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-01-05 22:41 +0200
    Re: reduce expression to test sublist Terry Reedy <tjreedy@udel.edu> - 2013-01-05 16:55 -0500
    Re: reduce expression to test sublist Terry Reedy <tjreedy@udel.edu> - 2013-01-05 16:55 -0500
    Re: reduce expression to test sublist Dave Angel <d@davea.name> - 2013-01-05 17:05 -0500

#36197 — 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

[toc] | [next] | [standalone]

#36199

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

[toc] | [prev] | [next] | [standalone]

#36204

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 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
-- 
http://mail.python.org/mailman/listinfo/python-list

[toc] | [prev] | [next] | [standalone]

#36208

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

[toc] | [prev] | [next] | [standalone]

#36212

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

[toc] | [prev] | [next] | [standalone]

#36213

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

[toc] | [prev] | [next] | [standalone]

#36215

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web