7

In Python, I would like to shuffle a list, in such a way that each element ends up no more than N elements away from where it started, where N is a constant. Also, I would like this to be fair. That is, every permutation that satisfies this constraint should be equally likely (within practical limits of random number generators).

For example, if N is 3, and the input is [1, 2, 3, 4, 5, 6], then the result [2, 1, 3, 6, 4, 5] would be valid, but [6, 4, 1, 3, 5, 2] would not be, because 6 and 2 are too far away from their starting location.

Is there an easy way to do this in Python? If not, is there some existing algorithm which will do this? Pseudocode is fine, I can implement it in Python if necessary.

Runtime is not incredibly important, because I will only run this shuffle on ~100k elements once every few minutes, so I can stand to wait a few seconds for it to run, if necessary.

ItsAmy
  • 844
  • 1
  • 6
  • 20
  • @Vallentin: no they can move afaik N places to the left, and N to the right at most. – Willem Van Onsem Mar 23 '17 at 16:39
  • The prior art seems to consider the _number_ of transpositions total, not the sum of transpositions encountered by any given element. – Josh Lee Mar 23 '17 at 16:40
  • @Vallentin No. For each element, the index it ends up at minus its original index should be less than (or equal to) N. – ItsAmy Mar 23 '17 at 16:41
  • 2
    I've answered a similar question [here](http://stackoverflow.com/questions/30747690/controlling-distance-of-shuffling). This seems to be a pretty hard problem. I would have liked to put more work into the random walk approach, but I don't know how to perform the analysis necessary to set appropriate stopping conditions. – user2357112 Mar 23 '17 at 16:42
  • @user2357112 Oh man, is this going to turn out to be one of those programming questions that turns out to be way harder than it seems like it should be? – ItsAmy Mar 23 '17 at 16:44
  • @ItsTimaiFool: If N is large, then yes. If N is small, it's not too bad, but it's still easy to get wrong. – user2357112 Mar 23 '17 at 16:45
  • @user2357112 Also, it turns out that that question is identical to mine, so maybe this should be marked as a duplicate. – ItsAmy Mar 23 '17 at 16:49

0 Answers0