shuffle_array proc

[KeepingRealBusy]

Hutch,

I have several questions about "shuffle_array proc" you described in the old UK forum. Note that this method is the method I have used since days of yore.

The problem I see is that at the end, there are only two locations available (all of the others have been randomized). The calculated random number can only be 0 or 1, meaning that you will replace the incrementing location with itself (if the random number is 0), or with the end number (if the random number is 1). Now if the last location has never been selected in the prior randomizations, then, at most, the last number can only move is 0 or 1 locations.

Would it be better to make a second pass starting at the opposite end from the initial pass to further disperse the end locations?

Second question. Should the incrementing location ever be allowed to be replaced with itself (if the random number is 0)? Or should the the first possible  replacement loocation always be the location just past the incrementing location? Note that in a completely random world, the result COULD be the starting set.

Dave.

[hutch--]

Dave,

This is the shuffle algo in the current version of MASM32.

Code Select Expand


; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

shuffle_array proc arr:DWORD,cnt:DWORD

    LOCAL lcnt  :DWORD

    mov eax, cnt            ; copy cnt to lcnt
    mov lcnt, eax

    push ebx
    push esi
    push edi

    mov esi, arr
    mov edi, arr
    xor ebx, ebx

  @@:
    invoke nrandom, cnt     ; get the random number within "cnt" range
    mov ecx, [esi+ebx*4]    ; get the incremental pointer
    mov edx, [edi+eax*4]    ; get the random pointer
    mov [esi+ebx*4], edx    ; write random pointer back to incremental location
    mov [edi+eax*4], ecx    ; write incremental pointer back to random location
    add ebx, 1              ; increment the original pointer
    sub lcnt, 1             ; decrement the loop counter
    jnz @B

    pop edi
    pop esi
    pop ebx

    ret

shuffle_array endp

; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤


I think you have misunderstood the algo, it uses a library routine that provides random numbers within a user specified range. The basic algo is an old card shuffling one that has been around forever and part of its design IS to select the swap pair randomly and NOT interfere with the random pointer.

You test the result with an app like ENT to see what the distribution is like. To do this you use an ordered array, (1,2,3,4,5,6,7,8 etc...) then randomise it then test it.

[KeepingRealBusy]

Hutch,

As far as I can see, this is the same as the old version, no problems there. I have been using a similar procedure for years.

Do you have a link for ENT? Couldn't find anything on Google for Ent or Entropy. I would be interested in checking how random my RNG really is.

Dave.

[Tedd]

The thing to note is that the final element may have already been swapped multiple times with previous elements, so it's not necessarily the same as the original final element - so it's not necessary to force it to be swapped afterward.


Also, ENT: http://www.fourmilab.ch/random/

[KeepingRealBusy]

Tedd,

Thank you for the link. I will see what kind of output ENT produces and test my RNG with multiple seeds and many iterations against a 256 element array, and then test nrandom with the same seeds and iterations and array.

It is interesting that neither Google nor Wiki came up with that link. With this post (as much as Google is data mining these forums), it will now probably show up.

Dave.