Shuffle Elements of Array Randomly Fisher-Yates (Knuth) shuffle

In this blog we will discuss how to shuffle elements of array randomly using Fisher-Yates (Knuth) algorithm. We will also add some additional checks later to ensure we get shuffled array in any case i.e. if array has 2 or more elements. If array has one element or empty we can’t produce shuffled array.

To shuffle an array, you can use the Fisher-Yates (Knuth) shuffle algorithm. It basically generates a random index between 0 (inclusive) and the current index (inclusive) and then swaps the value at the randomly generated index with the value at the current index. This operation is performed for all the values in the array by executing a loop.

function shuffleArray(array) {
  // Use the Fisher-Yates (Knuth) shuffle algorithm
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    // Swap array[i] and array[j]
    [array[i], array[j]] = [array[j], array[i]];
  }
}

// Example usage
const myArray = [1, 2, 3, 4, 5];
shuffleArray(myArray);
console.log(myArray);

Math.random() generates a value between 0 and 1 (exclusive) , think of i as current index and j as random index generated. Hence Math.random()*(i+1) would generate a value between 0 and current Index(inclusive).

Math.floor() will convert the generated random value to integer before decimal point. So 2.3 would be converted to 2, 0.5 would be converted to 0 . Effectively value of j will be integer and can be anything between 0 and current index value (inclusive) . We take this random index value and find swap the value present at index j with value at index i.

It is possible that array won’t be shuffled after full operation.

It might be possible , but possibility is very low. For that to happen each time Math.floor(Math.random()*(i+1)) will have to give index such that swaping won’t affect the array. So, value at index i and index j needs to be same. Also if there is just one element in array then shuffling would produce the same array. When there is only two elements there is high probability that the algorithm won’t produce shuffled array. The probability of not producing shuffled array would decrease as size of array increases.

That being said, if you want to ensure the array is shuffled, you can add a check after the loop to verify if any changes occurred during the shuffling process. Array is shuffled if there exist at least one element in shuffled array such that at this index there is different value in original array.

function shuffleArray(array) {
let originalArray = [...array]
  // Use the Fisher-Yates (Knuth) shuffle algorithm
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    // Swap array[i] and array[j]
    [array[i], array[j]] = [array[j], array[i]];
  }

  // Check if the array is already shuffled
  
  const isArrayShuffled = array.some((value, index) => value !== originalArray[index]);
  console.log(isArrayShuffled);
  // If not shuffled, call the function again
  if (!isArrayShuffled) {
    shuffleArray(array);
  }
}

// Example usage
const myArray = [1, 2];
shuffleArray(myArray);
console.log(myArray);

Keep in mind that this additional check may add some overhead, and the likelihood of the array not being shuffled after the loop is minimal in practice.

Infinite loop

The additional check for shuffled array could lead to an infinite loop for arrays with 1 or no elements since there is no opportunity for shuffling in those cases.

To address this issue, you can modify the function to check if the array has more than one element before attempting to shuffle. If the array has only one or no elements, there’s no need to shuffle it.

function shuffleArray(array) {
let originalArray = [...array]
  // Check if there are more than one element in the array
  if (array.length > 1) {
    // Use the Fisher-Yates (Knuth) shuffle algorithm
    for (let i = array.length - 1; i > 0; i--) {
      const j = Math.floor(Math.random() * (i + 1));
      // Swap array[i] and array[j]
      [array[i], array[j]] = [array[j], array[i]];
    }

    // Check if the array is already shuffled
    const isArrayShuffled = array.some((value, index) => value !== originalArray[index]);

    // If not shuffled, call the function again
    if (!isArrayShuffled) {
      shuffleArray(array);
    }
  }
}

// Example usage
const myArray = [1, 2, 3, 4, 5];
shuffleArray(myArray);
console.log(myArray);

This modification ensures that the shuffle operation and the check for already shuffled state are only performed when there are more than one element in the array.

Don't Miss Out! Subscribe to Read Our Latest Blogs.

If you found this blog helpful, share it on social media.

Subscription form (#5)

Leave a Comment

Your email address will not be published. Required fields are marked *

Pin It on Pinterest

Scroll to Top