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.
Python
# 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 linked # LinkedList def printList(self): temp = self.head while(temp): print temp.data, temp = temp.next # Driver code 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)
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 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 número]
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!
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