[RESOLVED] random coordinates without duplicates

[adamm83]

I'm trying to generate random coordinates without duplicates.

So I would need to generate all the possible coordinates from 0,0 to 100,100 (as an example)

I do not know how to go about this? Any help

[vivek_master146]

First u create a random coordinate and store them in a variable and then check whether the new coordinate generated does not match the previous one.

[Lord Orwell]

generate a random number like this:

Randomize
Num = int(rnd() * 101) 'this generates a # between 0 and 100 randomly as an integer.

You should seed it with Randomize() first.

You didn't specify how many coordinates you need, but in that particular example, i would create a multidimensional array of the type boolean

dim Coord(100, 100) as boolean

just dimming it will automatically fill it with false
now you have a place to mark your tried coordinates.

dim Coord(100, 100) as boolean
dim x as long, y as long, cl as long
for cl = 1 to 100
   do
     x = int(rnd() * 101)
     y = int(rnd() * 101)
     if coord(x, y) = false then exit do
   loop
   coord(x, y) = true
   msgbox "unique coordinate x:" & x & " y:" & y
next

this code will generate 100 unique coordinates. the do loop makes it generate a new coordinate if it is a repeat coordinate.
I hope this helps.

[adamm83]

Hey thanks. That's a good idea!!

You didn't specify how many coordinates you need, but in that particular example, i would create a multidimensional array of the type boolean

I did specify how many coordinates. I said "all the possible coordinates". SO I would assume all the possibilities would be 100 * 100, correct?

Also, how would I go about doing it so that the starting coordinates don't necessarily have to be 0,0? Lets say I want to go from 5,8 to 200,350

[Lord Orwell]

actually no because you were going from 0 to 100. the answer is 101 * 101

just add 5 to your random total to start at 5. Same with 8.
So basically you want every coordinate but randomly selected. I don't suppose you are fading in a picture?

[adamm83]

just add 5 to your random total to start at 5. Same with 8.

What about the multidimensional array?

I don't suppose you are fading in a picture?

no, otherwise I wouldn't need it to be random. I'm just fooling around, trying to make something for myself

[Lord Orwell]

well you are in luck in vb6. .net won't let you do this, but in vb, you could put this:
dim (5 to 99, 243 to 999) as boolean 'for example

[adamm83]

is there a 999 limit or did you just use 999 as an example?

[Lord Orwell]

dim myarray(5 to 99, 243 to 999) as boolean 'for example

[Lord Orwell]

sorry i have to go i connect with a cell phone and there is some kind of cell problem. no there is no limit. Just memory

[adamm83]

I declared the array like this:

Dim Coord(xStart To xEnd, yStart To yEnd) As Boolean

and i this error:
"Constant expression required"

Any ideas? The xStart, xEnd, yStart, yEnd variables are declared as integer. Can I declare the array using other variables?

[vivek_master146]

What values are u putting. Use debug to see what problem u have

[adamm83]

I figured out the problem. I could not use variables in the original declaration of the array. I had to redim the array within the sub-routine.

I had another question. Since the array is dynamic and depends on what is passed into the program, is there a way to determine the length of the multidimensional array?

[robbedaya]

Dim Coord(xStart To xEnd, yStart To yEnd) As Boolean

I think you can not use variables in the declaration of a array to set size.
xStart, xEnd, yStart, yEnd must be constants or must be replaced by their values.

[adamm83]

any idea how to get the length of a multidimensional array?

[leinad31]

I'm trying to generate random coordinates without duplicates.

So I would need to generate all the possible coordinates from 0,0 to 100,100 (as an example)

I do not know how to go about this? Any help

Create a sorted array first, data type up to you (eg, string with values as csv, udt). Then randomize the order of the array elements. (From lbound to ubound, pick randomly another array element and swap them).

After you've done that, simply maintain an index where you last pulled a value and increment it accordingly. So you wouldn't get the same pair twice since your iterating through the array.

It will need time to initially randomize the order of the entire list, but once done you won't run into performance problems later on. Imagine there's just one pair left... you'll have to wait until Rnd() by chance points to that unused pair somewhere in the list... but if the list was randomized and you just iterated through it then last unused pair will be at array Ubound().

[adamm83]

Create a sorted array first, data type up to you (eg, string with values as csv, udt). Then randomize the order of the array elements. (From lbound to ubound, pick randomly another array element and swap them).

After you've done that, simply maintain an index where you last pulled a value and increment it accordingly. So you wouldn't get the same pair twice since your iterating through the array.

It will need time to initially randomize the order of the entire list, but once done you won't run into performance problems later on. Imagine there's just one pair left... you'll have to wait until Rnd() by chance points to that unused pair somewhere in the list... but if the list was randomized and you just iterated through it then last unused pair will be at array Ubound().

This makes a lot of sense! I used orwell's code and it takes about 6 seconds to randomly generate approx 380,000 coordinates, but I DO notice that at the very end about 98-100% it takes slightly longer. I never thought about it that way.

But wouldn't your way run into the same problem? Wouldn't it take a bit longer to find that last random index when swapping? Could you give me a code example of how I could do the "swapping"?

[krtxmrtz]

well you are in luck in vb6. .net won't let you do this, but in vb, you could put this:
dim (5 to 99, 243 to 999) as boolean 'for example

Have not met .net yet but I'm curious, you mean .net allows only to start the first element at 0 (or 1)?

[extreme.aly]

the lowest bound must be 0

[leinad31]

This makes a lot of sense! I used orwell's code and it takes about 6 seconds to randomly generate approx 380,000 coordinates, but I DO notice that at the very end about 98-100% it takes slightly longer. I never thought about it that way.

But wouldn't your way run into the same problem? Wouldn't it take a bit longer to find that last random index when swapping? Could you give me a code example of how I could do the "swapping"?

Sample with using long data type, adjust for your user defined type or whatever structure your using to hold the pairs. If your gonna use classes to define the pair then a collection implementation rather than an array would be more appropriate.

The number of iterations is predetermined. The range for the random number remains fixed.

Option Explicit

Private arrValues() As Long  
Private Const ARR_UBOUND As Long = 100  
Private lngNextIdx As Long

Private Sub Form_Load()
Dim i As Long
Dim lngIdx As Long
Dim lngTmp As Long

   ReDim arrValues(ARR_UBOUND)  'then generate ordered list
   For i = 0 To ARR_UBOUND
      arrValues(i) = i
   Next

   Randomize  'then randomize list
   For i = 0 To ARR_UBOUND
      lngIdx = Int((ARR_UBOUND+1) * Rnd) 'Int((upperbound - lowerbound + 1) * Rnd + lowerbound)
      If lngIdx <> i Then 'swap
         lngTmp = arrValues(lngIdx)
         arrValues(lngIdx) = arrValues(i)
         arrValues(i) = lngTmp
      End If   
   Next

   lngNextIdx = 0
End Sub

Private Sub cmdGetNum_Click()
   If lngNextIdx > ARR_UBOUND Then
      MsgBox "No more values left in list.", vbOkOnly
      Exit Sub
   End If
   MsgBox "Index: " & lngNextIdx & vbCrLf & "Value: " & arrValues(lngNextIdx)
   lngNextIdx = lngNextIdx + 1
End Sub

[jeroen79]

If you want all coordinates then the randomness would be in their sequence.
Would it be more efficient to first generate all coordinates in sequence and then shuffle them?

Type tCoord
    X As Long
    Y As Long
End Type

Function RandomCoords() As tCoord()
Dim Coords() As tCoord
Dim Results() As tCoord
Dim Taken() As Boolean
Dim i As Long
Dim j As Long
Dim k As Long

    ReDim Coords(101 * 101)
    ReDim Results(101 * 101)
    ReDim Taken(101 * 101)
    
    k = 0
    For i = 0 To 100
        For j = 0 To 100
            Coords(k).X = i
            Coords(k).Y = j
            k = k + 1
        Next j
    Next i
    
    For i = 0 To 101 * 101
        Do
            j = Rnd * 101 * 101
        Loop While Taken(j)
        Results(i) = Coords(j)
        Taken(j) = True
    Next i
    
    RandomCoords = Results
End Function

[leinad31]

If you want all coordinates then the randomness would be in their sequence.
Would it be more efficient to first generate all coordinates in sequence and then shuffle them?

If your gonna exhaust the list then yes it would be easier to manage... you trade time spent on initial randomization in exhange of simplicity and guarantee of no duplicate selections.

There's also the question of can you afford the delay in the middle of the job/task/processing, or would it be better to let the user wait during initialization than in the middle of processing?

Another way of looking at it is you try to avoid setting up the complete list but end up maintaining a data struct for selected items almost the same, if not the same, size as the complete list.

On the other hand, if your gonna pull just a few random values then it would be more efficient to maintain data structure of those already selected instead.

Specific requirements and actual use (are there any other considerations?) will determine best way of tackling the problem. A one size fits all approach doesn't always work.

[adamm83]

leinad31,
I have a question about your code. You have no check to see if the index was already chosen. So in theory, couldn't it just continuously swap index 1 and 2 until it reaches 100? (obviously it wouldn't, but it COULD)

jeroen79,
your code makes a bit more sense to me because you have that boolean variable to rule out the already swapped indexes. Unfortunately because I'm dealing with such a high number (approx 330,000 indices -- 600 x 550), I get an overflow error when declaring the single dimensional array. I was able to use a multidimensional array without problems though.

Specific requirements and actual use (are there any other considerations?) will determine best way of tackling the problem. A one size fits all approach doesn't always work.

Basically, I need to generate all the possible coordinates up to 600x550, randomize it and do something with EACH coordinate in the random order.

I don't care about a delay when adding the coordinates to the array. Here is the code I have used to load the random coordinates into the multidimensional array (only). It seems to work perfectly, but as both of you said, the only way to ensure that there are no duplicates is to load up all the coordinates in order first, then randomize the indices.

Option explicit

Public Type RECT
Left As Long
Top As Long
Right As Long
Bottom As Long
End Type

Public mpRec As RECT
Public Coord() As String

Private Sub Form_Load()
Randomize
genCoords
End Sub

Sub genCoords()
Dim intPos() As String
Dim booCoord() As Boolean
Dim i, X, Y As Integer
Dim iLen As Long

mpRec.Left = 0
mpRec.Top = 0
mpRec.Right = 600
mpRec.Bottom = 550

'redim arrays to dynamic variables
ReDim booCoord(mpRec.Left To mpRec.Right, mpRec.Top To mpRec.Bottom)
iLen = (((mpRec.Right - mpRec.Left) + 1) * ((mpRec.Bottom - mpRec.Top) + 1))
ReDim Coord(iLen)

For i = 1 To iLen
    Do
        X = Int((mpRec.Right - mpRec.Left + 1) * Rnd + mpRec.Left)
        Y = Int((mpRec.Bottom - mpRec.Top + 1) * Rnd + mpRec.Top)
        If booCoord(X, Y) = False Then Exit Do
    Loop
    booCoord(X, Y) = True
    Coord(i) = X & "," & Y
    lblPercent = Round(i / iLen * 100) & "%" 'make a textbox named lblPercent
    DoEvents
    
Next
lblPercent = "Complete! " & iLen & " coordinates"
End Sub

[Logophobic]

leinad31,
I have a question about your code. You have no check to see if the index was already chosen. So in theory, couldn't it just continuously swap index 1 and 2 until it reaches 100? (obviously it wouldn't, but it COULD)

Not exactly. Only one element of each swap is chosen at random. The other is controlled by the loop counter. That method of shuffling is flawed, though, as the results are not evenly distributed.

This very similar suffling method, on the other hand, is not flawed. The difference here is that once an element has been swapped into position i, it cannot be subsequently swapped again.

  For i = ARR_UBOUND To 1 Step -1
    lngIdx = Int((i+1) * Rnd)
    lngTmp = arrValues(lngIdx)
    arrValues(lngIdx) = arrValues(i)
    arrValues(i) = lngTmp
  Next

Below are the results of one million shuffles of a ten-element array. The array was sorted before each shuffle. The numbers in the grid show the frequency, as a percentage, that the element indicated to the left (row label) ended up in the position indicated above (column label).

The first grid uses the code that lienad31 posted. You can see that the first element (0) is equally likely to end up in any position, that all elements are equally likely to end up in the last position (9), and that there is bias in other areas.

The second grid uses the code that I have posted. It is clear that there is no bias in the results.

    0  1  2  3  4  5  6  7  8  9
0  10 10 10 10 10 10 10 10 10 10
1  13 09 10 10 10 10 10 10 10 10
2  12 12 09 09 09 09 09 10 10 10
3  11 12 12 09 09 09 09 09 10 10
4  10 11 11 12 09 09 09 09 10 10
5  10 10 11 11 12 09 09 09 10 10
6  09 10 10 11 11 12 09 09 10 10
7  09 09 10 10 11 11 12 09 09 10
8  08 09 09 10 10 11 12 12 09 10
9  08 08 09 09 10 10 11 12 13 10

    0  1  2  3  4  5  6  7  8  9
0  10 10 10 10 10 10 10 10 10 10
1  10 10 10 10 10 10 10 10 10 10
2  10 10 10 10 10 10 10 10 10 10
3  10 10 10 10 10 10 10 10 10 10
4  10 10 10 10 10 10 10 10 10 10
5  10 10 10 10 10 10 10 10 10 10
6  10 10 10 10 10 10 10 10 10 10
7  10 10 10 10 10 10 10 10 10 10
8  10 10 10 10 10 10 10 10 10 10
9  10 10 10 10 10 10 10 10 10 10

Edited to add:

Unfortunately because I'm dealing with such a high number (approx 330,000 indices -- 600 x 550), I get an overflow error when declaring the single dimensional array.

...

Dim i, X, Y As Integer

(1) You're getting an overflow error because you are using Integer variables, and the result of the calculation is too large for that type. Use Long variables, and you won't have a problem.

(2) That Dim statement only declares Y as an Integer. Variables i and X are implicitly declared as Variant. In VB you can declare variables of different types on the same line, so you must specify the type for each variable.

[Lord Orwell]

any idea how to get the length of a multidimensional array?

here's some sample code i wrote just for you (aren't you special)

type Lord
   .alpha as double
   .omega as double
end type

dim Orwell(5 to 8, 99 to 1234) as Lord
msgbox lbound(Orwell, 1)
msgbox lbound(Orwell, 2)
msgbox ubound(orwell, 1)
msgbox ubound(orwell, 2)

[adamm83]

Hey, Thanks lord orwell! I do feel special! I appreciate the time you spent.