This article introduces the implementation of Fisher–Yates shuffle shuffle algorithm using shell syntax.
Introduction to Fisher-Yates shuffle algorithm
The Fisher–Yates shuffle algorithm can be used to randomly arrange arrays. Its time complexity is O(n). The pseudocode is as follows:
To shuffle an array a of n elements (indices 0..n-1): for i from n - 1 downto 1 do j = random integer with 0 <= j <= i exchange a[j] and a[i]
Assume that there is an array a=[1, 2, 3, 4, 5, 6, 7, 8, 9] and the length of the array is n, the specific iteration steps for disrupting the elements in a are as follows:
Generate a random number k for the interval [0, n-1]; exchange the kth element and n-1th element; perform the next iteration to generate a random number k for the interval [0, n-2], exchange the kth element and n-2th element, and the number of iterations is n-1: take 1 from n-1; finally obtain a messed array.
The following table is the specific disruption process of an array. The disrupted array is (9 4 8 1 2 3 5 6 7)
| Random number | Original array | New array |
|---|---|---|
| 0-8：6 | a = (1 2 3 4 5 6 7 8 9) | Exchange a[8] and a[6]: (1 2 3 4 5 6 9 8 7) |
| 0-7：5 | a = (1 2 3 4 5 6 9 8 7) | Exchange a[7] and a[5]: (1 2 3 4 5 8 9 6 7) |
| 0-6：4 | a = (1 2 3 4 5 8 9 6 7) | Exchange a[6] and a[4] : (1 2 3 4 9 8 5 6 7) |
| 0-5：2 | a = (1 2 3 4 9 8 5 6 7) | Exchange a[5] and a[2] : (1 2 8 4 9 3 5 6 7) |
| 0-4：1 | a = (1 2 8 4 9 3 5 6 7) | Exchange a[4] and a[1] : (1 9 8 4 2 3 5 6 7) |
| 0-3：0 | a = (1 9 8 4 2 3 5 6 7) | Exchange a[3] and a[0]: (4 9 8 1 2 3 5 6 7) |
| 0-2：2 | a = (4 9 8 1 2 3 5 6 7) | Exchange a[2] and a[2]: (4 9 8 1 2 3 5 6 7) |
| 0-1：0 | a = (4 9 8 1 2 3 5 6 7) | Exchange a[1] and a[0]: (9 4 8 1 2 3 5 6 7) |
shell implementation
:
#!/bin/bash
shuffle() {
local i tmp size max rand
# Chaotic order # Knuth-Fisher-Yates shuffle algorithm
size=${#my_array[*]}
max=$(( 32767 / size * size ))
# echo "max: $max"
for ((i=size-1; i>0; i--)); do
while (( (rand=$RANDOM) >= max )); do :; done
rand=$(( rand % (i+1) ))
# exchange tmp=${my_array[i]}
my_array[i]=${my_array[rand]}
my_array[rand]=$tmp
echo ${my_array[*]}
done
}
my_array=(1 2 3 4 5 6 7 8 9)
shuffle
echo ${my_array[*]}
Execution effect:
$ sh 1 2 3 4 9 6 7 8 5 1 8 3 4 9 6 7 2 5 7 8 3 4 9 6 1 2 5 7 8 6 4 9 3 1 2 5 7 8 6 9 4 3 1 2 5 7 9 6 8 4 3 1 2 5 7 6 9 8 4 3 1 2 5 7 6 9 8 4 3 1 2 5
This is the article about the introduction to shell's implementation of Fisher-Yates shuffle shuffle algorithm. For more related shell Fisher-Yates shuffle shuffle algorithm, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!