# Fast constant size overhead permutation generator

Discussion in 'The Lab' started by LeP, Sep 11, 2019 at 2:44 PM.

1. ### LeP

Joined:
Feb 13, 2008
Messages:
445
Resources:
0
Resources:
0
Fast constant size overhead permutation generator.
You can use this whenever you need numbers between 0 and x in a random order.

## Demo

Code (vJASS):

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
Code (Text):

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

Code (vJASS):

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

Last edited: Sep 12, 2019 at 5:20 PM
2. ### Bribe

Joined:
Sep 26, 2009
Messages:
8,015
Resources:
25
Maps:
3
Spells:
10
Tutorials:
3
JASS:
9
Resources:
25
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.

3. ### LeP

Joined:
Feb 13, 2008
Messages:
445
Resources:
0
Resources:
0
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).

4. ### Bribe

Joined:
Sep 26, 2009
Messages:
8,015
Resources:
25
Maps:
3
Spells:
10
Tutorials:
3
JASS:
9
Resources:
25
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??

5. ### LeP

Joined:
Feb 13, 2008
Messages:
445
Resources:
0
Resources:
0
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`
.

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

6. ### Prometheus3375

Joined:
Jul 20, 2018
Messages:
90
Resources:
0
Resources:
0
Can you explain, why?

7. ### LeP

Joined:
Feb 13, 2008
Messages:
445
Resources:
0
Resources:
0
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`

8. ### Prometheus3375

Joined:
Jul 20, 2018
Messages:
90
Resources:
0
Resources:
0
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.
Code (vJASS):
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.
Code (vJASS):
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.
Code (vJASS):
function ModuloN takes integer a, integer n returns integer
set a = IAbsBJ(a)
return a - a / n * n
endfunction

Last edited: Sep 14, 2019 at 1:35 PM
9. ### LeP

Joined:
Feb 13, 2008
Messages:
445
Resources:
0
Resources:
0
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).