reduce expression to test sublist

[Asim]

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]

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

 

[chaouche yacine]

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 <[email protected]>
To: (e-mail address removed)
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

 

[Jussi Piitulainen]

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]

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

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)

 

[Dave Angel]

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.