Random Numbers with a Twist
Author Message
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
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
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

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

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 15x15-squares 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
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 15x15-squares is only about

^^^^^

Looks like my math's pretty fuzzy, too. You need 60 30x30-squares,
which amounts to about 5% of the total area.  Same difference :)

--
Joe Schaefer

Sat, 05 Jul 2003 01:27:08 GMT
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
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.

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 uni-dimensional 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 bi-directional 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
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
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
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
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
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 space-filling, or quasi-)random
sequences you might try instead of using the stock "rand" on your box.

HTH
--
Joe Schaefer

Sat, 05 Jul 2003 12:11:29 GMT
Random Numbers with a Twist

Quote:

> If you are unsatisfied with the speed of Chris' solution or something,

s/Chris/Craig/ - sorry about that.  Mis-attribution seems
to be going around in clp.misc :(

--
Joe Schaefer

Sat, 05 Jul 2003 12:24:57 GMT
Random Numbers with a Twist

: > If you are unsatisfied with the speed of Chris' solution or something,
:
: s/Chris/Craig/ - sorry about that.  Mis-attribution 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
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]

Relevant Pages