How Can I Random A Non-Repeating Number?

01-19-2008, 09:11 PM	#1
Brash	I am trying to figure out a way to Random 650 different random numbers so that no two of any of the numbers randomized are equal to eachother.. how is this possible? I've been working on this for hours and it's driving me nuts!

01-19-2008, 09:25 PM	#2
xombie	You would have to compare each randomly generated number with all of the numbers before it. I'm not sure if this is the only way, but thats what comes to mind.

01-19-2008, 09:29 PM	#3
Centreri	That seems like the best method. It might also be possible to exclude the numbers already taken while taking them, so that you take a random number from 1-5, 7-9, 11-95, 97, etc, with 650 different sections, but that is in no way an ideal way. I'd just compare 'em.

01-19-2008, 09:30 PM

Silvenon

JASS:

local integer array I
local integer i1 = 0
local integer i2
loop
    exitwhen i1 == 650
        set I[i1] = GetRandomInt(<low bound>, <high bound>)
        set i2 = i1
        loop
            exitwhen i2 == 0
            if i2 != i1 then
            loop
                exitwhen I[i1] != I[i2]
                set I[i] = GetRandomInt(<low bound>, <high bound>)
            endloop
            set i2 = i2 - 1
        endloop
    set i1 = i1 + 1
endloop

I'm not sure if this works! I haven't tested it, I just wrote it really quick.

01-19-2008, 09:42 PM

Brash

Quote:

Originally Posted by xombie

You would have to compare each randomly generated number with all of the numbers before it.

but how? that's the part that's driving me nuts. wouldn't that require many loops within loops within loops and an infinite amount of if/than/elses to compare?

01-19-2008, 09:46 PM

Ammorth

Way better method. Give me a sec to post it.

JASS:

function RandomArray takes nothing returns nothing
    local integer i = 1
    local integer n
    local integer max = 650
    local integer temp
    // Fill the array with the possible numbers (1 to 650)
    loop
        exitwhen i > max
        set Array[i] = i
        set i = i + 1
    endloop
    set i = 1
    // Switch each number with a random possible number
    loop
        exitwhen i > max
        set n = GetRandomInteger(1, max)
        set temp = Array[n]
        set Array[n] = Array[i]
        set Array[i] = temp
        set i = i + 1
    endloop
    // Array is now random
endfunction

01-20-2008, 12:59 AM	#7
Alevice	Pools would be better, I suppose

01-20-2008, 02:25 AM	#8
chobibo	ammoroth's script does it perfectly, no need for pools.

01-20-2008, 05:47 AM	#9
Brash	hm, i can understand parts of that script but i'm not a jasser, i use gui. =P anyone explain this in gui terms? or can i plug that script in as it is and use the Array [] in another non-script trig for referencing those numbers it makes? and how would i call on it if i could? thanks for the script tho

01-20-2008, 06:59 AM

#10

Ammorth

first, change the name "Array" to "udg_NameOfVaraible" where NameOfVariable is... the name of the variable. ("udg_" stands for a "user-defined-global" or in lame-man terms, a GUI variable.)

make sure to copy this to your map script section.

You can then call it by using custom script.

Trigger:

Custom Script: call RandomArray()

You can convert this to GUI, if you want. Its not entirely difficult if you understand the concept.

01-20-2008, 07:25 AM

#11

Brash

hm, i tried pasting that into my map script and when i saved i got an error. doesn't seem to like that code.

i'm using standard war3 editor

anyways, i tried your advice by attempting to convert it and i'm coming out with my Array = 0s

Here is what i got, as close to looking like what you have as i could for gui, even var names the same:

Trigger:

test

Events

Player - Player 1 (Red) types a chat message containing test as A substring

Conditions

Actions

Set _i = 1

Set _n = 0

Set _Max = 650

Set _Temp = 0

-------- ------------------- --------

For each (Integer A) from _i to _Max, do (Actions)

Loop - Actions

Set _Array[_i] = _i

Set _i = 1

For each (Integer A) from _i to _Max, do (Actions)

Loop - Actions

Set _n = (Random integer number between 1 and _Max)

Set _Temp = _Array[_n]

Set _Array[_n] = _Array[_i]

Set _Array[_i] = _Temp

-------- test numbers.. do they equal something other than 0 --------

For each (Integer A) from 1 to 650, do (Actions)

Loop - Actions

Game - Display to (All players) for 5.00 seconds the text: (String(_Array[(Integer A)]))

Update: I modified the above by having _i +1 itself like in your script... which i didnt include in the above trig because i thought the loop was already doing that as it looped through each integer A

New trig with slight mod:

Trigger:

test

Events

Player - Player 1 (Red) types a chat message containing test as A substring

Conditions

Actions

Set _i = 1

Set _n = 0

Set _Max = 650

Set _Temp = 0

-------- ------------------- --------

For each (Integer A) from _i to _Max, do (Actions)

Loop - Actions

Set _Array[(Integer A)] = _i

Set _i = (_i + 1)

Set _i = 1

For each (Integer A) from _i to _Max, do (Actions)

Loop - Actions

Set _n = (Random integer number between 1 and _Max)

Set _Temp = _Array[_n]

Set _Array[_n] = _Array[_i]

Set _Array[_i] = _Temp

Set _i = (_i + 1)

-------- displays the number for feedback --------

For each (Integer A) from 1 to 650, do (Actions)

Loop - Actions

Game - Display to (All players) for 5.00 seconds the text: (String(_Array[(Integer A)]))

This version seems to be giving me random numbers but i'm still testing to see if any are duplicates using that text

What do you think? are either one of these correct?

Edit> it seems good! thanks guys. Especially Ammorth for the doing the coding.
Can't believe i made script into a look-a-like gui. looks kinda weird, but it seems to work!

01-20-2008, 09:00 PM	#12
Ammorth	You can remove all references of i and change them to Integer A. It should up performance a bit. edit: or better yet, use "For each integer (variable)" and specify i as the variable. It will the increase i for you, but you will have to change all instances of Integer A to i. I think thats the best optimization for GUI.

01-21-2008, 09:54 PM	#13
PipeDream	Ammorth, to get uniform sampling you want GetRandomInt(i,n). The algorithm is called Fisher Yates IIRC, look it up for explanation.

01-22-2008, 01:09 AM

#14

Ammorth

Quote:

Originally Posted by PipeDream

Ammorth, to get uniform sampling you want GetRandomInt(i,n). The algorithm is called Fisher Yates IIRC, look it up for explanation.

Interesting! I never thought about that.

I found this to be rather interesting aswell:

Quote:

Originally Posted by Wikipedia

For example, the built-in pseudorandom number generator provided by many programming languages and/or libraries may often have only 32 bits of internal state, which means it can only produce 2^32 different sequences of numbers. If such a generator is used to shuffle a deck of 52 playing cards, it can only ever produce a vanishingly small fraction of the 52! ≈ 2^225.6 possible permutations. Thus, it's impossible for a generator with less than 226 bits of internal state to produce all the possible permutations of a 52-card deck, and for a (reasonably) unbiased shuffle, the generator must have at least about 250 bits of state.

Source: http://en.wikipedia.org/wiki/Knuth_shuffle