Score:2

Deterministically produce an array of indexes based on input number

in flag

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
Score:2
es flag

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;
}
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.