Rearrangement with bounded element movement

Question

I want to rearrange (or permute) the elements of an array, by the condition that:

Each element should not move more than k position from its original position

Then I want to iterate over all such rearrangement efficiently.

What is the fastest way to generate the rearrangement?

I understand that the complexity would be less than O((2k+1)^n), I'm looking for the most efficient implementation of such algorithm.

I'm looking for a solution that can beat the naive algorithm which considers every permutation and do a check on the condition.

Answer 1

Here's a time O(n P)-algorithm, where P is the number of permutations. Assuming that you're going to run something linear-time or worse on each permutation, this is asymptotically optimal (though Knuth might have something to say about it).

The customary recursive algorithm for generating all permutations is this.

def swap(array, i, j):
    array[i], array[j] = array[j], array[i]

def perms(array, start=0):
    if start >= len(array):
        print(array)
    else:
        for i in range(start, len(array)):
            swap(array, start, i)
            perms(array, start + 1)
            swap(array, start, i)

The idea behind the modification that I'm about to make is to prune efficiently the subtrees that generate no output. Assuming that the work per recursive call is O(1), the remaining leaves pay for the other invocations.

First we make modifications to track the inverse permutation.

def swap(array, indices, inverse, i, j):
    array[i], array[j] = array[j], array[i]
    indices[i], indices[j] = indices[j], indices[i]
    inverse[indices[i]] = i
    inverse[indices[j]] = j

def perms(array, indices, inverse, start=0):
    if start >= len(array):
        print(array)
    else:
        for i in range(start, len(array)):
            swap(array, indices, inverse, start, i)
            perms(array, indices, inverse, start + 1)
            swap(array, indices, inverse, start, i)

Now we use the inverse to prune. The key invariant will be that the elements eligible to be swapped into index start are in start and the following k locations. Once eligible, an element remains eligible until selected or until start becomes too large. The inverse helps us avoid the latter condition.

def perms(array, indices, inverse, k, start=0):
    if start >= len(array):
        print(array)
    elif start - k >= 0 and inverse[start - k] >= start:
        i = inverse[start - k]
        swap(array, indices, inverse, start, i)
        perms(array, indices, inverse, k, start + 1)
        swap(array, indices, inverse, start, i)
    else:
        for i in range(start, min(start + k + 1, len(array))):
            swap(array, indices, inverse, start, i)
            perms(array, indices, inverse, k, start + 1)
            swap(array, indices, inverse, start, i)

You should be able to do

n = 8   # for example
k = 3   # for example
array = list(range(n))
indices = list(range(n))
inverse = list(range(n))
perms(array, indices, inverse, k)

and see the resulting permutations.