Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we have presented two algorithms to select a random node from Linked list efficiently while maintaining uniform randomness.
Table of contents:
- Introduction to Randomized Algorithms
- Efficient Approach
- Second Approach: Using auxillary array
Introduction to Randomized Algorithms
In Mathematics , we all have studied about the concept of random events,experiments and the probablities govering them. For solving the above problem we generally use the concept of Probability and Randomised Algorithm.
Now before jumping at the problem, lets first take a quick glance at the concept of Randomised algorithms in programming.
What is Randomised Algorithm?
An algorithm that takes help of random numbers to decide the upcoming/next action in its logic is called randomised algorithm. The fate of the entire algorithm depends on the random number generated.
There are basically two types of Randomises algorithms :
- Las Vegas algorithm : Allowed to return only true values
- Monte Carlo algorithm : Allowed to return wrong values but with small probability.
What is Probability?
The part of Mathematics that deals with finding the chance of the occurence of a random event is called prbability. For example , we have a coin , the probability of finding heads on tossing the coin is 0.5. Its general formula is :
P(X) = (No. of favourable outcomes) / (No. of possible outcomes)
1. Efficient Approach
Let's jump first to the Algorithm :
Step 1 : START
Step 2 : Assign value of first node to the result
result = head->value
Step 3 : Initialize n = 2
Step 4 : Now successively take every node starting from the second node
(a) Generate a random number from 1 to n for 1 based indexing and 0 to n-1 for 0 based indexing.
Suppose the generated number is j
(b) Suppose the number generated i.e. j is equal to 0 then just replace the result with value of current node
(c) Increment value of n by 1
(d) Move the current pointer to the next node
Step 5 : STOP
Now before jumping onto the implementation , let's first take a look at behind the scenes of the process of finding the probability of each element of the linked list :
Suppose there are n nodes in the given linked list. Now after applying the above mentioned concepts, the probability of each node being the result simply boils down to 1/n. Here is a simple formula for calculating the probability of each node being the required result :
Let's say the third last node is the required result. Now we have two scenarios : First that the third last node is the result and Second that the third last node is not the result.
Hence,
Probability that the third last node is the result is
= (probability that third last node overrides the result) * (probability that third last node doesn't override the result)
probability that third last node overrides the result = [(No. of favourable outcomes) / (No. of possible outcomes)] = 1 / n - 1
probability that third last node doesn't override the result = [(No. of favourable outcomes) / (No. of possible outcomes)] = n - 1 / n
Therefore,
Probability that the third last node is the result = [(1/(n-1)]*[(n-1)/n] = 1/n
Now this process is valid for each and every node in the given linked list,
now let's jump onto the implementation part.
Java implementation of the algorithm :
import java.util.*;
// Let's define the class for the linked list
class Opengenus_random_node {
private static Random generator = new Random();
static Node head;
// Method to generate the random number
static double randomGenerator() {
return generator.nextInt()*0.5;
}
/* Node class */
static class Node {
int value; // stores the integer type data of each node
Node next; // stores address of each node
// Constructor for creating a new node in the linked list
Node(int value) {
this.value = value;
next = null;
}
}
// function to print the random node from the linked list
void random_node(Node node) {
// Check if the list is empty
if (node == null) {
return;
}
randomGenerator();
// Initialize result as first node
int res = node.value; // for storing our required result
Node current_node = node;
int n;
for (n = 2; current_node != null; n++) {
if (Math.random() % n == 0) {
res = current_node.value;
}
// moving on to the next node
current_node = current_node.next;
}
System.out.println("Random node : " + res);
}
public static void main(String[] abc) {
Opengenus_random_node list = new Opengenus_random_node();
head = new Node(15);
head.next = new Node(0);
head.next.next = new Node(64);
head.next.next.next = new Node(13);
head.next.next.next.next = new Node(99);
list.random_node(head);
}
}
Output :
-
First execution :
Random node : 15 -
Second execution :
Random node : 99
2. Second Approach: Using auxillary array
Instead of using the above mentioned tedious method , we can use a simple method that takes use of arraylist and Math.random() functionality. First the linked list values will be stored in the arraylist and then values will be returned according to the index generated on the basis of the random number generated, that in turn will be obtained by the Math.random() function.
Now lets jump at our problem ,
Suppose there are N nodes in the linked list
Algorithm :
Step 1 : START
Step 2 : Create an arraylist of type integer
Step 3 : Declare an integer type variable for size and linked list type for head
Step 4 : We will use two methods, one for traversing through the linked list using while loop and also increase the size by 1
(a) Algorithms_random_node(head)
(b) run a while loop till null;
(c) add the value to arraylist;
(d) increase the size;
Step 5 : Now use another method for getting random values using Math.random() and return the value present in arraylist for the calculated index
Step 6 : Now in main() method we will simply insert nodes in the linked list and then call the appropriate method and then print the random node generated
Step 7 : STOP
Java implementation of the algorithm :
import java.util.ArrayList;
public class Algorithms_random_node {
ArrayList<Integer> list;
int size;
static ListNode head;
static class ListNode{
int val;
ListNode next;
ListNode(int val){
this.val = val;
}
}
public Algorithms_random_node(ListNode head) {
list = new ArrayList<>();
size = 0;
ListNode temp = head;
//Now using while loop to traverse through the linked list and
//go on adding values and increasing the size value by 1
while (temp != null) {
list.add(temp.val);
temp=temp.next;
size++;
}
}
public int getRandom() {
int index = (int)(Math.random()*size);
return list.get(index);
}
// Driver program to test above functions
public static void main(String[] args) {
head = new ListNode(15);
head.next = new ListNode(25);
head.next.next = new ListNode(4);
head.next.next.next = new ListNode(1);
head.next.next.next.next = new ListNode(78);
head.next.next.next.next.next = new ListNode(63);
Algorithms_random_node list = new Algorithms_random_node(head);
int random_num = list.getRandom();
System.out.println("Random Node : "+random_num);
}
}
Output :
-
First execution :
Random Node : 4 -
Second execution :
Random Node : 1 -
Third execution :
Random Node : 4
MCQs on Randomized alogrithms
1. Which of the following is a type of randomised alogrithm?
(A) New York algorithm
(B) Las Vegas algorithm
(C) Monte Carlo algorithm
(D) Colorado algorithm
Ans : B and C
2. Which function is used to generate random numbers in Java?
(A) Math.random()
(B) random()
(C) Math.random_num()
(D) random_num()
Ans : A
3. Randomised algorithm uses random bits as input inorder to achieve a _____________ good performance
(A) best case
(B) worst case
(C) average case
(D) none of the above
Ans : C
4. Which one of the following algorithm is fast in execution?
(A) Las Vegas algorithm
(B) Atlantic City algorithm
(C) Monte Carlo algorithm
(D) All of these
Ans : B
5. Which of the following is pobalistic algorithm?
(A) New York algorithm
(B) Las Vegas algorithm
(C) Monte Carlo algorithm
(D) Atlantic City algorithm
Ans : B , C and D
Thank you!
