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;
};
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.
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With