Programa C++ para seleccionar 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 probabilidad 1/N. La selección se puede hacer generando un número aleatorio de 0 a Ni para el i-ésimo 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, las probabilidades de que otros seleccionen otros Nodes son 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 k teclas.

(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.
    (a) Generate a random number from 0 to n-1. 
        Let the generated random number is j.
    (b) If j is equal to 0 (we could choose other fixed numbers 
        between 0 to n-1), then replace result with the current node.
    (c) n = n+1
    (d) current = current->next

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

/* 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 " << 
             result;
}
  
/* 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 code
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

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

¿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 el último Node como 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 y último ^Node y otros Nodes.
¡ Consulte el artículo completo sobre Seleccionar un Node aleatorio de una lista de enlaces únicos para obtener más detalles!