Given some input array
a = [a1, a2, ..., an] and a positive integer
k, shuffle the input array
a such that no entry is farther than
k from its initial position.
Given the array
[1, 2, 3, 4, 5, 6] and
k = 1, this means the entry
3 can be at following positions:
[*, 3, *, *, * ,*] [*, *, 3, *, *, *] (original position) [*, *, *, 3, *, *]
- Uniform randomness over all permissible permutations is not required, but
- You can assume the input array is limited to the range
[0, n-1], where
nis the length).
- all permissible permutations must have a nonzero probability of occurring.
- Instead of shuffling an input array, you can also just take
kand the length of the array
n+-1alternatively) as an input, and output a permutation in a suitable encoding (i.e as a list of indices etc). For this you can use 0 or 1 based indexing.
- Instead of
kyou can also take
k+1as an input if it is more suitable.
- You can assume that
0 < k < [length of array].
- Alternatively to sampling one random permutation you can also output all permissible permutations.