I'm looking for a function that, instead of simply shuffling an array, shuffles it without any element being left at the index he was previously in.

I've tried the Fisher-Yates algorithm, but it didn't solve my problem:

function shuffle(array) {
  var m = array.length, t, i;
  while (m) {
    i = Math.floor(Math.random() * m--);
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }
}

When testing, I've got results like [0, 1, 2, 3, 4, 5] shuffling into [5, 0, 3, 1, 4, 2]. But here, 4 pretty much "stayed" at the same index it previously was.

The function I'm looking for would for example randomize [0, 1, 2, 3, 4, 5] into [4, 1, 5, 3, 2] where no element is at the same index it were previously

CodePudding user response：

Check that the element being put into the rightmost (first unsorted) position isn't the same as what was there originally. You'll also need to make sure that what gets inserted on the final swap doesn't result in an infinite loop - use a separate condition for that after the loop is over.

function shuffle(array) {
  const originalArray = [...array];
  let m = array.length;
  while (m > 1) {
    let i;
    do {
      i = Math.floor(Math.random() * m);
    } while (array[i] === originalArray[m - 1]);
    m--;
    const t = array[m];
    array[m] = array[i];
    array[i] = t;
  }
  if (array[0] === originalArray[0]) {
    [array[0], [array[1]]] = [array[1], [array[0]]];
  }
  return array;
}
for (let i = 0; i < 100; i  ) {
  console.log(shuffle([0, 1, 2, 3, 4, 5]));
}

CodePudding user response：

Using a hashmap you can track the previous position each number was stored in and then generate a random index until it is different from that previous position and any other indexes that have already been used.

The one edge case is with the last number you are placing. Since there's only 1 spot left, if you had that spot previously assigned for that number and try to generate until it's unique, it won't allow you to move anywhere else since all other indexes have been taken up. Thus you have to resort to keeping that one in the remaining position.

let numberToIndexMap = {}

/*
  For the last number we are checking (at index 0) there is a paradox where you might need to select an index
  that hasn't been chosen but you already were in that spot last time. Unfortunately 
  that number has to stay in that spot unless it shuffles the rest of the numbers
  Otherwise you will choose a spot in the array that has either been used

  */
function getRandomIndex(currentNumIndex, randIndex, currentNum, indexesUsed, length) {

    if (currentNumIndex == 0) {
        while (indexesUsed.includes(randIndex)) {
            randIndex = Math.floor(Math.random() * length);
        }
    } else {
        while (randIndex == numberToIndexMap[currentNum] || indexesUsed.includes(randIndex)) {
            randIndex = Math.floor(Math.random() * length);
        }
    }
    return randIndex
}


function shuffle(array) {
    var length = array.length;
    let currentNumIndex = length - 1
    let shuffledArray = []
    let indexesUsed = []

    while (currentNumIndex > -1) {
        let randIndex = Math.floor(Math.random() * length);
        let currentNum = array[currentNumIndex]

        let counter = 0;

        if (Object.keys(numberToIndexMap)?.length > 0) {
            randIndex = getRandomIndex(currentNumIndex, randIndex, currentNum, indexesUsed, length)
        }
        numberToIndexMap[currentNum] = randIndex
        indexesUsed.push(randIndex)
        shuffledArray[randIndex] = currentNum
        currentNumIndex--

    }
    return shuffledArray
}


function test() {
    let array = [1, 2, 3]
    for (let i = 0; i < 10; i  ) {
        array = shuffle(array)
        console.log(array)
    }
}

test()