shuffle array without consecetive item - Javascript

Question

I currently acheive shuffle one of array without duplicated with previous value of next value.

However, I don't think my method is good. I think there are better way.

Firstly, I will describe what the array looks like.

it's an array of object with property {answer,url,category} and there are duplicated item in the array. think as [A,A,B,B,C,C] , A,B,C as object here.

As EzioMerce pointed out, in this array, object will always has equal amount of numbers. such if there are 3 A, will definitely have 3 B and C. It will not have array as such [A,A,A,B]

I need the array to shuffle until there is no consecutive object next to each other such as [A,B,C,B,A,C]

Here is my solution (which I have tested 40 times without consecutive object):

getShuffleWords(array: Card[]) {
    //First shuffle..
    for (let i = array.length - 1; i > 0; i--) {
      const j = Math.floor( Math.random() * (i - 1));
      if (j > 0) {
        //make sure there are no simliar value around position i and j
        if (array[i]?.answer !== array[j - 1]?.answer
          && array[i]?.answer !== array[j + 1]?.answer
          && array[i]?.answer !== array[j - 1]?.answer
          && array[i]?.answer !== array[j + 1]?.answer) {
          [array[i], array[j]] = [array[j], array[i]];
        }
      } else {
        if (array[i]?.answer !== array[j + 1]?.answer) {
          [array[i], array[j]] = [array[j], array[i]];
        } 
      }
    }

    const before = [...array];
    console.log(before);
    //Checking duplicate and swap with other value
    for (let x = 0; x < array.length; x++){
      if (array[x].answer == array[x + 1]?.answer) {
        console.log(x,array[x])
        for (let y = 0; y < array.length; y++){
          //make sure there are no simliar value around position x and y
          if (array[y]?.answer !== array[x]?.answer
            && array[y + 1]?.answer !== array[x].answer
            && array[y - 1]?.answer !== array[x].answer
            && array[y]?.answer !== array[x+1]?.answer
            && array[y]?.answer !== array[x-1]?.answer
          ) {
            console.log(y, array[y]);
            if (x < y) {
              [array[x], array[y]] = [array[y], array[x]];
            } else {
              [array[y], array[x]] = [array[x], array[y]];
            }
            
            break;
          }
        }
      }
    }

    //just another caculate if there is duplication left (for testing purpose)
    let dup = 0;
    for (let x = 0; x < array.length; x++){
      if (array[x].answer == array[x + 1]?.answer) {
        dup++;
      }
    }
    console.log(array, dup);
    return array;
  }

However, in the //First shuffle.. there are always has some consecutive object exisited in the array. thats why I repeat another checking and replace the value.

How would I improve my method. and why my first shuffle does not work perfectly?

Is it guaranteed that there is a solution? If not what do you expect if input be `[A, A, A, B]` — EzioMercer, Mar 03 '22 at 10:58
@EzioMercer thanks for pointing out and sorry for the confusion, there are equal amout of objects within the array. if the array has 3 A, it will definitely has 3 B and C. — Johnathan Li, Mar 03 '22 at 11:02
Okay I understood you. Is it okay for you if answer always be like `[A, B, C, A, B, C, A, B, C ...]`? — EzioMercer, Mar 03 '22 at 11:05
@EzioMercer no, it should be random order. [A,C,B,A,B,C] or [ A,B,C,A,C,B,] or etc.. and the object could be more than ABC depends how many different object in the array. — Johnathan Li, Mar 03 '22 at 11:11

Nina Scholz · Answer 1 · 2022-03-03T14:38:59.987

You could shuffle an array of indices of same grouped values until you got a result which has no same neighbour indices.

const
    fy = array => { // fisher-yates, adapted from https://stackoverflow.com/a/59837259/1447675
        let i = array.length;
        while (--i) {
            const j = Math.floor(Math.random() * (i + 1));
            [array[j], array[i]] = [array[i], array[j]];
        }
    },
    shuffle = array => {
        do fy(array);
        while (array.some((v, i, a) => v === a[i + 1]))
    };
    indices = [0, 0, 0, 1, 1, 1, 2, 2];

shuffle(indices);

console.log(...indices);

Sorry for the late reply. I will test this! thanks. – Johnathan Li Mar 09 '22 at 12:34 — Johnathan Li, Mar 09 '22 at 12:34

EzioMercer · Accepted Answer · 2022-03-03T12:17:07.373

You can try this way. It also works if arr will be an array of objects

const arr = [1, 2, 3, 1, 2, 3, 1, 2, 3];

const shuffle = (arr) => {
    const uniqueArr = [...(new Set(arr))];
    const shuffledArr = [];
    let countOfOneObj = 0;

    for (const obj of arr) {
        if (obj === arr[0]) ++countOfOneObj;
    };

    const getRandomObj = () => {
        const i = Math.floor(Math.random() * uniqueArr.length);
        return uniqueArr[i];
    }

    for (let i = 0; i < countOfOneObj; ++i) {

        let usedObjs = []

        for (let j = 0; j < uniqueArr.length; ++j) {
            const obj = getRandomObj();

            if (
              usedObjs.includes(obj) ||
              shuffledArr[shuffledArr.length - 1] === obj
            ) {
                --j;
                continue;
            }

            usedObjs.push(obj);
            shuffledArr.push(obj);
        }

        usedObjs = [];
    }

    return shuffledArr;
}

console.log(shuffle(arr));

@JohnathanLi It will be better if at the line `let usedObjs = []` we change `usedObjs` to a `new Set()` because `.includes()` will iterate array and we will get 3 loops, but with `new Set()` we can check if `obj` exists or not just with `O(1)` complexity. I can rewrite my code if you want it — EzioMercer, Mar 16 '22 at 12:12

shuffle array without consecetive item - Javascript

2 Answers2