یک لیست پیوندی مجرد داده شده است. هدف انتخاب یک گره تصادفی از لیست پیوندی است. اگر فرض شود که N گره در لیست وجود دارد، احتمال انتخاب شدن یک گره، باید یک اِنُم (یک به روی N) باشد. فرض می‌شود که بدین منظور، یک انتخاب کننده عدد تصادفی نیز در اختیار کاربر قرار گرفته است. یک راهکار ساده برای انجام این کار، در ادامه بیان شده است.

1. شمارش تعداد گره‌ها با پیمایش لیست
2. پیمایش مجدد لیست و انتخاب هر گره با احتمال یک به روی N. انتخاب را می‌توان با تولید اعداد تصادفی از ۰ تا N-i برای گره iاُم انجام داد و iاُمین گره را تنها در صورتی انتخاب کرد که عدد تولید شده برابر با ۰ باشد (یا هر عدد ثابت دیگری بین ۰ تا N-i).

با استفاده از شمای بالا، توزیع احتمال یکنواخت حاصل می‌شود.

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)
                  = ۱/N

به طور مشابه، احتمال انتخاب دیگر گره‌ها نیز یک به روی N است. راهکار بالا، نیازمند دو پیمایش در لیست پیوندی است. پرسشی که اکنون مطرح می‌شود این است که چگونه می‌توان یک گره تصادفی را تنها با یک پیمایش انتخاب کرد.

در پاسخ به این پرسش باید گفت که یکی از راهکارهای قابل استفاده برای انجام این کار، «نمونه‌برداری رزرویر» (Reservoir Sampling) است. در ادامه، گام‌های لازم برای این نوع از نمونه‌برداری، ارائه شده است. آنچه در ادامه آمده، یک نسخه ساده شده از این نوع از نمونه‌برداری محسوب می‌شود؛ زیرا در اینجا فقط نیاز به انتخاب یک کلید به جای k کلید است.

1. مقدار دهی اولیه نتیجه با اولین گره به صورت result = head->key
2. مقداردهی اولیه n = 2
3. اکنون، یک به یک همه گره‌ها از دومین گره در نظر گرفته می‌شوند:
   1. تولید یک عدد تصادفی از ۰ تا n-1. فرض می‌شود عدد تصادفی تولید شده j است.
   2. اگر j برابر با ۰ است (می‌تواند عدد ثابت دیگری را بین ۰ تا n-1 انتخاب کرد)، نتیجه را با گره کنونی جایگزین کن.
   3. n = n+1
   4. current = current->next

در ادامه، پیاده‌سازی روش بالا  در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «سی» (C)، «جاوا» (Java)، «پایتون» (Python) و «سی‌شارپ» (#C) انجام شده است.

برنامه انتخاب یک گره تصادفی از لیست پیوندی در ++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 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

برنامه انتخاب یک گره تصادفی از لیست پیوندی در پایتون

# 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 linkd 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 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

شایان توجه است که برنامه بالا بر مبنای خروجی یک تابع تصادفی است و ممکن است طی اجراهای مختلف، خروجی‌های متفاوتی داشته باشد.

توضیحاتی پیرامون روش کار کدهای بالا

فرض می‌شود که لیست پیوندی، به طور کلی N گره دارد. برای درک ساده‌تر موضوع، روش کار از آخرین گره شرح داده می‌شود. احتمال آنکه آخرین گره نتیجه باشد، یک به روی N است (برای آخرین گره یا گره Nاُم، یک عدد تصادفی بین ۰ تا N-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] 
          = [۱ / (N-1)] * [(N-1)/N]
          = ۱/N

به طور مشابه، می‌توان نشان داد که احتمال برای سومین گره از آخر و دیگر گره‌ها نیز به همین صورت است.

منبع [+]