使用 Python 实现序列的最小错排

排列组合学中的错排是指一个排列，其中没有一个元素出现在其原始位置。例如，对于序列 [1, 2, 3, 4]，错排会是 [2, 1, 4, 3]，因为没有一个元素在其原始位置。

错排在数学、软件工程和密码学中的应用很有趣。找到给定序列的最小错排是一个常见问题。在这里，我们将探讨如何使用 Python 来确定序列的最小错排。

输入

输出

2 1 4 3 6 5 8 7

说明

在代码的第一部分，我们定义了一个名为 generate_derangement 的函数，该函数接受整数 N 作为输入。此函数负责生成从 1 到 N 的整数序列的最小错排。

我们首先初始化一个长度为 (N + 1) 的空列表 P 来表示序列。我们使用循环将 1 到 N 的整数填充到 P 中，从而正确创建整数序列。

接下来，我们初始化另一个与 P 长度相同的空列表 D 来表示错排。错排将基于序列 P 进行构建。

然后，我们进入一个以 2 为步长从 1 迭代到 N 的循环。此循环用于通过交换 P 中的相邻元素来构建错排，以确保没有元素出现在其原始位置。

循环内部有两种情况：

• 如果 i 等于 N，这意味着我们正在处理最后一个元素。在这种情况下，我们交换 P 的最后两个元素，以确保最后一个元素不在其原始位置。我们通过将 P[N - 1] 的值赋给 D[N] 和 P[N] 的值赋给 D[N - 1] 来做到这一点。
• 如果 i 不等于 N，我们交换索引 i 处的当前元素和索引 i + 1 处的下一个元素。这确保了除最后一个元素之外的所有元素都不在其原始位置。

最后，我们遍历 D 列表并打印错排的元素，元素之间用空格分隔。

代码末尾的 if __name__ == '__main__': 块用于在脚本作为主程序运行时执行 generate_derangement 函数。在这种情况下，它会为 N = 8 生成最小错排并打印出来。

为了将最低有效元素（最小索引位置）移动到更有效的位置，我们将使用最小堆。我们将保留错排属性，同时执行此算法。

调用函数时，我们将使用提供的 sorted_sequence 作为参数。我们的输出将是最小错排序列列表，该列表与 sorted_sequence 列表没有任何共享元素。

输入

输出

[2, 1, 4, 3, 6, 7, 5]