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
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)
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
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.
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
System.out.println(results);
An example:
@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:
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.
Top comments (0)