In Python, I would like to shuffle the list so that each element ends with no more than N elements from the beginning, where N is a constant. In addition, I would like it to be fair. That is, each permutation that satisfies this restriction should be equally probable (within the 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] will be valid, but [6, 4, 1, 3, 5, 2] will not, because 6 and 2 are too far from their launch location, etc.
Is there an easy way to do this in Python? If not, is there any existing algorithm that will do this? The pseudocode is fine, I can implement it in Python if necessary.
The execution time is not very important because I will run this shuffle on ~ 100 K elements once every few minutes, so I can wait a few seconds to start it if necessary.
source share