Random Sorting Issues - Probably an easy fix!!

lee__48 · Post by **lee__48** » Thu Feb 01, 2007 12:07 am

Hi All!

I'm trying to write some code, but I'm stuck for an efficient solution. I have up to 9 buttons, and I want to pass a number between 1 and 9 to a procedure to make x number of buttons light up, but I want this change to affect a random selection of those 9 buttons.

Code: Select all

e.g.
For 2 buttons to light up I don’t want this:
+--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ 
|XX| |XX| |  | |  | |  | |  | |  | |  | |  |
|XX| |XX| |  | |  | |  | |  | |  | |  | |  |
+--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ 
I would like this:
+--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ 
|  | |  | |XX| |  | |  | |  | |XX| |  | |  |
|  | |  | |XX| |  | |  | |  | |XX| |  | |  |
+--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ 
Where any two of the buttons can light up when the procedure is called.

I thought about getting a random number between 1 and 9 and repeating this until x squares were lit, but if I wanted 9 squares to light, I’d feel this was inefficient and the loop could possibly run for a long time until the result was the remaining button.

I then thought I could have to dim()’s. One with numbers 1 to 9, and one with randomly generated numbers between 1 and 100. I could then sort both dim()’s in the order of the random numbers, but I can’t figure how to do this.

Code: Select all

e.g.
I would want to change this:
Dim_one() Dim_two()
(1)=1     (1)=60 (these numbers are randomly generated)
(2)=2     (2)=20
(3)=3     (3)=70
(4)=4     (4)=50
(5)=5     (5)=30
(6)=6     (6)=10
(7)=7     (7)=90
(8)=8     (8)=40
(9)=9     (9)=80

to this:
Dim_one() Dim_two()
(1)=7     (1)=90
(2)=9     (2)=80
(3)=3     (3)=70
(4)=1     (4)=60
(5)=4     (5)=50
(6)=8     (6)=40
(7)=5     (7)=30
(8)=2     (8)=20
(9)=6     (9)=10

Say I wanted 2 buttons on, I could write some code to light up buttons 7 and 9, and as the random numbers would be different each time the order would change each time. I guess in SQL this would be something like:

Code: Select all

GET Dim_one(), Dim_two() FROM table SORT BY Dim_two()

Any help or alternative methods would be much appreciated.

Lee

srod · Post by **srod** » Thu Feb 01, 2007 12:34 am

I think your algorithm is pretty sound, providing you sort the array as you construct the random numbers (kind of like a shuttle sort).

Alternatively, you might start with a single array containing digits 1 to 9:

Code: Select all

(1)=1
(2)=2
(3)=3
(4)=4
(5)=5
(6)=6
(7)=7
(8)=8
(9)=9

Suppose you want to select 2 unique digits at random. Start with a random digit between 1 and 9. Suppose it is 4. Remove the 4th element of the above array (simply shift them along) to get another array:

Code: Select all

(1)=1
(2)=2
(3)=3
(4)=5   (the 4 has gone)
(5)=6
(6)=7
(7)=8
(8)=9

Now select a random number between 1 and 8. Suppose it is 7. Since the 7th element contains 8 we thus have our two unique random numbers between 1 and 9.

Each time you have to remove an element from the array etc.

With this method, it would perhaps be most efficient to implement this as a string, i.e. use the string "123456789" in place of an array and then use PB's string functions.

Of course this is identical to searching a list, ignoring those numbers already selected etc.

Derek · Post by **Derek** » Thu Feb 01, 2007 10:19 am

Try this

Code: Select all

dim a(9)
for n=1 to 9
   a(n)=n
next

;randomise array
for n=1 to 20
   swap a(random(8)+1),a(random(8)+1)
next

for n=1 to 9
   debug a(n)
next

Use this to randomize your array each time and then just take the first x number of elements.

Kaeru Gaman · Post by **Kaeru Gaman** » Thu Feb 01, 2007 11:16 am

lee__48 wrote:I thought about getting a random number between 1 and 9 and repeating this until x squares were lit, but if I wanted 9 squares to light, I’d feel this was inefficient and the loop could possibly run for a long time until the result was the remaining button.

correct assumption, but it mainly takes place for really high ranges of numbers like 10000 or 65536.
for just nine, its neglectable.

Code: Select all

Dim test(8)

Repeat
  light = Random(8)
  If test(light) = 0
    test(light) = 1
    Debug light 
    lit +1
  EndIf
Until lit = 9

_____________________________________________

@Derek
interesting approach. thnx for sharing the idea.

Derek · Post by **Derek** » Thu Feb 01, 2007 11:24 am

The beauty of my approach is that you never have to reset array contents or do any testing making it quite a quick little routine.

srod · Post by **srod** » Thu Feb 01, 2007 11:28 am

Nice one Derek.

However, statistically speaking, such a method will not generate truly random numbers. The main problem is that you select from the beginning of the array before the array is truly 'randomised'. 2 ways around this. Either select randomly (which then defeats the object of randomly swapping elements) or swap more than 20 random pairs - much more!

In fact for this to approach a truly random selection you need to switch at least as many pairs as you would when performing the sort which lee_48 already described.

Still for only 9 elements, it should be fine!

Kaeru Gaman · Post by **Kaeru Gaman** » Thu Feb 01, 2007 11:37 am

I couldn't resist to write a little test for the classic approach.

I think it doesn't take too long to find the last free number by random.

Code: Select all

Dim test(9)

OpenWindow(0,0,0,400,200,"random tester")
CreateGadgetList(WindowID(0))
ButtonGadget(0, 120, 130, 160, 40, "next light")
For n=0 To 8
  CheckBoxGadget(n+1, 24+40*n, 24, 32, 32, Str(n+1))
Next

Repeat
  EvID = WaitWindowEvent()
  If EvID = #PB_Event_Gadget
    GadID = EventGadget()
    Select GadID
; ********************************      
      Case 0    ; next Light
      ; counting number of already lit boxes
        count = 0 : For n=1 To 9 : count + test(n) : Next 
        If count < 9
          Repeat
            light = Random(8)+1
          Until test(light) = 0
            test(light) = 1
            SetGadgetState(light,1)
        EndIf
; ********************************      
      Case 1 To 9
        test(GadID) = GetGadgetState(GadID)
    EndSelect
  EndIf
Until EvID = #PB_Event_CloseWindow

Derek · Post by **Derek** » Thu Feb 01, 2007 11:50 am

Code: Select all

Dim b.s(10000)

Dim a(9)
For n=1 To 9
  a(n)=n
Next

For m=0 To 10000
  For n=1 To 20
    Swap a(Random(8)+1),a(Random(8)+1)
  Next
  t.s=""
  For n=1 To 9
    t+Str(a(n))
  Next
  b(m)=t
Next

SortArray(b(),0)
multiples=0
For n=0 To 9999
  If b(n)=b(n+1)
    Debug b(n)
    multiples+1
  EndIf
Next
Debug Str(multiples)+" multiples found out of 10000"

Seems to be about 140 times out of 10000 that you get the same 9 numbers repeated which isn' bad. Random enough I would think.

*** Edit, if you didn't get the numbers repeated then it wouldn't be random, you would actually have to be preventing the repeats from happening!

srod · Post by **srod** » Thu Feb 01, 2007 11:57 am

Aye, it'd do me!

Derek · Post by **Derek** » Thu Feb 01, 2007 12:02 pm

@srod, but like you said, you can always up the number of swap's, even 100 times is instant, at least on my computer.

lee__48 · Post by **lee__48** » Thu Feb 01, 2007 11:32 pm

Thanks srod, Derek and Kaeru Gaman for your replies. I still couldn't justify using the "classic approach", although it was pretty fast!

I liked srod's idea, taking values from a string, but I've implemented Derek's code. I've not noticed the Swap command before, but it seems it offers a much easier solution to what I was heading for.

Thanks again for your help! If your interested this is what I was trying to write. It's based on the Tix clock from firebox.com. I can't afford it, so I thought I'd make my own!! It still needs some work - I'm hoping to use it for my screensaver.

Lee

Code: Select all

updateDelay = 2000

If InitKeyboard() = 0 Or InitSprite() = 0
  MessageRequester("Error", "Can't open DirectX 7", 0)
  End
EndIf

ExamineDesktops()
If OpenScreen(DesktopWidth(0), DesktopHeight(0), DesktopDepth(0), "tix")
 ; do nothing!
Else
 MessageRequester("Error", "Can't open a new screen", 0)
 End
EndIf

screenWidth = DesktopWidth(0)
screenHeight = DesktopHeight(0)
spriteSize = screenHeight/11
leftMargin = (screenWidth-((spriteSize*14)+50))/2

;- Create Sprites

CreateSprite(1, spriteSize, spriteSize, 0)
If StartDrawing(SpriteOutput(1))
  Box(0, 0, spriteSize, spriteSize, RGB(255,0,0))
  StopDrawing()
EndIf

CreateSprite(2, spriteSize, spriteSize, 0)
If StartDrawing(SpriteOutput(2))
  Box(0, 0, spriteSize, spriteSize, RGB(0,255,0))
  StopDrawing()
EndIf

CreateSprite(3, spriteSize, spriteSize, 0)
If StartDrawing(SpriteOutput(3))
  Box(0, 0, spriteSize, spriteSize, RGB(0,0,255))
  StopDrawing()
EndIf

CreateSprite(4, spriteSize, spriteSize, 0)
If StartDrawing(SpriteOutput(4))
  Box(0, 0, spriteSize, spriteSize, RGB(255,128,0))
  StopDrawing()
EndIf


CreateSprite(5, spriteSize, spriteSize, 0)
If StartDrawing(SpriteOutput(5))
  Box(0, 0, spriteSize, spriteSize, RGB(255,0,0))
  Box(5, 5, spriteSize-10, spriteSize-10, RGB(0,0,0))
  StopDrawing()
EndIf

CreateSprite(6, spriteSize, spriteSize, 0)
If StartDrawing(SpriteOutput(6))
  Box(0, 0, spriteSize, spriteSize, RGB(0,255,0))
  Box(5, 5, spriteSize-10, spriteSize-10, RGB(0,0,0))
  StopDrawing()
EndIf

CreateSprite(7, spriteSize, spriteSize, 0)
If StartDrawing(SpriteOutput(7))
  Box(0, 0, spriteSize, spriteSize, RGB(0,0,255))
  Box(5, 5, spriteSize-10, spriteSize-10, RGB(0,0,0))
  StopDrawing()
EndIf

CreateSprite(8, spriteSize, spriteSize, 0)
If StartDrawing(SpriteOutput(8))
  Box(0, 0, spriteSize, spriteSize, RGB(255,128,0))
  Box(5, 5, spriteSize-10, spriteSize-10, RGB(0,0,0))
  StopDrawing()
EndIf

InitMouse()  
ClearScreen(RGB(0,0,0))

wait = updateDelay+1

nBox1 = 3
nBox2 = 9
nBox3 = 6
nBox4 = 9

Dim a(nBox1)
Dim b(nBox2)
Dim c(nBox3)
Dim d(nBox4)

;- Main Loop
Repeat
  If wait > updateDelay
    box1 = Val( Left (FormatDate("%hh", Date() ),1) ) ; Red
    box2 = Val( Right(FormatDate("%hh", Date() ),1) ) ; Green
    box3 = Val( Left (FormatDate("%ii", Date() ),1) ) ; Blue
    box4 = Val( Right(FormatDate("%ii", Date() ),1) ) ; Orange
    
    ;- Box 1
    For n=1 To nBox1
       a(n)=n
    Next

    For n=1 To nBox1*10
       Swap a(Random(nBox1-1)+1),a(Random(nBox1-1)+1)
    Next
    
    DisplaySprite( 5, leftMargin+spriteSize, (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
    DisplaySprite( 5, leftMargin+spriteSize, (screenHeight/2)-(spriteSize/2) )
    DisplaySprite( 5, leftMargin+spriteSize, (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )
    
    For n=1 To box1
      If a(n)=1
        DisplaySprite( 1, leftMargin+spriteSize, (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
      EndIf
      If a(n)=2
        DisplaySprite( 1, leftMargin+spriteSize, (screenHeight/2)-(spriteSize/2) )
      EndIf
      If a(n)=3
        DisplaySprite( 1, leftMargin+spriteSize, (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )
      EndIf
    Next 

    ;- Box 2
    For n=1 To nBox2
       b(n)=n
    Next

    For n=1 To nBox2*10
       Swap b(Random(nBox2-1)+1),b(Random(nBox2-1)+1)
    Next

    DisplaySprite( 6, leftMargin+(spriteSize*3), (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
    DisplaySprite( 6, leftMargin+(spriteSize*3), (screenHeight/2)-(spriteSize/2) )
    DisplaySprite( 6, leftMargin+(spriteSize*3), (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )
    
    DisplaySprite( 6, (spriteSize*4)+10+leftMargin, (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
    DisplaySprite( 6, (spriteSize*4)+10+leftMargin, (screenHeight/2)-(spriteSize/2) )
    DisplaySprite( 6, (spriteSize*4)+10+leftMargin, (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )
    
    DisplaySprite( 6, (spriteSize*5)+20+leftMargin, (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
    DisplaySprite( 6, (spriteSize*5)+20+leftMargin, (screenHeight/2)-(spriteSize/2) )
    DisplaySprite( 6, (spriteSize*5)+20+leftMargin, (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )

    For n=1 To box2
      If b(n)=1
        DisplaySprite( 2, leftMargin+(spriteSize*3), (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
      EndIf
      If b(n)=2
        DisplaySprite( 2, leftMargin+(spriteSize*3), (screenHeight/2)-(spriteSize/2) )
      EndIf
      If b(n)=3
        DisplaySprite( 2, leftMargin+(spriteSize*3), (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )
      EndIf
      If b(n)=4
        DisplaySprite( 2, (spriteSize*4)+10+leftMargin, (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
      EndIf
      If b(n)=5
        DisplaySprite( 2, (spriteSize*4)+10+leftMargin, (screenHeight/2)-(spriteSize/2) )
      EndIf
      If b(n)=6
        DisplaySprite( 2, (spriteSize*4)+10+leftMargin, (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )
      EndIf
      If b(n)=7
        DisplaySprite( 2, (spriteSize*5)+20+leftMargin, (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
      EndIf
      If b(n)=8              
        DisplaySprite( 2, (spriteSize*5)+20+leftMargin, (screenHeight/2)-(spriteSize/2) )
      EndIf
      If b(n)=9              
        DisplaySprite( 2, (spriteSize*5)+20+leftMargin, (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )
      EndIf
    Next     

    ;- Box 3
    For n=1 To nBox3
       c(n)=n
    Next

    For n=1 To nBox3*10
       Swap c(Random(nBox3-1)+1),c(Random(nBox3-1)+1)
    Next

    DisplaySprite( 7, (spriteSize*7)+20+leftMargin, (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
    DisplaySprite( 7, (spriteSize*7)+20+leftMargin, (screenHeight/2)-(spriteSize/2) )
    DisplaySprite( 7, (spriteSize*7)+20+leftMargin, (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )
    
    DisplaySprite( 7, (spriteSize*8)+30+leftMargin, (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
    DisplaySprite( 7, (spriteSize*8)+30+leftMargin, (screenHeight/2)-(spriteSize/2) )
    DisplaySprite( 7, (spriteSize*8)+30+leftMargin, (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )

    For n=1 To box3
      If c(n)=1
        DisplaySprite( 3, (spriteSize*7)+20+leftMargin, (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
      EndIf
      If c(n)=2
        DisplaySprite( 3, (spriteSize*7)+20+leftMargin, (screenHeight/2)-(spriteSize/2) )
      EndIf
      If c(n)=3
        DisplaySprite( 3, (spriteSize*7)+20+leftMargin, (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )
      EndIf
      If c(n)=4
        DisplaySprite( 3, (spriteSize*8)+30+leftMargin, (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
      EndIf
      If c(n)=5
        DisplaySprite( 3, (spriteSize*8)+30+leftMargin, (screenHeight/2)-(spriteSize/2) )
      EndIf
      If c(n)=6
        DisplaySprite( 3, (spriteSize*8)+30+leftMargin, (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )
      EndIf
    Next

    ;- Box 4
    For n=1 To nBox4
       d(n)=n
    Next

    For n=1 To nBox4*10
       Swap d(Random(nBox4-1)+1),d(Random(nBox4-1)+1)
    Next

    DisplaySprite( 8, (spriteSize*10)+30+leftMargin, (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
    DisplaySprite( 8, (spriteSize*10)+30+leftMargin, (screenHeight/2)-(spriteSize/2) )
    DisplaySprite( 8, (spriteSize*10)+30+leftMargin, (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )
    
    DisplaySprite( 8, (spriteSize*11)+40+leftMargin, (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
    DisplaySprite( 8, (spriteSize*11)+40+leftMargin, (screenHeight/2)-(spriteSize/2) )
    DisplaySprite( 8, (spriteSize*11)+40+leftMargin, (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )
    
    DisplaySprite( 8, (spriteSize*12)+50+leftMargin, (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
    DisplaySprite( 8, (spriteSize*12)+50+leftMargin, (screenHeight/2)-(spriteSize/2) )
    DisplaySprite( 8, (spriteSize*12)+50+leftMargin, (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )

    For n=1 To box4
      If d(n)=1
        DisplaySprite( 4, (spriteSize*10)+30+leftMargin, (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
      EndIf
      If d(n)=2
        DisplaySprite( 4, (spriteSize*10)+30+leftMargin, (screenHeight/2)-(spriteSize/2) )
      EndIf
      If d(n)=3
        DisplaySprite( 4, (spriteSize*10)+30+leftMargin, (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )
      EndIf
      If d(n)=4
        DisplaySprite( 4, (spriteSize*11)+40+leftMargin, (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
      EndIf
      If d(n)=5
        DisplaySprite( 4, (spriteSize*11)+40+leftMargin, (screenHeight/2)-(spriteSize/2) )
      EndIf
      If d(n)=6
        DisplaySprite( 4, (spriteSize*11)+40+leftMargin, (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )
      EndIf
      If d(n)=7
        DisplaySprite( 4, (spriteSize*12)+50+leftMargin, (screenHeight/2)-(spriteSize/2)-(spriteSize+10) )
      EndIf
      If d(n)=8              
        DisplaySprite( 4, (spriteSize*12)+50+leftMargin, (screenHeight/2)-(spriteSize/2) )
      EndIf
      If d(n)=9              
        DisplaySprite( 4, (spriteSize*12)+50+leftMargin, (screenHeight/2)-(spriteSize/2)+(spriteSize+10) )
      EndIf
    Next
    
    FlipBuffers()
    wait = 0
    
  EndIf
  Delay(1)
  wait = wait + 1
  ExamineMouse()
Until MouseButton(#PB_MouseButton_Left)

Derek · Post by **Derek** » Fri Feb 02, 2007 12:48 pm

Very nice.

Just a suggestion, I notice a lot of the code is more or less the same, have you thought about using procedures or subroutines and just altering a variable before calling the routine, would shorten your code a lot.

Might save you some typing, of course if you are using cut and paste then it won't really make that much difference to you.

Kaeru Gaman · Post by **Kaeru Gaman** » Fri Feb 02, 2007 2:40 pm

I still couldn't justify using the "classic approach", although it was pretty fast!

I understand that.
It's not that good feeling, to use a loop when you have no idea how often it will be looped...

> It's based on the Tix clock from firebox.com.

hm...
so, the fields represent numbers... ok... I'll get 25:27...?
...hm.. should i count the light boxes, not the dark ones? 14:42 ok... correct..