how can I generate integers that satisfy some restrictions?

Question

Can anyone give me a hand with techniques to generate integers that satisfy certain restrictions.

For example, say I need to generate integers x and y such that

      100 > x
and   y < x + 5

And I don't mean this particular example but some generic techniques to generate integers that satisfy certain conditions.

Thanks a lot! Manuel

Answer 1

Well, that's not that hard:

1. Pick an integer, mayhaps randomly.
2. Check your conditions
3. If one condition fails, back to step 1.

If you have multiple integers, such as x and y in your example, replace "an integer" by "integers".

This technique is also known as rejection sampling.

You could implement this with a series of chained iterators, for example. And some constraints work pretty well as generators, such as "positive integers less than 100", so you'd probably start out with one of those before filtering through all other constraints.

The only other option I'd see that applies to general restrictions would be to analyze your constraints and generate numbers without guessing but knowing how to generate them. This is trivial for constraints such as “0 < x < 100” but beyond that it borders closely on implementing a computer algebra system. Also keep in mind that you have to simultaneously satisfy every constraint ... what takes rejection sampling long will make this approach a nightmare to implement.

Answer 2

If it's a scripting language you could pass the Minimal and Maximal x and y values, and an array of tests to a function, and then use rand to generate initial values within your range.

Following that you simply iterate through the array using some variant of 'eval' to test your values for fitness.

This would be a general purpose solution to your problem.

Answer 3

If all your constraints can be written as a set of linear equations, you could use linear programming to find a solution to maximize 'c1*x + c2*y'. For c1 and c2 you can draw random values. Especially if you have lots of constraints and variables that might be faster than just trying random values for x and y.

Answer 4

You want to look at constraint-based languages. For example, CLIP would allow you to specify your constraints and then will return the set of intervals which satisfy all your constraints.

Answer 5

This kind of problem is what Prolog was designed for. You could also look into newer languages like Mozart for a more modern take. The declarative programming model is to announce constraints for your outputs, and then get answers that meet the specified constraints.

To quote the wikipedia page for Prolog:

Prolog has its roots in formal logic, and unlike many other programming languages, Prolog is declarative: The program logic is expressed in terms of relations, represented as facts and rules. Execution is triggered by running queries over these relations.

Answer 6

If you are feeling LINQ-y then you can start with a List of all possible x,y pairs and then apply a where clause for each condition. Whatever's left you can pick items out of randomly.

Dim everything As List(Of Point) = generate_pairs()
Dim rest As List(Of Point) = everything.Where(Function(pp) pp.X > 100).ToList
rest = rest.Where(Function(pp) pp.Y < pp.X + 5).ToList
Dim rnd As New Random()
Dim r As Integer = rnd.Next(rest.Count)
Dim p As Point = rest.Skip(r).Take(1).SingleOrDefault
System.Console.WriteLine("x: " & p.X & " y: " & p.Y)