views:

144

answers:

6

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

+6  A: 

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.

Joey
this technique can be very time consuming if the restrictions are non-trivial. You might be shooting enormous amounts of data of which 99.9999% is rejected.
Toad
Of course; though for many purposes it works surprisingly well. The other option would be to transform your conditions into generating rules, which essentially enumerate possible combinations. But that's highly non-trivial and hard to get right. As far as general approaches go, there are not many better options.
Joey
The designers of Prolog would beg to disagree.
Justin Smith
Well, ok, backtracking is a way to resolve this, but not necessarily better than starting out with random numbers. You have to take similar care with the ordering of your conditions that they catch most rejects pretty early.
Joey
I'm concerned with this algorithm as it may take too long for some sets of constraints, and the problem is I don't know the constraints a priori. I'll try using this and meanwhile research about this idea of transforming conditions into generating rules. Any help in finding resources is appreciated! Thanks!
Manuel
+1  A: 

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.

yosser
I like your answer, but I'm not sure which programming language I'll be using and I'm afraid it might be a little bit slow.
Manuel
If the language is compiled, you could always embed a LUA interpreter into the executable and pass the values to be evaluated to it. This would be both fast and hugely flexible.
yosser
this can be done without scripting
Justin Smith
+4  A: 

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.

Maurits Rijk
Thanks for this! As I get the constraints dynamically, I'll try to think if I can easily determine if they are all linear to apply simplex or something of the sort. Great idea, really!
Manuel
+1  A: 

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.

Alex Feinman
+1  A: 

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.
Justin Smith
A: 

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)
tooleb