Permuting n elements by swapping each element by no more than k positions

Question

What I have is a vector (n = 4 in the example):

x = '0123';

What I want is a vector y of the same size of x and with the same elements as in x in different order:

y = ['0123'; '0132'; '0213'; '0231'; '0312'; '0321'; '1023'; '1032'; '1203'; '1302'; '2013'; '2031'; '2103'; '2301'];
y(ceil(rand * numel(y(:, 1))), :)

i.e. a permutation such that each element in y is allowed to randomly change no more than k positions with respect to its original position in x (k = 2 in the example). The probability distribution must be uniform (i.e. each permutation must be equally likely to occur).

An obvious but inefficient way to do it is of course to find a random unconstrained permutation and check ex post whether or not this happens to respect the constraint. For small vectors you can find all the permutations, delete those that are not allowed and randomly pick among the remaining ones. Any idea about how to do the same more efficiently, for example by actually swapping the elements?

Answer 1

I don't see any approach other than the rejection method that you mention. However, instead of listing all allowed permutations and then picking one, it's more efficient to avoid that listing. Thus, you can randomly generate a permutation, check if it's valid, and repeat if it's not:

x = '0123';
k = 2;

n = numel(x);
done = 0;
while ~done
    perm = randperm(n);
    done = all( abs(perm-(1:n)) <= k ); %// check condition
end
y = x(perm);

Answer 2

Generating all the permutations can be done easily using constraint programming. Here is a short model using MiniZinc for the above example (note that we assume that x will contain n different values here):

include "globals.mzn";

int: k = 2;
int: n = 4;
array[1..n] of int: x = [0, 1, 2, 3];
array[1..n] of var int: y;

constraint forall(i in 1..n) (
    y[i] in {x[i + offset] | offset in -min(k, i-1)..min(k, n-i)}
  );

constraint all_different(y);

solve :: int_search(y, input_order, indomain_min, complete)
  satisfy;

output [show(y)];

In most cases, constraint programming systems have the possibility to use a random search. However, this would not give you a uniform distribution of the results. Using CP will however generate all valid permutations more efficiently than the naive method (generate and test for validity).

If you need to generate a random permutation of your kind efficiently, I think that it would be possible to modify the standard Fisher-Yates shuffle to handle it directly. The standard algorithm uses the rest of the array to choose the next value from, and chooses the value with a probability distribution that is uniform. It should be possible to keep a list of only the currently valid choices, and to change the probability distribution of the values to match the desired output.