random sort?? 5

[Smithsco]

I have x amount of boxes which I want to set a random number to, however they can not be the same number.

I can get a random number ok but I'm not sure how to remove that number from the set.

Anyone done something like this before?

 

[johnwm]

Just generate an array of the numbers you want to use. loop through all your boxes, using Rand to get the array index. If the array value is zero, do it again. Otherwise use the array value and set that array value to zero.

Pseudocode:
For a = 1 to 10
ary(a) = a
Next
For b = 1 to 10
do while textbox(b) = 0
c = 1 + int(rnd*10)
textbox(b) = ary(c)
loop
ary(c) = 0
next b

________________________________________________________________
If you want to get the best response to a question, please check out FAQ222-2244 first

'If we're supposed to work in Hex, why have we only got A fingers?'

 

[strongm]

I still favour the "fill array, shuffle, step through shuffled array" approach

 

[Hypetia]

So do I, and also used this method in a couple of games.

The basic flaw in the first method is:

>If the array value is zero, do it again.

You might get caught into the do-loop for an indefinite number of iterations and you do not know whether you hit the correct index in just 1 iteration or 100 iterations, thus slowing down the process.

The fill-shuffle-step method is just fine and here's how it goes.
___
[tt]
Private Sub Form_Load()

'fill
Dim N As Integer
Dim A(10) As Integer
For N = 1 To 10
A(N) = N
Next

'shuffle
Dim I As Integer, X As Integer
Randomize
For N = 1 To 10
'choose a random item I
I = Int(10 * Rnd) + 1
'swap A(I) and A(N)
X = A(N)
A(N) = A(I)
A(I) = X
Next

'step
For N = 1 To 10
Debug.Print A(N)
Next

End
End Sub[/tt]

 

[Smithsco]

Thanks for the help

 

[LikeThisName]

Hypetia,

first thanks for the valuable post. i'm glad i searched before asking a similar question.

secondly, i applied your snippet to an asp page, but while the numbers were generated randomly the first time, they appear to always be the same. no matter who is accessing the asp page. i assumed it would change after each refresh.

any thoughts

dim oRS, lngrecs
Dim N, I, X
Dim A(48)

Set oRS = Server.CreateObject ("ADODB.Recordset")

strSQL= "SELECT fit_name FROM insiteCROMO.dbo.FitNames;"
set oRS = objConn.Execute(strSQL, lngrecs, 1)
rFitNames = oRS.GetRows()

For N = 1 To 48
    A(N) = N
Next

'shuffle

'Randomize
For N = 1 To 48
    'choose a random item I
    I = Int(10 * Rnd) + 1
    'swap A(I) and A(N)
    X = A(N)
    A(N) = A(I)
    A(I) = X
Next

'step
For N = 1 To 48
	Response.Write A(N)-1
	Response.Write rFitNames(0,(A(N)-1)) & "<BR>"
Next

the order is always
43The Bottom Lines
46Slim & Fit
38The Young and the Restless
24Thin Mints

etc...

LikeThisName <- ? Sorry It's Taken =)

 

[Golom]

Looks like you have [blue]Randomize[/blue] commented out. That statement is required to initialize the random number generator to different starting points. If you don't run it before calling "Rnd" then you will always get the same sequence.

 

[LikeThisName]

i got a solution

i randomized it in the sql statement using this as my sort:

ORDER BY ROUND(COS(fit_name_id * RAND()), 2)

i got this from post:

http://tek-tips.com/viewthread.cfm?SQID=378660&SPID=183&page=1

now i know two great ways thanks

LikeThisName <- ? Sorry It's Taken =)

 

[LikeThisName]

Thanks for clarifying Golom.

LikeThisName <- ? Sorry It's Taken =)

 

[Kavius]

Just happened across this and while I agree you don't want to just grab numbers at random (indefinate loops), you add an unnecessary performance hit by using shuffle-step. There is a modification to the first one that works solves the indefinate loop problem:

int seed[100];
int seedsize;
  
void InitRandArr()
{
  //intialize your seed array
  for(seedsize=0; seedsize<100; seedsize++){
    seed[seedsize] = seedsize;
  }
}

int GetUniqRand()
{
  int val;
  int index;
  
  //get the value
  index = (rand()*1.0/MAX_RAND)*seedsize;
  val = seed[index];
  
  //that value is no longer an option
  seedsize--;
  seed[index] = seed[seedsize];

  return(val);
}

Basically, you are creating the list of valid values and selecting them at random. After selecting them, they are removed from the list. This has the benefit of building the list and shuffling it on demand.

Say you generate 30000 numbers and this happens 1000 times in the application, but each time only 3-5 values are required from the list. Sure you have to do the list generation and the like 1000 times, but it takes a while to shuffle 30000 values.

By only selecting 1 random value per request you spare yourself the hit on shuffling (esentially you only shuffle one digit per request), while not having to worry about it grabbing values it has already grabbed (they are avaible to be selected from anymore).

 

[LikeThisName]

is that javascript?

LikeThisName <- ? Sorry It's Taken =)

 

[Kavius]

'C', but it would probably work as JavaScript without any changes. Sometimes I write code in C because it forces students to think about what I have told them while seasoned guys can usually pick up on the concept I am gettting at anyway.

In this case I just wasn't thinking.

dim seed(99) as integer
dim seedsize as integer
  
sub InitRandArr()
  'intialize your seed array
  for seedsize = 0 to 99
    seed(seedsize) = seedsize
  next
  seedsize = 100
end sub

function GetUniqRand() as Integer
{
  dim val as integer
  dim index as integer
  
  'get the value
  index = rnd()*(seedsize-1)
  val = seed(index);
  
  'that value is no longer an option
  seedsize = seedsize - 1
  seed(index) = seed(seedsize);

  return(val);
}

I didn't think you would be watching this thread anymore. I just added the code for people searching in the future.

I remember having a big discussion with a guy in school about this and we concluded that this is the single most efficient way to shuffle a deck of cards in code (his name was Steve Gardener).

 

[strongm]

No, it's C

Here's a VB translation:

Private seed(100) As Long
Private seedsize As Long
  
Public Sub InitRandArr()
    For seedsize = 0 To UBound(seed) - 1
        seed(seedsize) = seedsize
    Next
End Sub

Public Function GetUniqRand() As Long
    Dim val As Long
    Dim index As Long
    
    index = Int(Rnd * seedsize)
    val = seed(index)
    seedsize = seedsize - 1
    seed(index) = seed(seedsize)
    GetUniqRand = val
End Function

 

[LikeThisName]

kavius + strongm

thanks, at first glance it looked like javascript thats why i asked. it my scenario javascript wouldn't have helped me and i don't have .net editor yet so vbscript is all i got that i trust to connect to the database.

thanks for code translations here and introduction to shuffle.

LikeThisName <- ? Sorry It's Taken =)

 

[strongm]

>the single most efficient way to shuffle a deck of cards in code

As ever, I would say this very much depends on what you want to do with the 'deck'.

 

[Kavius]

> As ever, I would say this very much depends on what
> you want to do with the 'deck'.

Of course... <blush /> you are absolutely correct.

I think I am having a bad day. That makes me get a little vehement in my statements.

I notice that Hypetia's solution is actually identical to mine in concept. The only difference is that he shuffles the whole thing. The overall methodology is very efficient, there are a couple of things you can do to fine tune when the work gets done. Those fine-tuning things are very dependant on the programs usage.

In terms of Hypetia's solution and mine, Hypetia's is more efficient if you are going to use most of the numbers. Mine has the unfortunate effect of placing a little overhead at each call.

If you are going to select 99 of a 100 posible numbers then you might as well just skip the little bit of overhead and do the whole thing. If you are going to select 3 of 100 possible numbers, then you may as well add a little bit of overhead and only grab what you need.

Thank-you strongm for reigning my statement in for me.

 

[strongm]

No, no, don't worry. The whole point of these forums is to foster discussion. I think we've achieved that here...

 

[vladk]

This code generates six unique random numbers between 1 and 49 with one SQL statement on ORACLE DB:

select r
from (select r
from (select rownum r
from all_objects
where rownum < 50)
order by dbms_random.value)
where rownum <=6

vladk

 

[williamu]

Just something I came across not that long ago was using the srand() and rand() functions of C was the predictability of results when the srand() function was called again during the same second.

So if the VB versions of these (randomize and rnd) are the same (which they may well be) you may well suffer from the same issue as I did.


William
Software Engineer
ICQ No. 56047340