2
$\begingroup$

Please see the Reference section below for terms.

Is there a known one-way method to produce an array of indexes, based only on two input elements:

  • length of the resulting array
  • number, used as a key to deterministically produce the array

If there exists only a method that can produce only fixed-length arrays - it can also be a good start for me.

Examples:

Length Input number Resulting array of indexes
4 10001 [3, 0, 2, 1]
4 10002 [2, 3, 1, 0]
5 10001 [2, 3, 4, 1, 0]
5 10002 [4, 3, 0, 1, 2]

Reference:

  • an array of indexes:
    Array, whose values are all integers from 0 to (array's length - 1), unordered.
  • deterministic function:
    A function, producing the same result every time the same input data is provided
$\endgroup$

1 Answer 1

2
$\begingroup$

Start with an array of sorted indices.

The Durstenfeld Shuffle works by proceeding through the array, treating one part of the array as shuffled, and the rest of the array as un-shuffled. It simply swaps each of the items in the array with a random item from the un-shuffled region until the array is fully shuffled.

All permutations will be equiprobable.

A deterministic CSPRNG (seeded with your input number) is used to generate the random indices selected during the shuffle.

const csprng = new csprng(<input number seed>);
const len = 10;
const a = new Array(len);
for(let i=0; i<len; i++) a[i] = i;

for(let i=0; i<len; i++) {
  let swapIndex = nextDeterministicallyRandomIntBetween(i, len, csprng);
  let tmp = a[i]; a[i] = a[swapIndex]; a[swapIndex] = tmp; // swap
}

function nextDeterministicallyRandomIntBetween(lowerBoundInclusive, 
    upperBoundExclusive, csprng) {

  return lowerBoundInclusive +
    nextDeterministicallyRandomIntLowerThan(upperBoundExclusive-lowerBoundInclusive, csprng);
}

function nextDeterministicallyRandomIntLowerThan(upperBoundExclusive, csprng) {
  // determine the minimum number of bits "b" required to represent
  // (upperBoundExclusive-1).  Then repeatedly ask the csprng for b bits
  // until it returns a result that is lower than upperBoundExclusive
  let b = Math.ceil(Math.log(upperBoundExclusive) / Math.log(2));
  let r;
  do {
    r = csprng.nextBits(b);
  } while (r>=upperBoundExclusive);
  return r;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.