reduce expression to test sublist

Discussion in 'Python' started by Asim, Jan 5, 2013.

  1. Asim

    Asim Guest

    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
     
    Asim, Jan 5, 2013
    #1
    1. Advertising

  2. Asim

    Dave Angel Guest

    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
     
    Dave Angel, Jan 5, 2013
    #2
    1. Advertising

  3. 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 <>
    To:
    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
     
    chaouche yacine, Jan 5, 2013
    #3
  4. 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).
     
    Jussi Piitulainen, Jan 5, 2013
    #4
  5. Asim

    Terry Reedy Guest

    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, Jan 5, 2013
    #5
  6. Asim

    Terry Reedy Guest

    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
     
    Terry Reedy, Jan 5, 2013
    #6
  7. Asim

    Dave Angel Guest

    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
     
    Dave Angel, Jan 5, 2013
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Paul Whipp
    Replies:
    1
    Views:
    379
    Alex Martelli
    Nov 7, 2003
  2. Bernard A.

    inner sublist positions ?

    Bernard A., Apr 20, 2005, in forum: Python
    Replies:
    2
    Views:
    356
    tiissa
    Apr 21, 2005
  3. giampiero mu

    finding sublist

    giampiero mu, Aug 2, 2005, in forum: Python
    Replies:
    5
    Views:
    393
    Johan Lindberg
    Aug 3, 2005
  4. Helmut Jarausch

    append to a sublist - please help

    Helmut Jarausch, Apr 6, 2008, in forum: Python
    Replies:
    2
    Views:
    359
  5. Matthias Gallé

    find sublist inside list

    Matthias Gallé, May 4, 2009, in forum: Python
    Replies:
    13
    Views:
    1,241
    mzdude
    May 5, 2009
Loading...

Share This Page