StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PORandomly permute N first elements of a singly linked list
text
Body
copied!<p>I have to permute N first elements of a singly linked list of length n, randomly. Each element is defined as:</p> <pre><code>typedef struct E_s { struct E_s *next; }E_t; </code></pre> <p>I have a root element and I can traverse the whole linked list of size n. What is the most efficient technique to permute only N first elements (starting from root) randomly?</p> <p>So, given a->b->c->d->e->f->...x->y->z I need to make smth. like f->a->e->c->b->...x->y->z</p> <p>My specific case: </p> <ul> <li>n-N is about 20% relative to n</li> <li>I have limited RAM resources, the best algorithm should make it in place</li> <li>I have to do it in a loop, in many iterations, so the speed does matter</li> <li>The ideal randomness (uniform distribution) is not required, it's Ok if it's "almost" random</li> <li>Before making permutations, I traverse the N elements already (for other needs), so maybe I could use this for permutations as well</li> </ul> <p>UPDATE: I found <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V0F-45FKW7V-6B&_user=10&_coverDate=10%2F05%2F1992&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_searchStrId=1576191476&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=53029a9616acb1e9e90017e288d882ef&searchtype=a">this paper</a>. It states it presents an algorithm of O(log n) stack space and expected O(n log n) time. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload