sample array n^2 times without the same number occurring twice in a row and not repeating every n

MayaGans 0
Viewed 43

I'm trying to write a function that has the arguments of the array to sample arr and the number of samples, size (which is sqaured) and randomly samples from the original array:

arr = [1,2,3,4]

single_number = (x) => {
  return x[Math.floor(Math.random()*x.length)];
}

randomize = (arr, size) => {
  return Array(size*size).fill().map(x => single_number(arr))
}

randomize(arr, 5)

I want to add the additional requirements to my randomize function:

  1. no number shows up twice in a row
  2. make sure every sizeth item is not the same as the one before it

For example

randomize([1,2,3,4], 2)

[2,4,3,2,4,1,1,2,2,1,4,1,1,1,3,1,1,4,4,1,3,3,2,2,3]

CASE (1)

[
  2,4,3,2,4,
  2,1,       
  2,2,       // illegal!
  1,4,
  1,1,1,     // illegal!
  3,
  1,1,       // illegal!
  4,4,       // illegal!
  1,
  3,3,       // illegal!
  2,2,       // illegal!
  3
]

CASE (2)

[
  2,4,3,2,4,  [0] === 2 
  2,1,2,2,1,  [5] === 2 // illegal! 
  4,1,1,1,3,  
  1,1,4,4,1,
  3,3,2,2,3
]

I'm trying to use functional programming and avoid a for loop if possible since I think I can do this with a nested for loop?

arrays javascript
2 Answers

Well, this isn't as pretty as one would hope, but I think it accomplishes the objective: Iterate size^2 times and choose random elements from the input, taking care to exclude the last value and last nth value chosen...

const randomize = (array, size) => {
  const rand = () => Math.floor(Math.random() * array.length);
  const randExcept = exclude => {
    let v = array[rand()];
    while (exclude.includes(v)) v = array[rand()];
    return v;
  }
  const indexes = Array.from(Array(size*size).keys());
  let lastV = null, nthV = null;
  return indexes.map(i => {
    let exclude = nthV!==null && i%size===1 ? [lastV, nthV] : [lastV];
    let v = randExcept(exclude);
    lastV = v;
    if (i%size===1) nthV = v;
    return v;
  })
}

console.log( JSON.stringify(randomize([1,2,3,4], 2)) )

This defines nth values by the count into the array, so for size===2, the constraint is that every second element (indexes 1,3,5...) can't be equal to the prior second element.

danh0

I'd probably do something like this:

const values = [1,2,3,4]

function randomize(values, size) {
  let prev;
  let prevNth;

  return Array(size*size).fill().map( randomNumber );

  function randomNumber(_,i) {
    let value, ok;

    do {
      value = values[ Math.floor( Math.random() * values.length ) ];

      ok = value != prev;

      if ( i % size === 0) {
        ok = ok && value != prevNth;
        prevNth = value;
      }

      prev = value;

    } while (!ok);

    return value;
  }

}

arr = randomize(values, 5)

console.log(JSON.stringify(arr));

Or this, using a generator to generate the appropriately sized stream of randomness:

const values = [1,2,3,4];
const arr1 = Array.from( randomValues(5,values) );

console.log(JSON.stringify(arr1));

function *randomValues(n, values) {
  const limit = n*n;
  let prev, prevNth;

  for ( let i = 0 ; i < limit ; ++i ) {
    const isNthValue = i % n === 0;
    const value = randomValue( values, prev, isNthValue ? prevNth : undefined );
    yield value;

    prev = value;
    prevNth = isNthValue ? value : prevNth;
  }

}

function randomValue(values, test1, test2 ) {
  let value;
  do {
    value = values[ Math.floor( Math.random() * values.length ) ];
  } while (value === test1 || value === test2 );
  return value;
}
Nicholas Carey0
Related