_RandomUnique - Generate unique random numbers [updated 2011-11-24]

money · November 22, 2011

About:

_RandomUnique: Returns an array of unique random numbers

I found by billthecreator that was posted a while back. Insufficient for my needs (note the concerns of WideBoyDixon), I wrote my own function.

Features:

Sanity check
Commented code
Fast

Example:

#include <Array.au3>
Global $iTime, $aRandom

; Example #1 - Return five unique numbers from 0 to 10
$iTime = TimerInit()
$aRandom = _RandomUnique(5, 0, 10, 1)
ConsoleWrite("_RandomUnique = " & @error &" : "& @extended &@lf)
$iTime = Round(TimerDiff($iTime)/1000, 5)
_ArraySort($aRandom, 0, 1)
_ArrayDisplay($aRandom, "Example #1 Generated in: "& $iTime &" sec", 100)

Function:

; #FUNCTION# ====================================================================================================================
; Version........: 1.1 - 2011/11/24
; Name...........: _RandomUnique
; Description ...: Returns an array of unique random numbers
; Syntax.........: _RandomUnique($iCount, $nMin, $nMax, [$iInt = 0, [$nSeed = Default]])
; Parameters ....: $iCount  - The amount of numbers to generate Number between 1 and 10^6-1
;                 $nMin   - The smallest number to be generated. Number between -2^31 and 2^31-1
;                 $nMax   - The largest number to be generated. Number between -2^31 and 2^31-1
;                 $iInt   - [optional] If this is set to 1 then an integer result will be returned. Default is a floating point number.
;                 $nSeed     - [optional] Seed value for random number generation. Number between -2^31 and 2^31-1
; Return values .: Success  - Returns a 1-dimensional array containing only unique numbers
;                            $Array[0] = count of generated numbers
;                            $Array[1] = first number
;                            $Array[2] = second number, etc
;                Failure     - Returns 0 and sets @error:
;                               | 1 - $iCount is too small
;                               | 2 - $iCount is too large
;                               | 3 - $nMin and $nMax are equal
;                               | 4 - $nMin is larger than $nMax
;                               | 5 - $nMin or $nMax exceeds limit
;                               | 6 - $nSeed exceeds limit
; Author ........: money
; Modified.......:
; Remarks .......:  If $iInt is 1 and $iCount exceeds total unique numbers than @extend is set to 1 and item count is adjusted to the
;                  + maximum numbers that can be returned
; Related .......:
; Link ..........:
; Example .......: Yes
; ===============================================================================================================================
Func _RandomUnique($iCount, $nMin, $nMax, $iInt = 0, $nSeed = Default)
    ; error checking
    Select
        ; $iCount is too small
        Case ($iCount < 1)
            Return SetError(1, 0, 0)
        ; $iCount is too large
        Case ($iCount > 10^6-1)
            Return SetError(2, 0, 0)
        ; $nMin and $nMax cannot be equal
        Case ($nMin = $nMax)
            Return SetError(3, 0, 0)
        ; $nMin cannot be larger than $nMax
        Case ($nMin > $nMax)
            Return SetError(4, 0, 0)
        ; $nMin or $nMax exceeds limit
        Case ( ($nMin < -2^31) Or ($nMax > 2^31-1) )
            Return SetError(5, 0, 0)
    EndSelect
    ; user specific seed
    If IsNumber($nSeed) Then
        ; $nSeed exceeds limit
        If (($nSeed < -2^31) Or ($nSeed > 2^31-1) ) Then Return SetError(6, 0, 0)
        SRandom($nSeed)
    EndIf
    ; $iCount is equal too or exceeds maximum possible unique values
    Local $iCountInval = 0
    If ($iInt) Then
        ; positive
        If ($nMin >= 0) Then
            If ($iCount > ($nMax-$nMin)+1) Then
                $iCountInval = 1
            ElseIf ($iCount = ($nMax-$nMin)+1) Then
                $iCountInval = 3
            EndIf
        ; negative to positive
        Else
            If ($iCount > ($nMax + Abs($nMin)+1)) Then
                $iCountInval = 2
            ElseIf ($iCount = ($nMax + Abs($nMin)+1)) Then
                $iCountInval = 3
            EndIf
        EndIf
    EndIf
    ; courtesy
    If ($iInt And $iCount = 1) Then
        Local $aArray[2] = [1, Random($nMin, $nMax, $iInt)]
    ; $iCount is too large so we will generate as much we can from $nMin to $nMax values
    ElseIf $iCountInval Then
        If $iCountInval = 1 Then
            $iCount = Int($nMax - $nMin)+1
        ElseIf $iCountInval = 2 Then
            $iCount = Int($nMax + Abs($nMin))+1
        EndIf
        ; $iCount is equal to total unique numbers
        If $iCountInval = 3 Then $iCountInval = 0
        Local $aTmp, $iA, $iNumber = $nMin, $aArray[$iCount + 1] = [$iCount]
        ; add our numbers sequentially (from $iMin to $iMax)
        For $i = 1 To $aArray[0]
            $aArray[$i] = $iNumber
            $iNumber += 1
        Next
        ; swap every x index value with a random index value
        For $i = 1 To $aArray[0]
            $iA = Random($i, $aArray[0], 1)
            If $i = $iA Then ContinueLoop
            If $iA = 0 Then $iA = $aArray[0]
            $aTmp = $aArray[$i]
            $aArray[$i] = $aArray[$iA]
            $aArray[$iA] = $aTmp
        Next
    Else
    ; everything else is ok, generate unique numbers
        Local $nRnd, $iStep = 0, $aArray[$iCount + 1] = [$iCount]
        While ($iStep <= $iCount-1)
            $nRnd = Random($nMin, $nMax, $iInt)
            ; check if the number already exist
            If IsDeclared($nRnd) <> -1 Then
                $iStep += 1
                $aArray[$iStep] = $nRnd
                ; store our numbers in a local variable
                Assign($nRnd, '', 1)
            EndIf
        WEnd
    EndIf
    Return SetError(0, Number($iCountInval > 0), $aArray)
EndFunc

Changelog:

v1.1 - 2011/11/24
Set $nCount limit to 1,000,000 (avoid maximum array count error)
Fixed possible conflict with global variables
Updated shuffle routine to be more effective [reported by martin]
Updated unique number comparison routine [reported by martin]
Return values were changed

v1.0 - 2011/11/22
Initial release

Edited November 24, 2011 by money

martin · November 23, 2011

This bit

While ($iStep <= $iCount-1)
            $nRnd = Random($nMin, $nMax, $iInt)
            ; the values are stored as a local variable
            ; this is considerably faster than storing and checking from an array
            $sAsn = Hex(Binary($nRnd))
            If IsDeclared($sAsn) = 0 Then
                $iStep += 1
                $aArray[$iStep] = $nRnd
                Assign($sAsn, '', 1)
            EndIf
        WEnd

seems like a good idea, though I don't see the purposes of

Assign($sAsn, '', 1)

which I suppose just slows things down.

If that method works then why bother with the other approach?

I think that his loop

For $i = 1 To $aArray[0]
            $iA = Random($i, $aArray[0], 1)
            $iB = Random($i, $aArray[0], 1)
            $aTmp = $aArray[$iA]
            $aArray[$iA] = $aArray[$iB]
            $aArray[$iB] = $aTmp
        Next

only needs to have

For $i = 1 To $aArray[0]-1

etc

But to shuffle well you can't assume that you will get a good shuffle of n items by choosing n random pairs to be swapped. Some numbers will repeat which could negate one swap, and you might sometimes swap position x with x ie do nothing. I bet that if you applied the loop to an array of numbers 1 to 100 say then after one such shuffle a lot of numbers would still be in the same original position so it might be better to repeat that for loop a couple of times.

Edited November 23, 2011 by martin

JohnOne · November 23, 2011

This bit
While ($iStep <= $iCount-1)
            $nRnd = Random($nMin, $nMax, $iInt)
            ; the values are stored as a local variable
            ; this is considerably faster than storing and checking from an array
            $sAsn = Hex(Binary($nRnd))
            If IsDeclared($sAsn) = 0 Then
                $iStep += 1
                $aArray[$iStep] = $nRnd
                Assign($sAsn, '', 1)
            EndIf
        WEnd
seems like a good idea, though I don't see the purposes of

Assign($sAsn, '', 1)

which I suppose just slows things down.

If that method works then why bother with th eother approach?

I think that his loop
[autoit]
For $i = 1 To $aArray[0]
$iA = Random($i, $aArray[0], 1)
$iB = Random($i, $aArray[0], 1)
$aTmp = $aArray[$iA]
$aArray[$iA] = $aArray[$iB]
$aArray[$iB] = $aTmp
Next
[/autpit]

Your section
only needs to be
For $i = 1 To $aArray[0]-1
etc
But to shuffle well you can't assume that you will get a good shuffle of n items by choosing n random pairs to be swapped. Some numbers will repeat which could negate one swap, and you might sometimes swap position x with x ie do nothing. I bet that if you applied the loop to an array of numbers 1 to 100 say then after one such shuffle a lot of numbers would still be in the same original position so it might be better to repeat that for loop a couple of times.

I think I've seen this discussion here before, I cannot remember it fully, but It was mostly agreed that with

a human shuffle, for example a pack of cards, there may well be cards in the same position there were before it.

martin · November 24, 2011

Yes, I agree. I tried a single shuffle as in the original post with 100 numbers. Every time I ran the shuffle there were around 13 numbers which hadn't been moved. In 100 numbers the chance of a number being in it's own number position is 1 in 100 so 13 is not a good shuffle if it is intended to be a random mix.

Shuffling 3 times gave me from 0 to 3 in the few times I tried.

money · November 24, 2011

Updated.

@Martin.

Initially shuffle was an after thought, actually copy/paste from an older script that I forgot to update.

You're right though, it shuffled terribly. I changed it, and now results are much better.

Edited November 24, 2011 by money

MvGulik · November 25, 2011

Features:
Fast

I Always wonder about claims without relevant context.

Even a tortoise can be labeled as fast ... compared to the ground its walking on.

Search around the forum a bit to find potential upgrades to you code. ... If speed is one of your needs.

---

Think this is the topic that is revered to by JohnOne.

Edited November 25, 2011 by MvGulik

AZJIO · November 28, 2011

money

99999 out of 100000 for 1 second

Need to invert if $iCount > ($nMax-$nMin) / 2

#include <Array.au3>

$timer = TimerInit()
$aR = _RandomUnique(0, 100000, 99999)
_ArrayDisplay($aR, 'Time : ' & Round(TimerDiff($timer) / 1000, 2) & ' sec', 100)

Func _RandomUnique($Min = 0, $Max = 1, $Count = 1)
    Local $i, $k, $ts, $te, $tmp, $tmpNew, $iStep = 0, $nRnd, $iStepErr = 0

    $k = $Max - $Min + 1
    If $Min >= $Max Then Return SetError(1, 0, '')
    If $k < $Count Then Return SetError(2, 0, '')
    If $Count = 1 Then
        Local $aUnique[2] = [1, Random($Min, $Max, 1)]
        Return $aUnique
    EndIf

    Local $aStr[$k]
    For $i = 0 To $k - 1
        $aStr[$i] = $i + $Min
    Next

    If $Count > $k / 2 Then

        Local $iCountExp = $k - $Count
        Assign('', '', 1)
        While $iStep < $iCountExp
            $nRnd = Random(0, $k - 1, 1)
            If IsDeclared($aStr[$nRnd] & '') <> -1 Then
                $iStep += 1
                $aStr[$nRnd] = ''
                Assign($aStr[$nRnd] & '', '', 1)
            Else
                ; v===================================v
                $iStepErr += 1
                If $iStepErr > $k / 4 Then
                    $d = 0
                    For $i = 0 To $k - 1
                        If $aStr[$i] Then
                            $aStr[$d] = $aStr[$i]
                            $d += 1
                        EndIf
                    Next
                    If $d > 0 Then
                        ReDim $aStr[$d]
                        $k = $d
                        $iStepErr = 0
                    Else
                        ExitLoop
                    EndIf
                EndIf
                ; ^===================================^
            EndIf
        WEnd
        $d = 0
        Local $aUnique[$k]
        For $i = 0 To $k - 1
            If StringLen($aStr[$i]) Then
                $d += 1
                $aUnique[$d] = $aStr[$i]
            EndIf
        Next
        ReDim $aUnique[$d + 1]
        $aUnique[0] = $d

        ; swap
        For $i = 1 To $aUnique[0]
            $iR = Random($i, $aUnique[0], 1)
            If $i = $iR Then ContinueLoop
            If $iR = 0 Then $iR = $aUnique[0]
            $aTmp = $aUnique[$i]
            $aUnique[$i] = $aUnique[$iR]
            $aUnique[$iR] = $aTmp
        Next

    Else

        Local $aUnique[$Count + 1] = [$Count]
        Assign('', '', 1)
        While $iStep < $Count
            $nRnd = Random(0, $k - 1, 1)
            If IsDeclared($aStr[$nRnd] & '') <> -1 Then
                $iStep += 1
                $aUnique[$iStep] = $aStr[$nRnd]
                $aStr[$nRnd] = ''
                Assign($aStr[$nRnd] & '', '', 1)
            Else
                ; v===================================v
                $iStepErr += 1
                If $iStepErr > $k / 4 Then
                    $d = 0
                    For $i = 0 To $k - 1
                        If StringLen($aStr[$i]) Then
                            $aStr[$d] = $aStr[$i]
                            $d += 1
                        EndIf
                    Next
                    If $d > 0 Then
                        ReDim $aStr[$d]
                        $k = $d
                        $iStepErr = 0
                    Else
                        ExitLoop
                    EndIf
                EndIf
                ; ^===================================^
            EndIf
        WEnd
    EndIf

    Return $aUnique
EndFunc   ;==>_RandomUnique

Edited November 28, 2011 by AZJIO

netegg · December 24, 2011

money

99999 out of 100000 for 1 second

Need to invert if $iCount > ($nMax-$nMin) / 2

#include <Array.au3>

$timer = TimerInit()
$aR = _RandomUnique(0, 100000, 99999)
_ArrayDisplay($aR, 'Time : ' & Round(TimerDiff($timer) / 1000, 2) & ' sec', 100)

Func _RandomUnique($Min = 0, $Max = 1, $Count = 1)
    Local $i, $k, $ts, $te, $tmp, $tmpNew, $iStep = 0, $nRnd, $iStepErr = 0

    $k = $Max - $Min + 1
    If $Min >= $Max Then Return SetError(1, 0, '')
    If $k < $Count Then Return SetError(2, 0, '')
    If $Count = 1 Then
        Local $aUnique[2] = [1, Random($Min, $Max, 1)]
        Return $aUnique
    EndIf

    Local $aStr[$k]
    For $i = 0 To $k - 1
        $aStr[$i] = $i + $Min
    Next

    If $Count > $k / 2 Then

        Local $iCountExp = $k - $Count
        Assign('', '', 1)
        While $iStep < $iCountExp
            $nRnd = Random(0, $k - 1, 1)
            If IsDeclared($aStr[$nRnd] & '') <> -1 Then
                $iStep += 1
                $aStr[$nRnd] = ''
                Assign($aStr[$nRnd] & '', '', 1)
            Else
                ; v===================================v
                $iStepErr += 1
                If $iStepErr > $k / 4 Then
                    $d = 0
                    For $i = 0 To $k - 1
                        If $aStr[$i] Then
                            $aStr[$d] = $aStr[$i]
                            $d += 1
                        EndIf
                    Next
                    If $d > 0 Then
                        ReDim $aStr[$d]
                        $k = $d
                        $iStepErr = 0
                    Else
                        ExitLoop
                    EndIf
                EndIf
                ; ^===================================^
            EndIf
        WEnd
        $d = 0
        Local $aUnique[$k]
        For $i = 0 To $k - 1
            If StringLen($aStr[$i]) Then
                $d += 1
                $aUnique[$d] = $aStr[$i]
            EndIf
        Next
        ReDim $aUnique[$d + 1]
        $aUnique[0] = $d

        ; swap
        For $i = 1 To $aUnique[0]
            $iR = Random($i, $aUnique[0], 1)
            If $i = $iR Then ContinueLoop
            If $iR = 0 Then $iR = $aUnique[0]
            $aTmp = $aUnique[$i]
            $aUnique[$i] = $aUnique[$iR]
            $aUnique[$iR] = $aTmp
        Next

    Else

        Local $aUnique[$Count + 1] = [$Count]
        Assign('', '', 1)
        While $iStep < $Count
            $nRnd = Random(0, $k - 1, 1)
            If IsDeclared($aStr[$nRnd] & '') <> -1 Then
                $iStep += 1
                $aUnique[$iStep] = $aStr[$nRnd]
                $aStr[$nRnd] = ''
                Assign($aStr[$nRnd] & '', '', 1)
            Else
                ; v===================================v
                $iStepErr += 1
                If $iStepErr > $k / 4 Then
                    $d = 0
                    For $i = 0 To $k - 1
                        If StringLen($aStr[$i]) Then
                            $aStr[$d] = $aStr[$i]
                            $d += 1
                        EndIf
                    Next
                    If $d > 0 Then
                        ReDim $aStr[$d]
                        $k = $d
                        $iStepErr = 0
                    Else
                        ExitLoop
                    EndIf
                EndIf
                ; ^===================================^
            EndIf
        WEnd
    EndIf

    Return $aUnique
EndFunc   ;==>_RandomUnique

can this support decimal?

Sign In

_RandomUnique - Generate unique random numbers [updated 2011-11-24]

Recommended Posts

money

Link to comment

Share on other sites

martin

Link to comment

Share on other sites

JohnOne

Link to comment

Share on other sites

martin

Link to comment

Share on other sites

money

Link to comment

Share on other sites

MvGulik

Link to comment

Share on other sites

AZJIO

Link to comment

Share on other sites

netegg

Link to comment

Share on other sites

Create an account or sign in to comment

Create an account

Sign in

Recently Browsing 0 members

Browse

AutoIt Resources

Release

Beta