Randomize an array – Algorithms and JAVA/Python codes. Introduction to Random QR codes.

I/P Array – {1987, 1986, 1985, 1984, 1983, 1982, 1981, 1980} O/P Array – {1986, 1987, 1984, 1985, 1982, 1983, 1980, 1981} OR {1980, 1986, 1985, 1984, 1983, 1982, 1981, 1987}

Below is the algorithm.

• Step 1 – Add the elements of the array and store in a variable. Say ‘Total’
• Step 2 – Select an element from the original array randomly.
• Step 3 – Add the element from Step 1 to a list(create an empty list).
• Step 4 – In the original array replace the element selected in Step 1 with ‘Total’.
• Step 5 – Select a random element from the original array, and ignore ‘Total’.
• Step 6 – Add the element from Step 5 to the list created in Step 3.
• Step 7 – Replace the element selected in Step 5 with ‘Total’.
• Repeat Steps 5,6,7 till we find no element in the original array other than ‘Total’.

Above algorithm is a bit turnaround. The time complexity is k times O(n). (k = constant). So we will take a shorter path with time complexity O(n).

Simpler Algorithm

• Step 1 – Select a random element from original array from indices 0 to n-2.
• Step 2 – Replace last element with the element selected in Step 1.
• Step 3 – Repeat the Step 1 and Step 2 till the logic has reached to first element.

Above algorithm has O(n) time complexity. It is faster in performance. Crisp Recipe. Let’s see the codes below.

Below are codes in JAVA and Python.

JAVA Version

//Importing Random and Arrays from Java.Util package.
import java.util.Random;
import java.util.Arrays;
public class Randomize
{
    public static void randomize( int Array2[], int n)
    {
        // Instantiating Random class below.  
        Random randomize = new Random();
        for (int i = n-1; i > 0; i--) {
            // Choose random index
            int j = randomize.nextInt(i+1);
            // Swap Array2[i] with the element at random index
            int temp = Array2[i];
            Array2[i] = Array2[j];
            Array2[j] = temp;
        }
        System.out.println(Arrays.toString(Array2));
    }
     
    // Main
    public static void main(String[] args)
    {
         
         int[] Array1 = {1987, 1986, 1985, 1984, 1983, 1982, 1981, 1980};
         int n = Array1.length;
         //Display the original array
         System.out.println(Arrays.toString(Array2));
         randomize (Array1, n);
    }
}

Python

# Below is the python version for the same problem
# Importing randint for choosing random indices of original array
from random import randint

#Function
def randomize (Array2, n):
    # For Algorithm check above
    for i in range(n-1,0,-1):
        # Choose a random index from 0 to i
        j = randint(0,i+1)
 
        # Swap arr[i] with the element at random index
        Array2[i],Array2[j] = Array2[j],Array2[i]
    return Array2
 
# Driver program to test above function.
Array1 = [1987, 1986, 1985, 1984, 1983, 1982, 1981, 1980]
n = len(Array1)

#Print original
print(Array1)
#Print Randomize
print(randomize(Array1, n))

In our next blog we will bring the Random QR code generation algorithms. Above blog was introduction to the same.