algorithm - 生成序列排列的函数，元素限制为 1 个相邻移动

Question

假设有一个长度为 n 的列表，其中包含字母 A - char(n)。我想找到每个字母只能相邻移动或保持原位的排列。所以对于每个 seq，有三个“集合”排列，向左循环，向右循环(列表被认为是循环的)，以及原始列表。我无法想出一种算法来处理列表中间可能发生的交换。主要是，要交换的字母配对如何跳过字母。 例如:列表的排列，其中 n = 3 [ABC、CAB、BCA、ACB、CBA、BAC] 此外，ABC 和 CAB 被认为是唯一的，尽管元素相对于彼此具有相同的位置。主要是寻找算法而不是任何特定的语言。 基本规则是元素最多可以远离其在列表中的原始位置 1 个位置。

Answer 1

我将勾勒出一个高效的枚举策略。

首先让我们解决没有回绕的更简单的问题。最左边的元素有两种可能性。它要么留在原地，要么向右移动。如果它向右移动，那么它所取代的元素必须向左移动。我们可以递归地枚举其余排列的可能性。

# this code is for the simpler problem, without wraparound
# the algorithm for the problem with wraparound is described in prose below

def perms_line(lst, j):
    if len(lst) - j < 2:
        print(lst)
    else:
        perms_line(lst, j + 1)
        lst[j], lst[j + 1] = lst[j + 1], lst[j]
        perms_line(lst, j + 2)
        lst[j], lst[j + 1] = lst[j + 1], lst[j]

perms_line([1, 2, 3, 4, 5], 0)

现在让我们考虑环绕。如果两个连续的元素向右移动，则每个元素都必须向右移动。如果两个连续的元素向左移动，则每个元素都必须向左移动。分别处理这些异常排列。

首先，考虑最左边的元素。它要么保持不变，要么与其右侧的元素交换，要么与最右边的元素交换。对于这三种可能性中的每一种(注意:如果 n = 2 则有两种，如果 n = 1 则只有一种)，对排列的其余部分使用无环绕枚举策略。我将继续编写代码，因为需要一些操作才能正确完成。