Another Unique Random Number Generator

[kylomas]

This function will generate unique random numbers, int or float, in any range, e.g. -5 to +5. The function and several examples are included.

This function can generate 100000 numbers between 1 and 100000 (all possible numbers) in less than 15 seconds.

Not sure if this is at all usefull, just don't feel like thinking today so I'm goofing around with stuff like this.

expandcollapse popup

;
; generate unique random numbers
;

#include <array.au3> ; used for _arraydisplay

; error table - this is just my preferred method for developement, use switch...case on @error if you prefer

local   $errtbl[6]
        $errtbl[1] = ' Minimum value not numeric'
        $errtbl[2] = ' Maximum value not numeric'
        $errtbl[3] = ' Number of unique values to gen not numeric'
        $errtbl[4] = ' Number of unique random values to generate cannot be greater than the range of available numbers'
        $errtbl[5] = ' Random function failed'

;------------------------------------------------------------------------------------
; example scripts
;------------------------------------------------------------------------------------

; generate 1000 floating point random numbers between .1 and .2 - no debugging info
local $rnum = _GenUniqueNumbers(.1,.2,1000,false)
if @error then
    ConsoleWrite('! ERROR = ' & $errtbl[@error] & @LF)
else
    _arraydisplay($rnum)
endif

; generate 10 integers between -5 and 5 - show timings and accept/reject messages
local $rnum = _GenUniqueNumbers(-5,5,11,-1,'all')
if @error then
    ConsoleWrite('! ERROR = ' & $errtbl[@error] & @LF)
else
    _arraydisplay($rnum)
endif

; generate 10 integers between -9 and 0 - generate range error
local $rnum = _GenUniqueNumbers(-9,0,11)
if @error then
    ConsoleWrite('! ERROR = ' & $errtbl[@error] & @LF)
else
    _arraydisplay($rnum)
endif

; generate 1000 integers between 1 and 3000
local $rnum = _GenUniqueNumbers(1,3000,1000)
if @error then
    ConsoleWrite('! ERROR = ' & $errtbl[@error] & @LF)
else
    _arraydisplay($rnum)
endif

; generate 1001 integers between 0 and 1000 - show timing - this example demonstrates worst possible scenario in terms of overhead
local $rnum = _GenUniqueNumbers(0,1000,1001,default,'time')
if @error then
    ConsoleWrite('! ERROR = ' & $errtbl[@error] & @LF)
else
    _arraydisplay($rnum)
endif

; generate 100000 integers between 1 and 100000 - show timing - just fucking around to see how long it takes
local $rnum = _GenUniqueNumbers(1,100000,100000,default,'time')
if @error then
    ConsoleWrite('! ERROR = ' & $errtbl[@error] & @LF)
else
    _arraydisplay($rnum)
endif

;=========================================================================================================================================================
;
; Description:      : Generate unique random numbers
; Parameter(s):     : $min   - minimum random number
;                   : $max   - maximum random number
;                   : $num   - #of unique values to generate
;                   : $int   - true  = generate integers
;                              false = generate floating point numbers
;                              if this is true then $num cannot be greater than $max-$min (cannot generate more unique values than all possible candidates)
;                   : $debug - 'time' = issue timings to console
;                              'all'  = issue timings and number accept/reject messages to console
; Requirement:      : none
; Return Value(s):  : @error = 1 - minimum value not numeric
;                              2 - maximum value not numeric
;                              3 - number of unique values to gen not numeric
;                              4 - number to generate is greater than the range of available numbers (only set if $int = true)
; User CallTip:     : none
; Author(s):        : kylomas
; Note(s):          :
;
;===========================================================================================================================================================
func _GenUniqueNumbers($min, $max, $num, $int = true, $debug = '')

    if $debug = 'time' or $debug = 'all' then local $st = timerinit()

    if not IsNumber($min)           then return seterror(1)
    if not IsNumber($max)           then return seterror(2)
    if not IsNumber($num)           then return seterror(3)

    if $int= -1 or $int = default then $int = true

    if $int and (($max-$min)+1 < $num)  then return seterror(4)

    local $a1[$num], $tnum

    for $1 = 0 to $num - 1
        $tnum = random($min, $max, $int)
        if $tnum = 0 and @error = 1 then seterror(5)
        while IsDeclared('s' & $tnum)
            if $debug = 'all' then ConsoleWrite('!> rejecting ' & $tnum & @LF)
            $tnum = random($min, $max, $int)
            if $tnum = 0 and @error = 1 then seterror(5)
        wend
        if $debug = 'all' then ConsoleWrite('-> accepting ' & $tnum & @LF)
        assign('s' & $tnum,'')
        $a1[$1] = $tnum
    Next

    if $debug = 'time' or $debug = 'all' then consolewrite('+> Time to gen ' & $num & ' numbers = ' & round(timerdiff($st)/1000,4) & @lf)

    return $a1

endfunc

kylomas

[Myicq]

Hey,

I am working on a very similar project, only with possibility to add masks to randomness (like "ANNN" for alpha, num, num, num.).

I like your approach with arrays to check for duplicates. I use a memory based SQLite.. it would be interesting to know which of the two is faster ?

Should publish my code some time...

as an idea, you should allow $debug="count", so you can return the number of actual unique random values. Ex: make 100 random numbers between 1 and 9 should return exactly 9 random values (and 91 duplicates). Obviously that's easy. But do you actually get 10.000 if you use interval 1..100.000, since you have 10% chance of duplicates ?

Will keep watching this. Good start.

[kylomas]

Myicq,

Ex: make 100 random numbers between 1 and 9 should return exactly 9 random values (and 91 duplicates).

The code does not allow for this and I am not sure what the value of this would be in this context (unique random numbers).

as an idea, you should allow $debug="count", so you can return the number of actual unique random values

All returned values are unique, not sure what you are getting at.

it would be interesting to know which of the two is faster ?

The worst possible scenario is generating all possible numbers within a range, e.g. 100,000 integers between 1 and 100,000. This runs in under 15 seconds on my machine. It might be interesting to plot the time scale for generation. Obviously most of the time is spent toward the end.

Good start.

Thanks, but I have no further plans for this. AS I said in the OP, I was just goofing around. The idea came to me when I wanted to see how fast I could shuffle a deck of cards and what the incidence of repeats (cards not shuffled) would be, like this

expandcollapse popup

#include <array.au3>
#include <string.au3>

local $old_deck, $new_deck = shuffle(), $cnt=0, $tcnt=0

for $1 = 1 to 1000
    local $st = timerinit()
    $new_deck = shuffle()
    for $2 = 0 to ubound($old_deck) - 1
        if $old_deck[$2] = $new_deck[$2] then $cnt += 1
    next
    _DBG_ConOut('Time to shuffle',round(timerdiff($st)/1000,4),50,'.','red')
    _DBG_ConOut('  Cards not moved',$cnt,50,'.','red')
    $old_deck = $new_deck
    $tcnt += $cnt
    $cnt = 0
next

_DBG_ConOut('Total Cards not moved in ' & $1-1 & ' shuffles',$tcnt,50,'.','red')

func shuffle()

    local $deck[52],$card
    $card = random(1,52,1)

    for $1 = 0 to 51

        while isdeclared('s' & $card)
                $card = random(1,52,1)
        WEnd
        assign('s' & $card,'')
        $deck[$1] = $card

    Next

    return $deck

endfunc

; #FUNCTION# ===========================================================================================================
; Name ................:    _DBG_ConOut
; Description .........:    output formatted output to the console
; Syntax ..............:    _DBG_ConOut($String1, $string2='', $Col1_Width=50, $Fill_Char=' ', $Color='Black)
; Parameters ..........:    $String1        - 1ST string to appear in console output
;                           $String2        - 2ND string to appear in console output
;                           $Col1_Width     - 1ST string column width.  This will be left filled with
;                                             $Fill_Char if > than $String1 length
;                           $Fill_Char      - one, or more chars to use to left pad between $String1 and $Sting2
;                           $Color          - Console output color.  Valid colors are black, red, blue, green and yellow
;
; Example..............;    con_out('Time to run',round(timerdiff($st)/1000,3),20,'.','red') output to the console
;                           Time to run..........0.003 (in red)
;
; ======================================================================================================================

func _DBG_ConOut($String1,$String2='',$Col1_Width=50,$Fill_Char=' ',$Color='Black')
    switch stringlower($Color)
        case 'black'
            $Color = ' '
        case 'blue'
            $Color = '>'
        case 'yellow'
            $Color = '-'
        case 'red'
            $Color = '!'
        case 'green'
            $Color = '+'
        case Else
            $Color = ' '
    EndSwitch
    consolewrite($Color & ' ' & $String1 & _stringrepeat($Fill_Char,$Col1_Width - stringlen($String1)) & $String2 & @lf)
endfunc

It would be interesting to see the comparison between this technique and SQLite.

kylomas

[wraithdu]

I've been thinking this, but decided not to post until your last comment... breeding in uniqueness breeds out randomness. Truly random numbers can (and will) have repeats, especially given a small enough range.

It sounds like what you're really after is a shuffling algorithm, and a good one already exists. Here's my implementation of the Fisher-Yates shuffle.

expandcollapse popup

#include-once

; #FUNCTION# ====================================================================================================
; Name...........: _ArrayShuffle
; Description....: Shuffle elements of a 1D or 2D array
; Syntax.........: _ArrayShuffle(ByRef $aArray)
; Parameters.....: $aArray - [ByRef] Input 1D or 2D array
;
; Return values..: Success - 1
;                  Failure - 0 and sets @error:
;                          | 1 - 1st dimension has less than 2 elements, nothing to shuffle
;                          | 2 - More than 2 dimensions
; Author.........: Erik Pilsits
; Modified.......:
; Remarks........: Implementation of the Fisher-Yates algorithm.
; Related........:
; Link...........: http://en.wikipedia.org/wiki/Fisher–Yates_shuffle
; Example........:
; ===============================================================================================================
Func _ArrayShuffle(ByRef $aArray)
    Local $u = UBound($aArray)
    If $u < 2 Then Return SetError(1, 0, 0)
    Local $j, $temp
    Switch UBound($aArray, 0)
        Case 1
            For $i = $u - 1 To 1 Step -1
                $j = Random(0, $i, 1)
                $temp = $aArray[$i]
                $aArray[$i] = $aArray[$j]
                $aArray[$j] = $temp
            Next
        Case 2
            Local $u2 = UBound($aArray, 2) - 1
            For $i = $u - 1 To 1 Step -1
                $j = Random(0, $i, 1)
                For $k = 0 To $u2
                    $temp = $aArray[$i][$k]
                    $aArray[$i][$k] = $aArray[$j][$k]
                    $aArray[$j][$k] = $temp
                Next
            Next
        Case Else
            Return SetError(2, 0, 0)
    EndSwitch
    Return 1
EndFunc

Edited December 6, 2012 by wraithdu

[kylomas]

wraithdu - Thanks, interesting reading

edit - recently saw a cartoon about randomness but can't figure out how to post a .gif file, sorry!

Edited December 6, 2012 by kylomas