We are provided with an array, Now, WAP (write a program) to generate a random permutation of array elements. For example when we say “shuffle a deck of cards” or “randomize an array”.

Above mentioned ‘shuffle’ implies that each permutation of an array element should be equally likely.

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.

Happy Coding 🙂