Seleccione un Node aleatorio de una lista enlazada individualmente

Dada una lista enlazada individualmente, seleccione un Node aleatorio de la lista enlazada (la probabilidad de elegir un Node debe ser 1/N si hay N Nodes en la lista). Se le da un generador de números aleatorios.
A continuación se muestra una solución simple 

  1. Cuente el número de Nodes recorriendo la lista. 
  2. Recorra la lista nuevamente y seleccione cada Node con una probabilidad de 1/N. La selección se puede hacer generando un número aleatorio de 0 a Ni para el Node, y seleccionando el i-ésimo Node solo si el número generado es igual a 0 (o cualquier otro número fijo de 0 a Ni). 

Obtenemos probabilidades uniformes con los esquemas anteriores. 

i = 1, probability of selecting first node = 1/N
i = 2, probability of selecting second node =
                   [probability that first node is not selected] * 
                   [probability that second node is selected]
                  = ((N-1)/N)* 1/(N-1)
                  = 1/N  

De manera similar, la probabilidad de que otros seleccionen otros Nodes es 1/N.
La solución anterior requiere dos recorridos de la lista enlazada. 

¿Cómo seleccionar un Node aleatorio con solo un recorrido permitido?  
La idea es utilizar Reservoir Sampling . Los siguientes son los pasos. Esta es una versión más simple de Reservoir Sampling ya que necesitamos seleccionar solo una tecla en lugar de las teclas k. 

(1) Initialize result as first node
   result = head->key 
(2) Initialize n = 2
(3) Now one by one consider all nodes from 2nd node onward.
    (3.a) Generate a random number from 0 to n-1. 
         Let the generated random number is j.
    (3.b) If j is equal to 0 (we could choose other fixed number 
          between 0 to n-1), then replace result with current node.
    (3.c) n = n+1
    (3.d) current = current->next

A continuación se muestra la implementación del algoritmo anterior. 

C++

/* C++ program to randomly select a node from a singly
linked list */
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
#include<iostream>
using namespace std;
  
/* Link list node */
class Node
{
    public:
    int key;
    Node* next;
    void printRandom(Node*);
    void push(Node**, int);
      
};
  
// A reservoir sampling based function to print a
// random node from a linked list
void Node::printRandom(Node *head)
{
    // IF list is empty
    if (head == NULL)
    return;
  
    // Use a different seed value so that we don't get
    // same result each time we run this program
    srand(time(NULL));
  
    // Initialize result as first node
    int result = head->key;
  
    // Iterate from the (k+1)th element to nth element
    Node *current = head;
    int n;
    for (n = 2; current != NULL; n++)
    {
        // change result with probability 1/n
        if (rand() % n == 0)
        result = current->key;
  
        // Move to next node
        current = current->next;
    }
  
    cout<<"Randomly selected key is \n"<< result;
}
  
/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST */
  
/* A utility function to create a new node */
Node* newNode(int new_key)
{
    // allocate node 
    Node* new_node = (Node*) malloc(sizeof( Node));
  
    /// put in the key 
    new_node->key = new_key;
    new_node->next = NULL;
  
    return new_node;
}
  
/* A utility function to insert a node at the beginning
of linked list */
void Node:: push(Node** head_ref, int new_key)
{
    /* allocate node */
    Node* new_node = new Node;
  
    /* put in the key */
    new_node->key = new_key;
  
    /* link the old list off the new node */
    new_node->next = (*head_ref);
  
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
  
// Driver program to test above functions
int main()
{
    Node n1;
    Node *head = NULL;
    n1.push(&head, 5);
    n1.push(&head, 20);
    n1.push(&head, 4);
    n1.push(&head, 3);
    n1.push(&head, 30);
  
    n1.printRandom(head);
  
    return 0;
}
  
// This code is contributed by SoumikMondal

C

/* C program to randomly select a node from a singly
   linked list */
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
  
/* Link list node */
struct Node
{
    int key;
    struct Node* next;
};
  
// A reservoir sampling based function to print a
// random node from a linked list
void printRandom(struct Node *head)
{
    // IF list is empty
    if (head == NULL)
       return;
  
    // Use a different seed value so that we don't get
    // same result each time we run this program
    srand(time(NULL));
  
    // Initialize result as first node
    int result = head->key;
  
    // Iterate from the (k+1)th element to nth element
    struct Node *current = head;
    int n;
    for (n=2; current!=NULL; n++)
    {
        // change result with probability 1/n
        if (rand() % n == 0)
           result = current->key;
  
        // Move to next node
        current = current->next;
    }
  
    printf("Randomly selected key is %d\n", result);
}
  
/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST  */
  
/* A utility function to create a new node */
struct Node *newNode(int new_key)
{
    /* allocate node */
    struct Node* new_node =
        (struct Node*) malloc(sizeof(struct Node));
  
    /* put in the key  */
    new_node->key  = new_key;
    new_node->next =  NULL;
  
    return new_node;
}
  
  
/* A utility function to insert a node at the beginning
  of linked list */
void push(struct Node** head_ref, int new_key)
{
    /* allocate node */
    struct Node* new_node = new Node;
  
    /* put in the key  */
    new_node->key  = new_key;
  
    /* link the old list off the new node */
    new_node->next = (*head_ref);
  
    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}
  
  
// Driver program to test above functions
int main()
{
    struct Node *head = NULL;
    push(&head, 5);
    push(&head, 20);
    push(&head, 4);
    push(&head, 3);
    push(&head, 30);
  
    printRandom(head);
  
    return 0;
}

Java

// Java program to select a random node from singly linked list
  
import java.util.*;
  
// Linked List Class
class LinkedList {
  
    static Node head;  // head of list
  
    /* Node Class */
    static class Node {
  
        int data;
        Node next;
  
        // Constructor to create a new node
        Node(int d) {
            data = d;
            next = null;
        }
    }
  
    // A reservoir sampling based function to print a
    // random node from a linked list
    void printrandom(Node node) {
  
        // If list is empty
        if (node == null) {
            return;
        }
  
        // Use a different seed value so that we don't get
        // same result each time we run this program
        Math.abs(UUID.randomUUID().getMostSignificantBits());
  
        // Initialize result as first node
        int result = node.data;
  
        // Iterate from the (k+1)th element to nth element
        Node current = node;
        int n;
        for (n = 2; current != null; n++) {
  
            // change result with probability 1/n
            if (Math.random() % n == 0) {
                result = current.data;
            }
  
            // Move to next node
            current = current.next;
        }
  
        System.out.println("Randomly selected key is " + result);
    }
  
    // Driver program to test above functions
    public static void main(String[] args) {
  
        LinkedList list = new LinkedList();
        list.head = new Node(5);
        list.head.next = new Node(20);
        list.head.next.next = new Node(4);
        list.head.next.next.next = new Node(3);
        list.head.next.next.next.next = new Node(30);
  
        list.printrandom(head);
  
    }
}
  
// This code has been contributed by Mayank Jaiswal

Python3

# Python program to randomly select a node from singly
# linked list 
  
import random
  
# Node class 
class Node:
  
    # Constructor to initialize the node object
    def __init__(self, data):
        self.data= data
        self.next = None
  
class LinkedList:
  
    # Function to initialize head
    def __init__(self):
        self.head = None
  
    # A reservoir sampling based function to print a
    # random node from a linked list
    def printRandom(self):
  
        # If list is empty 
        if self.head is None:
            return
        if self.head and not self.head.next:
           print ("Randomly selected key is %d" %(self.head.data))
  
        # Use a different seed value so that we don't get 
        # same result each time we run this program
        random.seed()
  
        # Initialize result as first node
        result = self.head.data
  
        # Iterate from the (k+1)th element nth element
        # because we iterate from (k+1)th element, or 
        # the first node will be picked more easily 
        current = self.head.next 
        n = 2 
        while(current is not None):
              
            # change result with probability 1/n
            if (random.randrange(n) == 0 ):
                result = current.data 
  
            # Move to next node
            current = current.next
            n += 1
  
        print ("Randomly selected key is %d" %(result))
          
    # Function to insert a new node at the beginning
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
  
    # Utility function to print the LinkedList
    def printList(self):
        temp = self.head
        while(temp):
            print (temp.data,end=" ")
            temp = temp.next
  
  
# Driver program to test above function
llist = LinkedList()
llist.push(5)
llist.push(20)
llist.push(4)
llist.push(3)
llist.push(30)
llist.printRandom()
  
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program to select a random node 
// from singly linked list
using System;
      
// Linked List Class
public class LinkedList 
{
    Node head; // head of list
  
    /* Node Class */
    public class Node
    {
        public int data;
        public Node next;
  
        // Constructor to create a new node
        public Node(int d) 
        {
            data = d;
            next = null;
        }
    }
  
    // A reservoir sampling based function to print a
    // random node from a linked list
    void printrandom(Node node) 
    {
  
        // If list is empty
        if (node == null) 
        {
            return;
        }
  
        // Use a different seed value so that we don't get
        // same result each time we run this program
        //Math.abs(UUID.randomUUID().getMostSignificantBits());
  
        // Initialize result as first node
        int result = node.data;
  
        // Iterate from the (k+1)th element to nth element
        Node current = node;
        int n;
        for (n = 2; current != null; n++) 
        {
  
            // change result with probability 1/n
            if (new Random().Next() % n == 0) 
            {
                result = current.data;
            }
  
            // Move to next node
            current = current.next;
        }
  
        Console.WriteLine("Randomly selected key is " + 
                                               result);
    }
  
    // Driver Code
    public static void Main(String[] args)
    {
        LinkedList list = new LinkedList();
        list.head = new Node(5);
        list.head.next = new Node(20);
        list.head.next.next = new Node(4);
        list.head.next.next.next = new Node(3);
        list.head.next.next.next.next = new Node(30);
  
        list.printrandom(list.head);
    }
}
  
// This code is contributed by 29AjayKumar

Javascript

<script>
  
// Javascript program to select a random node 
// from singly linked list
  
 /* Node Class */
class Node
{
    constructor(d)
    {
        this.data=d;
        this.next = null;
    }
}
  
 // A reservoir sampling based function to print a
    // random node from a linked list
function printrandom(node)
{
    // If list is empty
        if (node == null) {
            return;
        }
    
        // Use a different seed value so that we don't get
        // same result each time we run this program
        //Math.abs(UUID.randomUUID().getMostSignificantBits());
    
        // Initialize result as first node
        let result = node.data;
    
        // Iterate from the (k+1)th element to nth element
        let current = node;
        let n;
        for (n = 2; current != null; n++) {
    
            // change result with probability 1/n
            if (Math.floor(Math.random()*n) == 0) {
                result = current.data;
            }
    
            // Move to next node
            current = current.next;
        }
    
        document.write("Randomly selected key is <br>" +
        result+"<br>");
}
  
// Driver program to test above functions
head = new Node(5);
head.next = new Node(20);
head.next.next = new Node(4);
head.next.next.next = new Node(3);
head.next.next.next.next = new Node(30);
  
printrandom(head);
  
// This code is contributed by rag2127
  
</script>
Producción

Randomly selected key is 
3

Complete Interview Preparation - GFG

Complejidad de tiempo: O (n), ya que estamos usando un bucle para atravesar n veces. Donde n es el número de Nodes en la lista enlazada.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.

Tenga en cuenta que el programa anterior se basa en el resultado de una función aleatoria y puede producir diferentes resultados.

¿Como funciona esto?  
Deje que haya un total de N Nodes en la lista. Es más fácil de entender desde el último Node.
La probabilidad de que el último Node sea resultado simplemente 1/N [Para el último o N’ésimo Node, generamos un número aleatorio entre 0 y N-1 y hacemos que el último Node sea el resultado si el número generado es 0 (o cualquier otro número fijo]
La probabilidad de que el penúltimo Node sea el resultado también debe ser 1/N. 

The probability that the second last node is result 
          = [Probability that the second last node replaces result] X 
            [Probability that the last node doesn't replace the result] 
          = [1 / (N-1)] * [(N-1)/N]
          = 1/N

De manera similar, podemos mostrar la probabilidad para el tercer último Node y otros Nodes.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *