Shuffle arrays of strings in JavaScript with repeated elements that are at least two elements apart

I have two arrays of strings:

var array1 = ["word1", "word2", "word3", "word4", "word5", "word6"];
var array2 = ["word7", "word8"];

I need to concatenate these arrays into a new array and shuffle the elements in a random order. However, the elements from array2 should repeat appear twice in this new array, and the repeats of a given element must be at least two elements apart from each other.

Here's an example result that satisfies these conditions:

["word7", "word3", "word8", "word7", "word1", "word4", "word6", "word8", "word5", "word2"];

All the elements are in a random order, and the repeated elements have at least two other elements between them. How can I write a function (using no extra libraries, preferably) that creates a randomly ordered array that satisfies the above conditions? I've tried extending standard permutation algorithms (e.g. Fisher-Yates) but I'm tripping over the implementation as I'm not very familiar with JS.

Any help greatly appreciated - thanks!

Solution 1:

The easiest would probably be doing it in two steps.

1. Shuffle array1 with a standard fisher-yates algorithm.
2. Insert the elements at random positions satisfying the conditions.

Ie something like the following (I assume, you can implement fisher yates, thus I didn't include it here and just made an (unshuffled) copy of the array)

let array1 = [1,2,3,4,5,6,7]
let array2 = [8,9]

let rand = (n) => Math.floor(Math.random()*n);

//let shuffled = fisheryates(array1);
let shuffled = array1.slice(); //just make a copy of the array
    
while (array2.length) {
  let e = array2.splice(rand(array2.length), 1)[0];
  let i1 = shuffled.length == 2 
    ? 0 
    : rand(shuffled.length + 1);
  let i2 = 0;
  do {
    i2 = shuffled.length == 2 
     ? 2 
     : rand(shuffled.length + 1);
  }
  while (Math.abs(i1 - i2) < 2)

  if (i1 < i2) {
    shuffled.splice(i2, 0, e);
    shuffled.splice(i1, 0, e);
  } else {
    shuffled.splice(i1, 0, e);
    shuffled.splice(i2, 0, e);
  }
}
    
console.log(shuffled)

How does it work:

Iterating over all elements from array2 in random order

• you get a random index for inserting the first element. If the shuffled has only 2 elements, the only valid indexes are 0 and 2 (because that's the only way, that there are at least two elements in between). I'm using shuffled.length + 1 here, because that allows to insert the element also at the end of the array.

• Then you need to find another index, which is at least two elements away from the first index. The easiest (but not necessarily the fastest) method is just to try until an index is found.

• When inserting the element in the array, you have to insert the bigger index first, because otherwise the upper element will be at the wrong position.

If array1 does only have one element, you need at least two elements in array2 to be able to generate a valid output, but you can do that by hand as as special case.

let array1 = ['a']
let array2 = ['x', 'y', ...]
let shuffled = ['x', 'y', 'a', 'x', 'y'] //or yxayx