StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>It sounds like you’re not too picky about having an equal probability for each possible output. One simple solution might be to do the equivalent of <code>n</code> passes of bubble sort, but rather than sorting the elements, just randomly choose whether or not to exchange the two elements at each step. This approach lets you do the randomization in place, too. You could do something like:</p> <pre><code>import random def shuffle_list(list, n): for ipass in xrange(n): for ielt in xrange(len(list) - 1): if random.randrange(2): temp = list[ielt] list[ielt] = list[ielt + 1] list[ielt + 1] = temp </code></pre> <p><strong>EDIT:</strong> Sorry, I should have thought about this more. The approach I described doesn’t work — in the very first pass, there’s a nonzero probability of the first element bubbling all the way to the end of the list. Somehow I missed that.</p> <p>I guess I don’t really have an answer now, but here’s an idea at least: Assign each element in the original list a proxy value equal to <code>ii + random.uniform(-n/2., n/2.)</code>, where <code>ii</code> is the element's index in the original list; then sort the original list based on this proxy value. Then, the earliest that element <code>ii</code> can appear in the final list is position <code>ii-n</code>: this would only happen if element received proxy value <code>ii-n/2.</code> and each element starting with element <code>ii-n</code> received a proxy value of at least <code>ii-n/2.</code>. Same argument for the upper bound.</p> <p>In practice, you’d want to use a slightly wider range, probably something like <code>random.uniform(-n/2. - 0.49, n/2. + 0.5)</code>. I haven’t gone through this math carefully yet, but I think this maintains the distance constraint. I’m also not totally sure what the final distribution of possible lists will be. @Basel, I think you’re right about the original suggestion, it seems more likely to have each element move a small amount rather than a large amount. I think this solution should be better, but I can’t swear to that. :-)</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