Boolean function on variable-length lists

L

Libra

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
 
J

Jussi Piitulainen

Libra said:
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.
 
S

Steven D'Aprano

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

Tim Chase

Libra said:
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]value) in zip(conditions, lst))
False

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

-tkc
 
L

Libra

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
 
L

Libra

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
 
J

Jussi Piitulainen

Libra said:
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.
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.
 
M

Mark Lawrence

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

[snip]

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

MRAB

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)
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,734
Messages
2,569,441
Members
44,832
Latest member
GlennSmall

Latest Threads

Top