How to generate unique numbers using Fisher-Yates Algorithm with Java
Tags: algorithms, tutorial, java
Published: 2021-09-01 19:37:02

In this article, we will be writing a java program that implements the paper and pencil method of the Fisher-Yates algorithm to generate nth unique numbers. 

You can also use any list of numbers (or anything else it doesn't matter ) to shuffle their sequence.

But first ...

### What is this fish?
The Fisher-Yates shuffle is an algorithm named after Ronald Fisher and Frank Yates, and it is used to shuffle a sequence. Time Complexity: O(n). The main idea is that imagine you have ordered numbers written on a scratch paper, and you randomly strike out a number and write it down on another piece of paper. You do this until no unstruck number remains. The order in which the numbers are written is your shuffled sequence.

Here we go! 🚀

### 1. Start by declaring the variables you will use
 throughout the program 
```java
int n = Integer.parseInt(args[0]) ; // amount of numbers to generate
int k; // random index of unstruckNums
ArrayList<Integer> unstruckNums = new ArrayList<Integer>();
ArrayList<Integer> results = new ArrayList<Integer>();
```
### 2. Fill the UnstruckNums list with numbers 
from 0 to n (exclusive)

```java
for (int i = 0; i < n; i++) {
    unstruckNums.add(i);
}
```
Now, what we want to do is strike out random numbers from the `unstruckNums` list and add them to a separate list which is the `results`. To achieve this we
### 3. generate a random index k 
which is between 0 and the amount of `unstruckNums` remaining
```java
for (int i = 0; i < n; i++) {
    // k represents the index of the number we want to strike out from the unstruckNums
    k = (int) Math.floor(Math.random() * (unstruckNums.size()));
}
```

### 4. Add the number at index k to our result List 
and strike it out from the `unstruckNums` list.
 ```java
for (int i = 0; i < n; i++) {
    k = (int) Math.floor(Math.random() * (unstruckNums.size()));
    results.add(unstruckNums.get(k));
    unstruckNums.remove(unstruckNums.get(k)); 
}
```

That's it, your done. Print out the results
```java
 System.out.println(results);
```
An example:
```powershell
@tebza> javac UniqueNums.java
@tebza> java UniqueNums.java 12
[6, 1, 0, 5, 4, 10, 2, 11, 3, 8, 9, 7]
```

Here is the full code:
``` java
import java.util.ArrayList;

public class UniqueNums{
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]) ; // amount of numbers to generate
        int k; // random index of unstruckNums
        ArrayList<Integer> unstruckNums = new ArrayList<Integer>();
        ArrayList<Integer> results = new ArrayList<Integer>();
        // Fill the UnstruckNums list with numbers from 0 to n
        for (int i = 0; i < n; i++) {
           unstruckNums.add(i);
        }
        for (int i = 0; i < n; i++) {
            // k represents the index of the number we want to strike out from the unstruckNums
           k = (int) Math.floor(Math.random() * (unstruckNums.size()));
           results.add(unstruckNums.get(k));
           unstruckNums.remove(unstruckNums.get(k)); 
      }
        System.out.println(results);
   }
}
```

### Conclusion 
The fisher-yates shuffle is a simple algorithm used to shuffle the sequence of lists. We have used it to shuffle an ordered list of numbers, to generate a list of unique numbers.