arrays - 有界元素移动的重新排列

Question

我想根据以下条件重新排列(或置换)数组的元素:

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

然后我想有效地迭代所有这些重新排列。

生成重排的最快方法是什么？

我知道复杂度会低于 O((2k+1)^n)，我正在寻找此类算法的最有效实现。

我正在寻找一种解决方案，可以击败考虑每个排列并检查条件的朴素算法。

Answer 1

这是一个时间复杂度为 O(n P) 的算法，其中 P 是排列数。假设您要在每个排列上运行线性时间或更糟的东西，这是渐近最优的(尽管 Knuth 可能有话要说)。

生成所有排列的惯用递归算法是这样的。

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)

我即将进行的修改背后的想法是有效地修剪不产生输出的子树。假设每次递归调用的工作量为 O(1)，剩余的叶子用于支付其他调用。

首先，我们进行修改以跟踪逆排列。

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)

现在我们使用逆向剪枝。关键不变量将是有资格交换到索引 start 中的元素位于 start 和以下 k 个位置。一旦符合条件，元素将保持符合条件，直到被选中或直到 start 变得太大。倒数有助于我们避免后一种情况。

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)

你应该可以做到

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)

并查看生成的排列。