Random Numbers with a Twist
Author 
Message 
Shawn Coppoc #1 / 25

Random Numbers with a Twist
I can yank random numbers from ranges etc. all day. But now, I need a little more and I am tripping to solve this one. #Problem: Lets say I need to generate 60 random pairs of numbers ($x,$y) ... where $x is from a range of 1..1200 and $y is from a range of 1..800. Consider these pairs as a random point or coordinate on a grid of 1200x800. In addition to this, each pair must be unique, in that 1. no pair can be the same 2. no pair can be within 30 of another #Example: Pair 1: 50,100 Pair 2: 32,135 Pair 3: 31,130 etc.. Assuming that the pair numbers are checked before being added to a final list... Pair 2 is ok because only one number is within 30 of Pair 1. But, Pair 3 is NOT ok, because both numbers are within 30 of another pair (Pair 2). I don't want the pairs/coordinates to be perfectly spaced by 30. There's no need because at 1200x800 there are 960k available points... and if no two are within 30 of another, there are still 320k possibilities. Any assistance here would be greatly appreciated! Shawn

Sat, 05 Jul 2003 02:53:08 GMT 


Duncan Murdo #2 / 25

Random Numbers with a Twist
On Mon, 15 Jan 2001 10:53:08 0800, "Shawn Coppock"
Quote: >I can yank random numbers from ranges etc. all day. But now, I need a little >more and I am tripping to solve this one. >#Problem: >Lets say I need to generate 60 random pairs of numbers ($x,$y) ... where $x >is from a range of 1..1200 and $y is from a range of 1..800. Consider these >pairs as a random point or coordinate on a grid of 1200x800. >In addition to this, each pair must be unique, in that >1. no pair can be the same >2. no pair can be within 30 of another ... >I don't want the pairs/coordinates to be perfectly spaced by 30. There's no >need because at 1200x800 there are 960k available points... and if no two >are within 30 of another, there are still 320k possibilities.
You might want to narrow down your requirements a little more, and then ask this question in sci.stat.math. Explain how many points you want in your sample. Explain why choosing one point completely at random, then as many as desired from a grid with a spacing of 30 would not be acceptable. More generally, explain what you hope to do with the numbers, because there are lots of "random" distributions with different properties; maybe some are okay and some aren't. If you aren't very picky about the exact distributional properties, then one way to get a random looking sample is to maintain an array of legal positions, and a count of how many there are. Generate a number from 1 to the count; put your sampled pair at the corresponding position, and mark all the neighbours as illegal, reducing the count. Keep going until your sample is big enough, or there are no more legal positions. This *does not* generate a sample that's drawn uniformly from all possible samples, but for most purposes it would be good enough. Followups to sci.stat.math. Duncan Murdoch

Sat, 05 Jul 2003 00:40:54 GMT 


Anno Sieg #3 / 25

Random Numbers with a Twist
Quote: >I can yank random numbers from ranges etc. all day. But now, I need a little >more and I am tripping to solve this one. >#Problem: >Lets say I need to generate 60 random pairs of numbers ($x,$y) ... where $x >is from a range of 1..1200 and $y is from a range of 1..800. Consider these >pairs as a random point or coordinate on a grid of 1200x800. >In addition to this, each pair must be unique, in that >1. no pair can be the same >2. no pair can be within 30 of another
The second condition implies the first one, so you'll just have to worry about condition 2. Quote: >#Example: >Pair 1: 50,100 >Pair 2: 32,135 >Pair 3: 31,130 >etc.. >Assuming that the pair numbers are checked before being added to a final >list... >Pair 2 is ok because only one number is within 30 of Pair 1. But, Pair 3 is >NOT ok, because both numbers are within 30 of another pair (Pair 2). >I don't want the pairs/coordinates to be perfectly spaced by 30. There's no >need because at 1200x800 there are 960k available points... and if no two >are within 30 of another, there are still 320k possibilities.
Well, you could conceptually tile your rectangle with 30x30 squares, and select 60 of those at random. Then, in a second step, select a random point in each preselected square. I don't know what statistical properties to expect from a distribution generated this way. Nor am I sure what to do with the partial squares that turn up along the edges. You will probably have to select a "square" with a probability proportional to its area. Anno

Sat, 05 Jul 2003 00:47:15 GMT 


Joe Schaefe #4 / 25

Random Numbers with a Twist
Quote:
> #Problem: > Lets say I need to generate 60 random pairs of numbers ($x,$y) ... > where $x is from a range of 1..1200 and $y is from a range of 1..800. > Consider these pairs as a random point or coordinate on a grid of > 1200x800. > In addition to this, each pair must be unique, in that > 1. no pair can be the same
Ignoring (2), why not try to solve this problem first? Explicitly, can you write a perl sub that grabs 60 unique, arbitrarily chosen points from your grid? Quote: > 2. no pair can be within 30 of another
To solve (2), a minor perturbation of the solution to (1) should work (it's the same class of problem since 60 15x15squares is only about 1% of the total area of your grid). Quote: > I don't want the pairs/coordinates to be perfectly spaced by 30. There's > no need because at 1200x800 there are 960k available points... and if no > two are within 30 of another, there are still 320k possibilities.
Not sure your figures make much sense if you are talking about 60 points, there are considerably more possibilities than that (think binomial coefficients); if you're only talking about one point, spacing between points is not an issue. HTH  Joe Schaefer

Sat, 05 Jul 2003 01:14:22 GMT 


Joe Schaefe #5 / 25

Random Numbers with a Twist
Quote:
> > 2. no pair can be within 30 of another > To solve (2), a minor perturbation of the solution to (1) should work > (it's the same class of problem since 60 15x15squares is only about
^^^^^ Looks like my math's pretty fuzzy, too. You need 60 30x30squares, which amounts to about 5% of the total area. Same difference :)  Joe Schaefer

Sat, 05 Jul 2003 01:27:08 GMT 


Craig Ber #6 / 25

Random Numbers with a Twist
: Lets say I need to generate 60 random pairs of numbers ($x,$y) ... where $x : is from a range of 1..1200 and $y is from a range of 1..800. Consider these : pairs as a random point or coordinate on a grid of 1200x800. : : In addition to this, each pair must be unique, in that : 1. no pair can be the same : 2. no pair can be within 30 of another The following doesn't do much error checking, and will loop infinitely if presented with an impossible task (80 point on a 10 by 10 grid, separated by 3, for example). #!/usr/bin/perl w # scatter  generate separated pairs of cartesian coords (for clpm) # Useage: scatter <width> <height> <count> <minsep> # Where... # width and height are the dimensions of the 'field' # count is the number of points to be generated # minsetp is the minimum horizontal and vertical separation between points # Output: List of coordinate pairs on stdout # Craig Berry (20010115) use strict;
POINT:
my $p1 = [ int rand $width, int rand $height ];
next POINT if abs($p1>[0]  $p0>[0]) <= $minsep && abs($p1>[1]  $p0>[1]) <= $minsep; }
Quote: }
  Craig Berry  http://www.cinenet.net/~cberry/ * "The hills are burning, and the wind is raging; and the clock  strikes midnight in the Garden of Allah."  Don Henley

Sat, 05 Jul 2003 02:40:52 GMT 


David Hiskiyah #7 / 25

Random Numbers with a Twist
This is an interesting problem, though quite simple. I will avoid going into Perl code, because mine will for sure not be optimal  let's focus on the algorithm. 1. Represent your grid as an array of 1200x800. Mark all points in the array as '1' (1=allowed to use, 0=not good). 2. From the cells marked with '1', select one at random. 3. Now mark all points in the distance of 30 from the chosen cell, those that you never want to pick again, as not good ('0'). 4. Go to 2. About point 2: You can just shoot random samples until you get a '1' cell, or you could optimize by a pointer array. This kind of optimization is simple to code, though it might not really be needed in your case. A simple example, from a unidimensional world, is a virtual card deck from which you draw cards. You code it as a simple array, fill each cell in the array with the value of the card, then when you draw a card, you take the last cell of the array, move it into the position of the 'taken' card, and consider your array as one cell shorter from that point on. Very simple, and can work also in a bidirectional case, if you got the principle. Think about marking your cell with a '0' as withdrawing a card. Kind regards, David. Quote:
> I can yank random numbers from ranges etc. all day. But now, I need a little > more and I am tripping to solve this one. > #Problem: > Lets say I need to generate 60 random pairs of numbers ($x,$y) ... where $x > is from a range of 1..1200 and $y is from a range of 1..800. Consider these > pairs as a random point or coordinate on a grid of 1200x800. > In addition to this, each pair must be unique, in that > 1. no pair can be the same > 2. no pair can be within 30 of another > #Example: > Pair 1: 50,100 > Pair 2: 32,135 > Pair 3: 31,130 > etc.. > Assuming that the pair numbers are checked before being added to a final > list... > Pair 2 is ok because only one number is within 30 of Pair 1. But, Pair 3 is > NOT ok, because both numbers are within 30 of another pair (Pair 2). > I don't want the pairs/coordinates to be perfectly spaced by 30. There's no > need because at 1200x800 there are 960k available points... and if no two > are within 30 of another, there are still 320k possibilities. > Any assistance here would be greatly appreciated! > Shawn
 *** David Hiskiyahu, Alcatel SRD, 1 Fr.Wellesplein, Antwerp *** *** Phone/Fax: +32 3 240 7965/9820, private +32 3 290 0912 *** Quote of the Day Some cause happiness wherever they go; others, whenever they go.  Oscar Wilde

Sat, 05 Jul 2003 03:15:40 GMT 


Abiga #8 / 25

Random Numbers with a Twist
September MCMXCIII in <URL::">
__ > __ >Lets say I need to generate 60 random pairs of numbers ($x,$y) ... where $x __ >is from a range of 1..1200 and $y is from a range of 1..800. Consider these __ >pairs as a random point or coordinate on a grid of 1200x800. __ > __ >In addition to this, each pair must be unique, in that __ >1. no pair can be the same __ >2. no pair can be within 30 of another __ __ Well, you could conceptually tile your rectangle with 30x30 squares, __ and select 60 of those at random. Then, in a second step, select a __ random point in each preselected square. That of course doesn't garantee to satisfy the conditions. Suppose two of your squares are (1, 1) x (30, 30) and (31, 1) x (60, 30). Now, point (25, 10) lies in the first square, and (35, 15) in the second, but they aren't 30 apart. Abigail  sub f{sprintf$_[0],$_[1],$_[2]}print f('%c%s',74,f('%c%s',117,f('%c%s',115,f( '%c%s',116,f('%c%s',32,f('%c%s',97,f('%c%s',0x6e,f('%c%s',111,f('%c%s',116,f( '%c%s',104,f('%c%s',0x65,f('%c%s',114,f('%c%s',32,f('%c%s',80,f('%c%s',101,f( '%c%s',114,f('%c%s',0x6c,f('%c%s',32,f('%c%s',0x48,f('%c%s',97,f('%c%s',99,f( '%c%s',107,f('%c%s',101,f('%c%s',114,f('%c%s',10,)))))))))))))))))))))))))

Sat, 05 Jul 2003 04:57:35 GMT 


Abiga #9 / 25

Random Numbers with a Twist
<URL::">
:: : Lets say I need to generate 60 random pairs of numbers ($x,$y) ... where $x :: : is from a range of 1..1200 and $y is from a range of 1..800. Consider these :: : pairs as a random point or coordinate on a grid of 1200x800. :: : :: : In addition to this, each pair must be unique, in that :: : 1. no pair can be the same :: : 2. no pair can be within 30 of another :: :: The following doesn't do much error checking, and will loop infinitely if :: presented with an impossible task (80 point on a 10 by 10 grid, separated :: by 3, for example). Unfortunally, the program is fundamentally flawed  it's based on the assumption any point can be part of at least one solution. For instance, on a 10 by 10 grid, it's possible to pick 4 points that are at least 8 apart pairwise (just pick four points near the corners). But if your program starts by picking a point near the middle as the first point, no other valid point can be found. [ Program that randomly picks point, always keeping what fits so far snipped ] Abigail

Sat, 05 Jul 2003 05:05:22 GMT 


Craig Ber #10 / 25

Random Numbers with a Twist
: <URL::">
: :: The following doesn't do much error checking, and will loop infinitely if : :: presented with an impossible task (80 point on a 10 by 10 grid, separated : :: by 3, for example). : : Unfortunally, the program is fundamentally flawed  it's based on the : assumption any point can be part of at least one solution. [explanation snipped] Quite true. My solution is good enough for sparse cases, in which early choices can't make the puzzle insoluble. For denser cases, you'd definitely need to add backtracking of some sort, or another way to detect and correct "blocking" move choices. But that's a lot more complicated to code. I chose to present a solution that meets the OP's needs, but should have gone into more detail about its weaknesses for more general tasks.   Craig Berry  http://www.cinenet.net/~cberry/ * "The hills are burning, and the wind is raging; and the clock  strikes midnight in the Garden of Allah."  Don Henley

Sat, 05 Jul 2003 06:31:00 GMT 


Shawn Coppoc #11 / 25

Random Numbers with a Twist
Thanks for all of the input. It really helped. Problem solved! I created a tiled system... each square say... 75x75 ... that gave me a 25 buffer on all sides and a random placement in the center 25. This avoided overlaps. Again, thanks for all the input! Regards, Shawn

Sat, 05 Jul 2003 14:50:52 GMT 


Joe Schaefe #12 / 25

Random Numbers with a Twist
Quote:
> Thanks for all of the input. It really helped. Problem solved! > I created a tiled system... each square say... 75x75 ... that gave me a 25 > buffer on all sides and a random placement in the center 25. This avoided > overlaps.
Huh? That doesn't sound like a solution to the question you asked. Chris' solution (although I haven't tested it, it appears to be ok) should solve your problem under the conditions you stated. Did you try it? Is it too slow or something? The solution you came up with here is rather artificial, since the vast majority of your screen (the margins of your 75x75 box) will never contain a point. If you are unsatisfied with the speed of Chris' solution or something, there are more sophisticated (aka spacefilling, or quasi)random sequences you might try instead of using the stock "rand" on your box. Try google(quasirandom space filling) to learn more about them. HTH  Joe Schaefer

Sat, 05 Jul 2003 12:11:29 GMT 


Joe Schaefe #13 / 25

Random Numbers with a Twist
Quote:
> If you are unsatisfied with the speed of Chris' solution or something,
s/Chris/Craig/  sorry about that. Misattribution seems to be going around in clp.misc :(  Joe Schaefer

Sat, 05 Jul 2003 12:24:57 GMT 


Craig Ber #14 / 25

Random Numbers with a Twist
: > If you are unsatisfied with the speed of Chris' solution or something, : : s/Chris/Craig/  sorry about that. Misattribution seems : to be going around in clp.misc :( No prob. The funny thing is that, while reading your post, I was thinking "Hm, haven't seen a post from anybody named Chris...wonder how it compares to mine?" :)   Craig Berry  http://www.cinenet.net/~cberry/ * "The hills are burning, and the wind is raging; and the clock  strikes midnight in the Garden of Allah."  Don Henley

Sat, 05 Jul 2003 13:32:16 GMT 


Anno Sieg #15 / 25

Random Numbers with a Twist
Quote:
>September MCMXCIII in <URL::">
>__ Well, you could conceptually tile your rectangle with 30x30 squares, >__ and select 60 of those at random. Then, in a second step, select a >__ random point in each preselected square. >That of course doesn't garantee to satisfy the conditions. >Suppose two of your squares are (1, 1) x (30, 30) and (31, 1) x (60, 30). >Now, point (25, 10) lies in the first square, and (35, 15) in the >second, but they aren't 30 apart.
Logic! It always gets in the way of a Good Idea. Anno

Sat, 05 Jul 2003 17:43:39 GMT 


Page 1 of 2

[ 25 post ] 

Go to page:
[1]
[2] 
