Javascript - Algorithm to repeatedly pseudorandomly select from a set, without frequent repeats

SteveBennett
October 24, 2023
71 views
3 votes
3 Answers

I have an array of things (conceptually a set, but let’s implement as an array), say [A, B, C, D, E, F].

I need an algorithm that can pseudo-randomly pick an item from the array such that no item will be picked twice within x iterations.

That is, if x is 3 for this array, this would be ok: F, C, B, D, F, E, A, B,…

This would not be ok: F, C, D, C, …

Other than this constraint, the selections should be as random as possible. (For instance, simply shuffling the array and selecting within copies of it is not acceptable.)

Ideally, this would achieved without having to record all the previous picks.

So the function would have a structure like:

function pick(options, minspacing, iteration) {...}

Answers

This seems to fit the bill:

For each iteration i, if i<x, then:

randomly choose an index j in [i,N)
if i!=j, then swap A[i] with A[j]
return A[i]

For all other iterations, where i>=x:

randomly choose an index j in [x, N)
swap A[j] with A[i%x]
return A[i%x]. It will not be swapped back into the choosable range until after x more iterations.

function pick(options, minspacing, iteration) {
    if (iteration < minspacing) {
         const j = Math.floor(Math.random()*(options.length - iteration)) + iteration;
        const t = options[j];
        options[j] = options[iteration];
        options[iteration] = t;
        return t;
    } else {
        const j = Math.floor(Math.random()*(options.length - minspacing)) + minspacing;
        const i = iteration % minspacing;
        const t = options[j];
        options[j] = options[i];
        options[i] = t;
        return t;
    }
}

const opts = ['A', 'B', 'C', 'D', 'E', 'F'];
const results = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].map(i => pick(opts, 3, i));
console.log(results);

This code choses a pseudo-random index from a range >=2 without replacement up to an arbitrary non-repetition length >=1 . You can then use the index to dereference any array of values of the same length [A,B,C … ].

var max_choice = 10; // >= 2
var replacement_limit = 3; // >= 1 

let chosen = new Array(replacement_limit);

function chose() {
  let choice;
  do {
    choice = Math.floor(Math.random() * max_choice);
  } while (chosen.includes(choice));
  if (chosen.length == replacement_limit) {
    chosen.pop();
  }
  chosen.unshift(choice);
  return choice;
}

let runs = 20
for (let i = 0; i < runs; i++) {
  console.log(chose());
}

Incorporating this as a closure you have a generator of unlimited choice iterations.

var options = ['A', 'B', 'C', 'D', 'E', 'F'];
var replacementLimit = 3; // >= 1 and <options.length

function pick(options, minSpacing) {
  let chosen = new Array(minSpacing);
  return function chose() {
    let choice;
    do {
      choice = Math.floor(Math.random() * options.length);
    } while (chosen.includes(choice));
    if (chosen.length == minSpacing) {
      chosen.pop();
    }
    chosen.unshift(choice);
    return options[choice];
  }
}

let iteration = 20;
generateChoice = pick(options, replacementLimit);
for (let i = 0; i < iteration; i++) {
  console.log(generateChoice());
}

My approach to handle this problem (as per my understanding of the problem) would be like:

Pseudocode:

1. Init: 
        Set s; for keeping track of recently picked items.
        counter; for keeping track of number of iterations.
        result; for storing result.
2. while counter < iteration:
      2.1. Pick a random item from the options array
      2.2. if item is not in s:
           2.2.1. If the size of s === len(options):
                  2.2.1.1. clear s.
           2.2.2. Add it to set and add the pick to result.
           2.2.3. Increment the counter.
      2.3. If item in s, but we haven't reached the minimum spacing,
          2.3.1. continue to pick a new item.
      2.4. If item in s, and we've reached the minimum spacing,
           2.4.1. Remove it from the set and continue to pick a new item.

CODE IMplementation:

function pick(options, minspacing, iteration) {
  const s = new Set();
  let counter = 0;
  let result = "";
  while (counter < iteration) {
    const index = Math.floor(Math.random() * options.length);
    const item = options[index];

    if (!s.has(item)) {
      if (s.size === options.length) {
        s.clear();
      }
      result += `${item} `;
      s.add(item);
      counter++;
    } else if (counter % minspacing !== 0) {
      continue;
    } else {
      s.delete(item);
      continue;
    }
  }
  return result.trim();
}
const options = ['A', 'B', 'C', 'D', 'E', 'F'];
console.log(pick(options, 3, 10));

Hope it helps.

Please signup or login to give your own answer.

Click here to cancel reply.

Javascript – Algorithm to repeatedly pseudorandomly select from a set, without frequent repeats

Answers