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
Printable View
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
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.
generate a random number like this:
You should seed it with Randomize() first.Code:Randomize
Num = int(rnd() * 101) 'this generates a # between 0 and 100 randomly as an integer.
You didn't specify how many coordinates you need, but in that particular example, i would create a multidimensional array of the type boolean
just dimming it will automatically fill it with falseCode:dim Coord(100, 100) as boolean
now you have a place to mark your tried coordinates.
this code will generate 100 unique coordinates. the do loop makes it generate a new coordinate if it is a repeat coordinate.Code: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
I hope this helps.
Hey thanks. That's a good idea!!
I did specify how many coordinates. I said "all the possible coordinates". SO I would assume all the possibilities would be 100 * 100, correct?Quote:
Originally Posted by Lord Orwell
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
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?
What about the multidimensional array?Quote:
Originally Posted by Lord Orwell
no, otherwise I wouldn't need it to be random. I'm just fooling around, trying to make something for myselfQuote:
Originally Posted by 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
is there a 999 limit or did you just use 999 as an example?
dim myarray(5 to 99, 243 to 999) as boolean 'for example
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
I declared the array like this:
and i this error:Code:Dim Coord(xStart To xEnd, yStart To yEnd) As Boolean
"Constant expression required"
Any ideas? The xStart, xEnd, yStart, yEnd variables are declared as integer. Can I declare the array using other variables?
What values are u putting. Use debug to see what problem u have
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?
I think you can not use variables in the declaration of a array to set size.Code:Dim Coord(xStart To xEnd, yStart To yEnd) As Boolean
xStart, xEnd, yStart, yEnd must be constants or must be replaced by their values.
any idea how to get the length of a multidimensional array?
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).Quote:
Originally Posted by adamm83
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.Quote:
Originally Posted by leinad31
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"?
Have not met .net yet but I'm curious, you mean .net allows only to start the first element at 0 (or 1)?Quote:
Originally Posted by Lord Orwell
the lowest bound must be 0
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.Quote:
Originally Posted by adamm83
The number of iterations is predetermined. The range for the random number remains fixed.
Code: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
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?
Code: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
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.Quote:
Originally Posted by jeroen79
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.
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.
Basically, I need to generate all the possible coordinates up to 600x550, randomize it and do something with EACH coordinate in the random order.Quote:
Originally Posted by leinad31
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.
Code: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
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.Quote:
Originally Posted by adamm83
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.
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).Code:For i = ARR_UBOUND To 1 Step -1
lngIdx = Int((i+1) * Rnd)
lngTmp = arrValues(lngIdx)
arrValues(lngIdx) = arrValues(i)
arrValues(i) = lngTmp
Next
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.
Edited to add:Code: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
(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.Quote:
Originally Posted by adamm83
(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.
here's some sample code i wrote just for you (aren't you special)Quote:
Originally Posted by adamm83
Code: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)
Hey, Thanks lord orwell! I do feel special! :) I appreciate the time you spent.