Fast constant size overhead permutation generator

[LeP]

Fast constant size overhead permutation generator.
You can use this whenever you need numbers between 0 and x in a random order.

Demo

function demo takes nothing returns nothing
    local integer i
 
    set i = 0
    loop
    exitwhen i == 5
        call BJDebugMsg(I2S(i) +": "+ I2S(Permutation_index(5, 1337, i)))
        set i = i +1
    endloop
 
    set i = 0
    loop
    exitwhen i == 5
        call BJDebugMsg(I2S(i) +": "+ I2S(Permutation_index(5, 42069, i)))
        set i = i +1
    endloop
 
endfunction

Will print something like this

0: 4
1: 3
2: 2
3: 0
4: 1

0: 4
1: 0
2: 3
3: 2
4: 1

How does it work

We use a bijective function r : integer -> integer where integer is our 32bit jass integer type. We want a good pseudo-random function for r. Such functions are rather easy to construct. Now to get from [0, 2^32] into our desired range [0, hi) we simply apply r until it returns a value in range [0, hi). Proving that this terminates is left as an excersize to the reader (or just ask and i will provide a proof)
To speed things up we truncate the value to [0, 2^n] for the smallest n such that hi <= 2^n.

Looking at [2] one can see such a function r which could be adopted to jass easily. But for speeds sake we use a simpler pseudo-random function.

Code

library Permutation

private function nextPowerOfTwo takes integer x returns integer
    local integer p = 1
    loop
    exitwhen x <= p
        set p = 2*p
    endloop
    return p
endfunction

// any bijective function from integer to integer
private function R takes integer x, integer seed returns integer
    set x = x * 0xe170893d
    set x = x + 0x0929eb3f
    set x = x * 0x6935fa69
    set x = x - seed
    set x = x * 0xc860a3df
    return x
endfunction

/**
Returns the i'th index of the permutated series [0, hi-1].

@param hi The upper bound of this permutation
@param seed Random seed for the permutation
@param i Index of the permutation. Should be in range [0, hi-1]

pure
*/
public function index takes integer hi, integer seed, integer i returns integer
    local integer w = nextPowerOfTwo(hi)
    loop
        set i = R(i, seed)
    
        // this step isn't neccessary but it should speed up the search
        // Also jasshelper doesnt like %. Otherwise we could use i % w
        set i = BlzBitAnd(i, w-1)
    exitwhen i < hi
    endloop
    // again thanks to jasshelper we can't use %
    return ModuloInteger(i+seed, hi)
endfunction

endlibrary

Sources

[1]: https://web.cs.ucdavis.edu/~rogaway/papers/subset.pdf
[2]: https://graphics.pixar.com/library/MultiJitteredSampling/paper.pdf

 

[Bribe]

I find it more user-friendly to just pop a random array index where needed via GetRandomInt(0, array_Size -1), and then re-build the array if you need to preserve it.

 

[LeP]

I find it more user-friendly to just pop a random array index where needed via GetRandomInt(0, array_Size -1), and then re-build the array if you need to preserve it.

You can provide the same api either way. And it all depends on the use case. Still this is constant size overhead while an array has linear size overhead (+ rebuilding take linear time).

 

[Bribe]

I'm taking a deeper dive into the code now and a couple things stood out to me:

1)
The user needing to pass a seed in order to utilize the system's behavior is necessary in order to maintain the integrity of each respective grouping, also the user needing to use a loop to extract the random sequence, might make the API overhead a bit high.

I propose doing some optional wrapper functions in your resource that automates a bit of that redundant user-side stuff. Ie. something that returns a Table.

2)
Does % actually work in vanilla JASS as a mod character??

 

[LeP]

I'm taking a deeper dive into the code now and a couple things stood out to me:

1)
The user needing to pass a seed in order to utilize the system's behavior is necessary in order to maintain the integrity of each respective grouping, also the user needing to use a loop to extract the random sequence, might make the API overhead a bit high.

I propose doing some optional wrapper functions in your resource that automates a bit of that redundant user-side stuff. Ie. something that returns a Table.

Having a completely pure API is an upside. You can use any index in any order (or multiple times). I don't consider wrapping a mere integer seed into some stateful object an improvement.
But writing some library which provides random seed generation/array syntax/iterator api is trivial.
Another improvement would be allowing any range [lo, hi] instead of [0, hi-1].
I don't intend to post this as a resource though. One of the reasons i posted this is its mathematical beauty.

Also this can be trivially converted to pure jass: just remove library/public/private.

2)
Does % actually work in vanilla JASS as a mod character??

Yes, since 1.29 or so. In fact using % is preferable over ModuloInteger since ModuloInteger is bugged for negative second argument.

 

[Prometheus3375]

is bugged for negative second argument.

Can you explain, why?

 

[LeP]

Can you explain, why?

While ModuloInteger doesn't make any hard promises we have some expectations for it.
The normal law for modulus is (x/y) * y + (x % y) == x, or x % y in [0 .. y-1].
On the other hand ModuloInteger(-7, -3) == -4 where -4 not in [-2 .. 0].
In fact (-7/-3)*-3 + ModuloInteger(-7, -3) == -10 != -3

 

[Prometheus3375]

Thanks, I realised the problem before reading you answer.
Problem occurs when both args are negative. It checks whether modulus is negative, but did not check whether seconds arg is negative, so it adds -3 to -1, -4 is obtained.
It can be easily fixed by taking absolute value of divisor.

function ModuloInteger takes integer dividend, integer divisor returns integer
    local integer modulus = dividend - (dividend / divisor) * divisor

    // If the dividend was negative, the above modulus calculation will
    // be negative, but within (-divisor..0).  We can add (divisor) to
    // shift this result into the desired range of (0..divisor).
    if (modulus < 0) then
        set modulus = modulus + IAbsBJ(divisor)
    endif

    return modulus
endfunction

Or shorter.

function ModuloN takes integer a, integer n returns integer
    return a - a / n * n
endfunction

function ModuloNPos takes integer a, integer n returns integer
    return ModuloN(IAbsBJ(a), n)
endfunction

First function must be used when you are sure that a is positive.

The universal function.

function ModuloN takes integer a, integer n returns integer
    set a = IAbsBJ(a)
    return a - a / n * n
endfunction

 

[LeP]

Thanks, I realised the problem before reading you answer.
Problem occurs when both args are negative. It checks whether modulus is negative, but did not check whether seconds arg is negative, so it adds -3 to -1, -4 is obtained.
It can be easily fixed by taking absolute value of divisor.

function ModuloInteger takes integer dividend, integer divisor returns integer
    local integer modulus = dividend - (dividend / divisor) * divisor

    // If the dividend was negative, the above modulus calculation will
    // be negative, but within (-divisor..0).  We can add (divisor) to
    // shift this result into the desired range of (0..divisor).
    if (modulus < 0) then
        set modulus = modulus + IAbsBJ(divisor)
    endif

    return modulus
endfunction

Or shorter.

function ModuloN takes integer a, integer n returns integer
    return a - a / n * n
endfunction

function ModuloNPos takes integer a, integer n returns integer
    return ModuloN(IAbsBJ(a), n)
endfunction

First function must be used when you are sure that a is positive.

The universal function.

function ModuloN takes integer a, integer n returns integer
    set a = IAbsBJ(a)
    return a - a / n * n
endfunction

Good thing is most people never use negative divisor so no-one ever experienced it probably. But yeah if you can't use % and need negative divisor you can use the above. In the case in my code in the OP ModuloInteger will always work (if you respect the API).

 

[Aniki]

This is cool, I think I've been shuffling integer arrays up until now...


The sign of the result of Jass' '%' binary operator seems to be that of the dividend (like in C99), instead of the divisor (like in Lua).
The sign of the result of Jass' 'ModuloInteger' function seems to always be '+' (almost like that of the euclidian remainder), except when both paramters are negative.

With that said:

function index ...
    // again thanks to jasshelper we can't use %
    return ModuloInteger(i+seed, hi)
...

If we replace 'ModuloInteger' with Jass' '%' operator we might get a negative result if 'seed' is negative (which it can be?).

Because the 'Permutation_index' functions ends up getting called in a loop it seems like a good idea to "optimize" it (in Jass, I guess this would mean to inline the functions that it calls), i.e some like the following:

function next_index takes integer n, integer p, integer seed, integer a returns integer
    loop
        set a = a * 0xe170893d
        set a = a + 0x0929eb3f
        set a = a * 0x6935fa69
        set a = a - seed
        set a = a * 0xc860a3df

        set a = BlzBitAnd(a, p)
        exitwhen a < n
    endloop

    // at this point a < n, not sure why we need to 'return (a+seed) mod n;'

    set a = a + seed

    set a - (a/n) * n
    if a < 0 then
        set a = a + n
    endif

    return a
endfunction

Not sure why you moved the 'w/p' parameter computation inside the function, now it gets recomputed every time, and the function does get called in a loop, so... =)

function index ...
    local integer w = nextPowerOfTwo(hi)
...

Like in the Pixar paper, it can be computed outside and passed as a paramter.

function next_pow2 takes integer x returns integer
    // set x = x - 1
    // set x = BlzBitOr(x, x/2)
    // set x = BlzBitOr(x, x/4)
    // set x = BlzBitOr(x, x/16)
    // set x = BlzBitOr(x, x/256)
    // set x = BlzBitOr(x, x/65536)
    // return x

    local integer p = 1
    loop
    exitwhen x <= p
        set p = p+p
    endloop
    return p - 1
endfunction

function demo takes nothing returns nothing
    local integer n
    local integer p
    local integer seed
    local integer a
    local integer b
    local integer s
    local integer e

    set n = 5
    set p = next_pow2(n)
    set seed = -1337
    set a = 0
    loop
        exitwhen a == n
        set b = next_index(n, p, seed, a)
        call BJDebugMsg(I2S(a) +": "+ I2S(b))
        set a = a + 1
    endloop
    // 0, 3
    // 1, 1
    // 2, 0
    // 3, 4
    // 4, 2


    // [s .. e]
    set s = -6
    set e = 7

    set n = e - s + 1
    set p = next_pow2(n)
    set seed = 69105
    set a = 0
    loop
        exitwhen a == n
        set b = s + next_index(n, p, seed, a)
        call BJDebugMsg(I2S(a) +": "+ I2S(b))
        set a = a + 1
    endloop
    // 0, 5
    // 1, 0
    // 2, -5
    // 3, 6
    // 4, 1
    // 5, -4
    // 6, 7
    // 7, 2
    // 8, -3
    // 9, -6
    // 10, 3
    // 11, -2
    // 12, -1
    // 13, 4
endfunction

 

[LeP]

This is cool, I think I've been shuffling integer arrays up until now...


The sign of the result of Jass' '%' binary operator seems to be that of the dividend (like in C99), instead of the divisor (like in Lua).
The sign of the result of Jass' 'ModuloInteger' function seems to always be '+' (almost like that of the euclidian remainder), except when both paramters are negative.

With that said:

function index ...
    // again thanks to jasshelper we can't use %
    return ModuloInteger(i+seed, hi)
...

If we replace 'ModuloInteger' with Jass' '%' operator we might get a negative result if 'seed' is negative (which it can be?).

I *think* dividend % divisor should only be negative if divisor is negative.

Because the 'Permutation_index' functions ends up getting called in a loop it seems like a good idea to "optimize" it (in Jass, I guess this would mean to inline the functions that it calls), i.e some like the following:

function next_index takes integer n, integer p, integer seed, integer a returns integer
    loop
        set a = a * 0xe170893d
        set a = a + 0x0929eb3f
        set a = a * 0x6935fa69
        set a = a - seed
        set a = a * 0xc860a3df

        set a = BlzBitAnd(a, p)
        exitwhen a < n
    endloop

    // at this point a < n, not sure why we need to 'return (a+seed) mod n;'

    set a = a + seed

    set a - (a/n) * n
    if a < 0 then
        set a = a + n
    endif

    return a
endfunction

Not sure why you moved the 'w/p' parameter computation inside the function, now it gets recomputed every time, and the function does get called in a loop, so... =)

function index ...
    local integer w = nextPowerOfTwo(hi)
...

Like in the Pixar paper, it can be computed outside and passed as a paramter.

Sure bunch of stuff to optimize if neccessary but i tried to keep it more clear instead of a bit faster.
Storing the power-of-two is ofcourse an easy optimisation and another usecase for a struct or so.
Same reason for the bijective function actually being a function: it's more clear.
The i + seed is just another source of "randomness".
And tbh a lot of this stuff could be done by an easy optimizing compiler (2*p = p+p, inlining R etc.).