StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POShuffling a list while constraining the range of element shift
text
Body
copied!<p>Randomly <a href="http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle" rel="nofollow">shuffling</a> an array can be easily solved. I want to do a shuffle but with the added restriction that the shift in any element is constrained within a range. So if the max allowed shift <code>= n</code>, no element can be moved more than <code>n</code> steps in either direction as a result of the shuffle. </p> <p>So given this array, and n=3: </p> <pre><code>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] </code></pre> <p>this would be a valid shuffle:</p> <pre><code>[2, 3, 4, 0, 1, 6, 5, 8, 9, 7] </code></pre> <p>while these would be invalid:</p> <pre><code>[2, 3, 4, 7, 1, 6, 5, 8, 9, 0] [2, 3, 4, 6, 1, 7, 5, 8, 9, 0] </code></pre> <p>(notice that the range is not rotational)</p> <p>We are looking for a simple and efficient way to achieve this. It is preferred to do it in-place, but using a second array is ok if it provides a good solution.</p> <p>A naive starter solution would be, using a second array:</p> <pre><code>for element in array1: get legal index range filter out indexes already filled select random index i from filtered range array20[i] = element </code></pre> <p><strong>Edit</strong>:</p> <p>This is regarding the probability distortion issue raised by @ruakh if the algorithm is to process terminal element(s) first with equal probability:</p> <p>I thought for a first glance that the probability variance will diminish with increasing array size, but that doesn't seem to be the case. Some quick tests below (I concocted this in haste, so could have errors). As the distortion in probability is big I don't think it's acceptable as a general case, but for my own application I can live with it as I said in the comment.</p> <pre><code>import itertools n = 2 def test(arlen): ar = range(arlen) lst = list(itertools.permutations(ar)) flst = [l for l in lst if not illegal(l)] print 'array length', arlen print 'total perms: ', len(lst) print 'legal perms: ', len(flst) frst = [0] * (n+1) for l in flst: frst[l[0]] +=1 print 'distribution of first element: ',frst def illegal(l): for i in range(len(l)): if abs(l[i]-i)>n: return True if __name__=="__main__": arlen = range(4,10) for ln in arlen: test(ln) ------------ n=2 array length 4 total perms: 24 legal perms: 14 distribution of first element: [6, 4, 4] array length 5 total perms: 120 legal perms: 31 distribution of first element: [14, 10, 7] array length 6 total perms: 720 legal perms: 73 distribution of first element: [31, 24, 18] array length 7 total perms: 5040 legal perms: 172 distribution of first element: [73, 55, 44] array length 8 total perms: 40320 legal perms: 400 distribution of first element: [172, 128, 100] array length 9 total perms: 362880 legal perms: 932 distribution of first element: [400, 300, 232] ------------ n=4 array length 4 total perms: 24 legal perms: 24 distribution of first element: [6, 6, 6, 6, 0] array length 5 total perms: 120 legal perms: 120 distribution of first element: [24, 24, 24, 24, 24] array length 6 total perms: 720 legal perms: 504 distribution of first element: [120, 96, 96, 96, 96] array length 7 total perms: 5040 legal perms: 1902 distribution of first element: [504, 408, 330, 330, 330] array length 8 total perms: 40320 legal perms: 6902 distribution of first element: [1902, 1572, 1296, 1066, 1066] array length 9 total perms: 362880 legal perms: 25231 distribution of first element: [6902, 5836, 4916, 4126, 3451] </code></pre>

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