Velocity Reviews > Boolean function on variable-length lists

Boolean function on variable-length lists

Libra
Guest
Posts: n/a

 09-12-2012
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

Jussi Piitulainen
Guest
Posts: n/a

 09-12-2012
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.

Steven D'Aprano
Guest
Posts: n/a

 09-12-2012
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

> 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

Tim Chase
Guest
Posts: n/a

 09-12-2012
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

Libra
Guest
Posts: n/a

 09-12-2012
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
Guest
Posts: n/a

 09-12-2012
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
Guest
Posts: n/a

 09-12-2012
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

Jussi Piitulainen
Guest
Posts: n/a

 09-12-2012
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.

Mark Lawrence
Guest
Posts: n/a

 09-12-2012
On 12/09/2012 14:51, Ken Seehart wrote:

[snip]

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

--
Cheers.

Mark Lawrence.

MRAB
Guest
Posts: n/a

 09-12-2012
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)
>