Is there an easy way to adapt the algorithm to get the cards drawn in a random order? The article says "it’s easy to randomize the order after the fact" but if we can't store them in memory then that's a no-go.
You can produce an exact random permutation with a Feistel network for any number, in this case selecting every number between 0 and 2^64 exactly once, with no appreciable space requirements.
procedure feistel(input) {
result = input;
h = 2<<32;
for (let i = 0; i < 8; i++) {
l = (input / h)|0;
r = input % h;
temp = r;
fn = (r + i) % h;
r = (l + fn) % h;
l = temp;
result = h * l + r;
}
return result;
}Here's a working implementation:
function feistel(ctr, lr, ll) {
let result = ctr;
for (var i = 0; i < 8; i++) {
let l = (result / ll)|0;
let r = result % ll;
let temp = r;
// alter round fn's multiplier & increment accordingly.
let fn = (r * 16807 + i) % lr;
r = (l + fn) % lr;
l = temp;
result = lr * l + r;
}
return result;
}
let rsize = 8;
let outputs = new Set();
for(let i = 0; i < rsize * rsize; i++) outputs.add(feistel(i, rsize, rsize))
for(let i = 0; i < rsize * rsize; i++) if (!outputs.has(i)) console.log('failure: ', i);If you look at his code, the first function seems to be calling a method that claims to do the latter. I think his documentation may be out of sync.