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:
- Cuente el número de Nodes recorriendo la lista.
- 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
/* C program to randomly select a node from a singly linked list */ #include<stdio.h> #include<stdlib.h> #include <time.h> // Linked 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", result); } /* 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 code 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; }
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 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 resulte 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 the 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!
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