All valid combinations of points, in the most (speed) effective way

Question

I know there are quite some questions out there on generating combinations of elements, but I think this one has a certain twist to be worth a new question:

For a pet proejct of mine I've to pre-compute a lot of state to improve the runtime behavior of the application later. One of the steps I struggle with is this:

Given N tuples of two integers (lets call them points from here on, although they aren't in my use case. They roughly are X/Y related, though) I need to compute all valid combinations for a given rule.

The rule might be something like

• "Every point included excludes every other point with the same X coordinate"
• "Every point included excludes every other point with an odd X coordinate"

I hope and expect that this fact leads to an improvement in the selection process, but my math skills are just being resurrected as I type and I'm unable to come up with an elegant algorithm.

• The set of points (N) starts small, but outgrows 64 soon (for the "use long as bitmask" solutions)
• I'm doing this in C#, but solutions in any language should be fine if it explains the underlying idea

Thanks.

---

Update in response to Vlad's answer:

Maybe my idea to generalize the question was a bad one. My rules above were invented on the fly and just placeholders. One realistic rule would look like this:

• "Every point included excludes every other point in the triagle above the chosen point"

By that rule and by choosing (2,1) I'd exclude

• (2,2) - directly above
• (1,3) (2,3) (3,3) - next line
• and so on

So the rules are fixed, not general. They are unfortunately more complex than the X/Y samples I initially gave.

Answer 1

For some special rule types your task seems to be simple. For example, for your example rule #1 you need to choose a subset of all possible values of X, and than for each value from the subset assign an arbitrary Y.

For generic rules I doubt that it's possible to build an efficient algorithm without any AI.

Answer 2

My understanding of the problem is: Given a method bool property( Point x ) const, find all points the set for which property() is true. Is that reasonable?

The brute-force approach is to run all the points through property(), and store the ones which return true. The time complexity of this would be O( N ) where (a) N is the total number of points, and (b) the property() method is O( 1 ). I guess you are looking for improvements from O( N ). Is that right?

For certain kind of properties, it is possible to improve from O( N ) provided suitable data structure is used to store the points and suitable pre-computation (e.g. sorting) is done. However, this may not be true for any arbitrary property.

Answer 3

How about "the x coordinate of every point included is the exact sum of some subset of the y coordinates of the other included points". If you can come up with a fast algorithm for that simply-stated constraint problem then you will become very famous indeed.

My point being that the problem as stated is so vague as to admit NP-complete or NP-hard problems. Constraint optimization problems are incredibly hard; if you cannot put extremely tight bounds on the problem then it very rapidly becomes not analyzable by machines in polynomial time.