1

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

Ninjdai
  • 21
  • 5
  • Didn't `2` move in your first example? I'm not clear on why `2` is an issue? In your second example, what happened to `0`? And instead `1` still in the same position as before? – Nick Parsons Jan 14 '23 at 06:09
  • 1
    If "random" is not your definition of "shuffled", then what is your exact definition of "shuffled"? For example: does simply shifting each element forward one index (modulo length) qualify? – jsejcksn Jan 14 '23 at 06:09
  • @jsejcksn It would theoretically qualify, but the result needs to change and I believe that it would repeat itself after some time – Ninjdai Jan 14 '23 at 06:15
  • 1
    [^](https://stackoverflow.com/questions/75116132/javacript-is-there-a-function-that-shuffles-an-array-with-every-element-switchi#comment132556251_75116132) "_it would repeat itself after some time_" @Ninjdai Any algorithm will eventually repeat: no finite ordered collection has infinite permutations. You'll need to supply a well-defined expectation to get a satisfying answer. – jsejcksn Jan 14 '23 at 06:18
  • @jsejcksn Imma try to clarify: I'm looking for a tuple of two arrays where no element of the first one is at the same index in the second one. Using modulo would kind of work, but my goal is to be theoretically able to have every combination of two elements, for example ([1, 2, 3, 4], [4, 1, 2, 3]) would be a possible result with your idea, but ([1, 2, 3, 4], [4, 3, 2, 1]) would not be by simply shifting the elements of the array. – Ninjdai Jan 14 '23 at 06:28

2 Answers2

-1

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]));
}
CertainPerformance
  • 356,069
  • 52
  • 309
  • 320
-1

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()
Drew Gallagher
  • 442
  • 1
  • 12