Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Selecting a random node from a list in C

Tags:

c

list

random

I have a list and I want to randomly select a node from it. As it's not an array I don't know in advance its length. Is there a way to select a node randomly (with uniform distribution) without having to scan the whole list (in the worst case) twice (i.e. to get its length and to reach the selected node after having randomly selected its position)?

Here's the code I use for my list:

struct mynode {
    in_addr_t paddr;
    struct mynode *prev, *next;
};

struct mylist {
    struct mynode *first, *last;
    char *name;
};
like image 257
Robb1 Avatar asked May 04 '17 09:05

Robb1


People also ask

How do you randomize a linked list?

Approach 1 (Using user-define method) Create a LinkedList. Store its elements in an array by the toArray() method. Shuffle the array elements. Use ListIterator on the LinkedList and traverse the LinkedList by next() method and store the shuffled data of the Array to the List simultaneously by set() method.

What is random node?

Let the count of nodes be n. To get a random node, we generate a random number from 0 to n-1, use this number as index in array and return the value at index. An alternate solution is to modify tree structure. We store count of children in every node.


1 Answers

As advised in the comments by joop and Ilja Everilä, I implemented the reservoir sampling in C.

struct mynode *select_mynode(struct mylist *list) {
    struct mynode *list_iter = list->first; // An iterator to scan the list
    struct mynode *sel_node = list_iter; // The node that will be selected
    int count = 2; // Temporary size of the list
    srand((unsigned int) time(NULL)); // Seed
    // Select a random element in O(n)
    while (list_iter->next != NULL) {
        if (rand() % count == (count - 1))
            sel_node = list_iter->next;
        list_iter = list_iter->next;
        count++;
    }
    return sel_node;
}

Note: for further information about random selection, see here.

like image 75
Robb1 Avatar answered Nov 15 '22 01:11

Robb1