Lua - Shuffling Arrays

We can shuffle an array easily in multiple ways in Lua. We're going to use Fisher-Yates Shuffle Algorithm for the same.

Fisher-Yates Shuffle Algorithm

The Fisher-Yates Shuffle algorithm shuffles a given finite sequence of elements by generating a random permutation where the possibility of every permutation occurring is nearly same. The algorithm is performed by storing the elements of the sequence in a sack and drawing each element randomly from the sack to form the shuffled sequence.

Coined after Ronald Fisher and Frank Yates, for designing the original method of the shuffle, the algorithm is unbiased. It generates all permutations in same conditions so the output achieved is nowhere influenced. However, the modern version of the Fisher-Yates Algorithm is more efficient than that of the original one.

For more details, you can refer to Fisher-Yates Shuffle Algorithm.

Following are the steps used to shuffle an array.

The algorithm to generate the random permutation is as follows−

• Step 1− Write down all the elements in the finite sequence. Declare a separate list to store the output achieved.

• Step 2− Choose an element i randomly in the input sequence and add it onto the output list. Mark the element i as visited.

• Step 3− Repeat Step 2 until all the element in the finite sequence is visited and added onto the output list randomly.

• Step 4− The output list generated after the process terminates is the random permutation generated.

Example - Shuffling an Array of numbers

In following example, we're shuffling an array of numbers. Every time program is run, a different shuffled array is printed.

main.lua

-- randmoize seed
math.randomseed(os.time()) 

-- function to shuffle the array
function shuffle( array )
   local returnArray = {}
   -- loop over elements of array
   for i = #array, 1, -1 do
      -- get a random index
      local j = math.random(i)
      -- swap the elements of the array
      array[i], array[j] = array[j], array[i]
      -- insert the element in target array
      table.insert(returnArray, array[i])
   end

   -- return the target array
   return returnArray
end

-- create the array
array = { 1, 2, 3, 4, 5, 6}

-- print source array
for i = 1, #array do
   print(array[i])
end

-- shuffle the array
shuffledArray = shuffle(array)
print("Shuffled array: ")

-- print the suffled array
for i = 1, #shuffledArray do
   print(shuffledArray[i])
end

Output

When we run the above code, we will get the following output−

1
2
3
4
5
6
Shuffled array: 
5
1
6
3
2
4

Example - Shuffling an Array of Strings

In following example, we're shuffling an array of Strings. Every time program is run, a different shuffled array is printed.

main.lua

-- randmoize seed
math.randomseed(os.time()) 

-- function to shuffle the array
function shuffle( array )
   local returnArray = {}
   -- loop over elements of array
   for i = #array, 1, -1 do
      -- get a random index
      local j = math.random(i)
      -- swap the elements of the array
      array[i], array[j] = array[j], array[i]
      -- insert the element in target array
      table.insert(returnArray, array[i])
   end

   -- return the target array
   return returnArray
end

-- create the array
array = { "A", "B", "C", "D", "E", "F"}

-- print source array
for i = 1, #array do
   print(array[i])
end

-- shuffle the array
shuffledArray = shuffle(array)
print("Shuffled array: ")

-- print the suffled array
for i = 1, #shuffledArray do
   print(shuffledArray[i])
end

Output

When we run the above code, we will get the following output−

A
B
C
D
E
F
Shuffled array: 
D
C
B
F
A
E