Boolean function on variable-length lists

Discussion in 'Python' started by Libra, Sep 12, 2012.

  1. Libra

    Libra Guest

    Hello,

    I need to implement a function that returns 1 only if all the values in a list satisfy given constraints (at least one constraint for each element in the list), and zero otherwise.

    For example, I may have a list L = [1, 2, 3, 4] and the following constraints:
    L[0] >= 1
    L[1] <= 3
    L[2] == 2
    L[3] >= 3

    In this case, the function returns 0 because the third constraint is not satisfied.

    With fixed-length lists, I can sometimes use a very naive approach and hard-code the constraints combined with AND. Nonetheless, the problems are:
    1) even with fixed-length lists, the hard-code approach requires a lot of effort (especially with long lists) and is prone to error;
    2) the constraints may change, so with a hard-code approach the effort grows exponentially;
    3) I need to work on variable-length lists (generally, lists of numbers).

    I can't figure out anything useful.
    Could you please suggest me a suitable ways?

    Thanks
    Libra
     
    Libra, Sep 12, 2012
    #1
    1. Advertising

  2. Libra writes:

    > Hello,
    >
    > I need to implement a function that returns 1 only if all the values
    > in a list satisfy given constraints (at least one constraint for
    > each element in the list), and zero otherwise.
    >
    > For example, I may have a list L = [1, 2, 3, 4] and the following
    > constraints:
    > L[0] >= 1
    > L[1] <= 3
    > L[2] == 2
    > L[3] >= 3
    >
    > In this case, the function returns 0 because the third constraint is
    > not satisfied.


    So you would associate each constraint with an index. You could
    maintain a list of constraints and apply it to the values as follows:

    >>> cs = [ lambda x : x >= 1, lambda x : x <= 3, lambda x : x == 2,

    .... lambda x : x >= 3 ]
    >>> { f(x) for f, x in zip(cs, [1,2,3,4]) }

    {False, True}
    >>> { f(x) for f, x in zip(cs, [1,2,2,4]) }

    {True}
    >>>


    Then map the return value to 0 if it contains a False, else to 1.
     
    Jussi Piitulainen, Sep 12, 2012
    #2
    1. Advertising

  3. On Wed, 12 Sep 2012 05:48:09 -0700, Libra wrote:

    > Hello,
    >
    > I need to implement a function that returns 1 only if all the values in
    > a list satisfy given constraints (at least one constraint for each
    > element in the list), and zero otherwise.


    What are the restrictions on the constraints themselves?

    Could they be arbitrarily complicated?

    "Item 2 must be an even number divisible by 17 and 39 with at least eight
    digits but no greater than four million, unless today is Tuesday, in
    which case it must be equal to six exactly."

    I'm going to assume you have a list of functions which take a single
    argument and then return True if it meets the constraint and False if it
    doesn't. Using your examples later:

    > For example, I may have a list L = [1, 2, 3, 4] and the following
    > constraints:
    > L[0] >= 1
    > L[1] <= 3
    > L[2] == 2
    > L[3] >= 3


    constraints = [
    lambda x: x >= 1,
    lambda x: x <= 3,
    lambda x: x == 2,
    lambda x: x >= 3,
    ]

    ought to handle any reasonable constraint.

    Then use the zip() function to match up constraints with values, and
    all() to make sure they are all met.

    Since this sounds like homework, I won't give you the exact solution. If
    you still can't solve it, come back with your attempt and we'll give you
    a bit more help.


    --
    Steven
     
    Steven D'Aprano, Sep 12, 2012
    #3
  4. Libra

    Tim Chase Guest

    On 09/12/12 08:02, Jussi Piitulainen wrote:
    > Libra writes:
    >> For example, I may have a list L = [1, 2, 3, 4] and the following
    >> constraints:
    >> L[0] >= 1
    >> L[1] <= 3
    >> L[2] == 2
    >> L[3] >= 3

    >
    > So you would associate each constraint with an index. You could
    > maintain a list of constraints and apply it to the values as follows:
    >
    >>>> cs = [ lambda x : x >= 1, lambda x : x <= 3, lambda x : x == 2,

    > ... lambda x : x >= 3 ]


    This can even be decoupled a bit more for dynamic creation:

    >>> lst = [1,2,3,4]
    >>> import operator as o
    >>> conditions = [

    .... (o.ge, 1),
    .... (o.le, 3),
    .... (o.eq, 2),
    .... (o.ge, 3),
    .... ]
    >>> [op(v, constraint) for ((op, constraint), v) in zip(conditions,

    lst)]
    [True, True, False, True]
    >>> all(compare(value, constraint) for ((compare, constraint),

    value) in zip(conditions, lst))
    False

    Note that you'd also want to check len(conditions)==len(lst) for
    obvious reasons. :)

    -tkc
     
    Tim Chase, Sep 12, 2012
    #4
  5. Libra

    Libra Guest

    On Wednesday, September 12, 2012 3:02:44 PM UTC+2, Jussi Piitulainen wrote:

    > So you would associate each constraint with an index. You could
    > maintain a list of constraints and apply it to the values as follows:


    Yes, even though there could be more constraints for each value in the list (at least 1 constraint for each value)
    >
    > >>> cs = [ lambda x : x >= 1, lambda x : x <= 3, lambda x : x == 2,

    >
    > ... lambda x : x >= 3 ]
    >
    > >>> { f(x) for f, x in zip(cs, [1,2,3,4]) }


    Just to understand, with f(x) you are defining a function f with argument x, right? I didn't know it was possible to define functions in this way. Is this a case of anonymous function?

    > {False, True}


    Actually, I don't understand the output. Why it is both False and True?

    > >>> { f(x) for f, x in zip(cs, [1,2,2,4]) }

    > {True}


    Ok.

    Thank you very much
     
    Libra, Sep 12, 2012
    #5
  6. Libra

    Libra Guest

    On Wednesday, September 12, 2012 3:11:42 PM UTC+2, Steven D'Aprano wrote:
    > On Wed, 12 Sep 2012 05:48:09 -0700, Libra wrote:


    > > I need to implement a function that returns 1 only if all the values in
    > > a list satisfy given constraints (at least one constraint for each
    > > element in the list), and zero otherwise.

    >
    > What are the restrictions on the constraints themselves?
    > Could they be arbitrarily complicated?
    > "Item 2 must be an even number divisible by 17 and 39 with at least eight
    > digits but no greater than four million, unless today is Tuesday, in
    > which case it must be equal to six exactly."


    Generally the constraints are quite simple, like the one in my example. But I can also have 2 or more constraints for each value:
    L[0] >= 1
    L[0] <= 5

    To complicate a little, what about constraints like:
    L[0] + L[2] >= 3

    Thanks

    > --
    >
    > Steven
     
    Libra, Sep 12, 2012
    #6
  7. Libra

    Libra Guest

    On Wednesday, September 12, 2012 3:19:28 PM UTC+2, Libra wrote:

    > > {False, True}

    > Actually, I don't understand the output. Why it is both False and True?


    Ok, I have understood now, I didn't noticed it was a set and not a list.
    Regards
     
    Libra, Sep 12, 2012
    #7
  8. Libra writes:
    > On Wednesday, September 12, 2012 3:02:44 PM UTC+2, Jussi Piitulainen wrote:
    >
    > > So you would associate each constraint with an index. You could
    > > maintain a list of constraints and apply it to the values as
    > > follows:

    >
    > Yes, even though there could be more constraints for each value in
    > the list (at least 1 constraint for each value)


    Either you write more complex constraint functions, or you use more
    complex data structures to hold them.

    > > >>> cs = [ lambda x : x >= 1, lambda x : x <= 3, lambda x : x == 2,

    > >
    > > ... lambda x : x >= 3 ]
    > >
    > > >>> { f(x) for f, x in zip(cs, [1,2,3,4]) }

    >
    > Just to understand, with f(x) you are defining a function f with
    > argument x, right? I didn't know it was possible to define functions
    > in this way. Is this a case of anonymous function?


    The value of each lambda expression is a function. f(x) is a function
    call, evaluated for each pair (f, x) from the list of pairs that the
    zip returns.

    { ... for ... in ... } creates a set of the values, no duplicates.
    [ ... for ... in ... ] creates a list of the values.

    > > {False, True}

    >
    > Actually, I don't understand the output. Why it is both False and
    > True?


    It's a set containing False and True. The False comes from the f(x)
    where f = lambda x : x == 2, and x is 3. There is only one True
    because I requested a set of the values.
     
    Jussi Piitulainen, Sep 12, 2012
    #8
  9. On 12/09/2012 14:51, Ken Seehart wrote:

    [snip]

    Could you please not top post on this list, thanks.

    --
    Cheers.

    Mark Lawrence.
     
    Mark Lawrence, Sep 12, 2012
    #9
  10. Libra

    MRAB Guest

    On 12/09/2012 14:51, Ken Seehart wrote:
    > Putting a few of peoples ideas together...
    >
    >
    > gt = lambda x: lambda y: x>y
    > eq = lambda x: lambda y: x==y
    >
    > def constrain(c,d):
    > return all({f(x) for f, x in zip(c, d)})
    >

    If you're going to use 'all', why use a set?

    return all(f(x) for f, x in zip(c, d))

    This will stop as soon as a constraint fails.

    > constraints = [gt(2), eq(1)]
    > data0 = [1,1]
    > data1 = [3,1]
    >
    > print constrain(constraints, data0)
    > print constrain(constraints, data1)
    >
     
    MRAB, Sep 12, 2012
    #10
    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. =?Utf-8?B?Sm9obl9I?=
    Replies:
    1
    Views:
    2,792
    =?Utf-8?B?Sm9obl9I?=
    Jan 19, 2006
  2. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    441
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  3. Jonathan Burd

    Help with Variable-Length Argument Lists

    Jonathan Burd, Dec 14, 2004, in forum: C Programming
    Replies:
    5
    Views:
    381
    Keith Thompson
    Dec 15, 2004
  4. J Leonard
    Replies:
    4
    Views:
    12,885
    Mark Space
    Jan 19, 2008
  5. Metre Meter
    Replies:
    7
    Views:
    458
    Metre Meter
    Aug 6, 2010
Loading...

Share This Page