通过在 A 中选择一个集合然后反转该集合并将该集合插入到 A 的开头，将排列序列 A 转换为 B

Question

给定由 N 个数字组成的序列 A 和 B，这些数字是 1,2,3,...,N 的排列。在每一步中，你从左到右依次选择序列A中的一个集合S（被选中的数字将从A中移除），然后反转S并将S中的所有元素添加到序列A的开头。找到一种方法在 log2(n) 步中将 A 转换为 B。

输入：N <= 10^4（序列A、B的元素个数）和2个排列序列A、B。
输出：K（将 A 转换为 B 的步骤数）。接下来的 K 行是每一步选择的数字集 S。

示例：

输入：

5         // N
5 4 3 2 1 // A sequence 
2 5 1 3 4 // B sequence

输出：

2 
4 3 1
5 2

第 0 步：S = {}，A = {5, 4, 3, 2, 1}
第 1 步：S = {4, 3, 1}，A = {5, 2}。然后反转S => S = {1, 3, 4}。将 S 插入 A 的开头 => A = {1, 3, 4, 5, 2}
第 2 步：S = {5, 2}，A = {1, 3, 4}。然后反转S => S = {2, 5}。将 S 插入 A 的开头 => A = {2, 5, 1, 3, 4}

我的解决方案是使用回溯法在 log2(n) 步中考虑 S 的所有可能选择。但是，N 太大了，那么有更好的方法吗？谢谢。

Answer 1

对于组合 selecting/removing/prepending 的每个操作，您实际上是在相对于“枢轴”对元素进行排序，并保持顺序。考虑到这一点，您可以按倒序重复“排序”项目（我的意思是，您最后排序最高位），以实现真正的排序。

对于一个明确的例子，让我们举一个例子序列7 3 1 8。用它们在最终排序列表中的各自位置重写术语（将是 1 3 7 8），以获得 2 1 0 3.

7 -> 2  // 7 is at index 2 in the sorted array
3 -> 1  // 3 is at index 0 in the sorted array
1 -> 0  // so on
8 -> 3

这个新数组等同于原始数组 - 我们只是使用索引间接引用值（如果你仔细观察的话，我们有点重写未排序列表作为指向已排序列表的指针，而不是值).

现在，让我们用二进制写下这些新值：

如果我们要对这个列表进行排序，我们将首先按 MSB（最高有效位）排序，然后仅在必要时 对后续位 进行平分，直到我们在 LSB（最低有效位）。同样，我们可以先按 LSB 排序，然后在下一个最高有效位对 all 值排序，并以这种方式继续，直到我们到达 MSB。这将起作用，并正确地对列表进行排序，只要排序是 稳定的 ，也就是说，它不会改变被认为相等的元素的顺序。

让我们通过示例来解决这个问题：如果我们按 LSB 对这些进行排序，我们将得到

-然后在 MSB 上进行排序（但这次没有打破平局的逻辑），我们会得到：

-这是正确的排序结果。

还记得开头的“枢轴”分类笔记吗？这就是我们使用这种洞察力的地方。我们将对这个转换后的列表 2 1 0 3 进行排序，从 LSB 到 MSB，没有平局。为此，我们将以标准 <= 0.

为中心

这实际上就是我们在上一个示例中所做的，因此以 space 的名义，我不会再写出来，但请再次查看我们在每个步骤中所做的事情。我们将我们正在检查的位等于 0 的元素移到开头。首先，我们将 2 (10) 和 0 (00) 移动到开头，然后下一次迭代我们将 0 (00) 和 1 (01) 到开头。这正是您的挑战允许您执行的操作。

此外，因为我们的数字被缩减到它们的索引，最大值是 len(array)-1，位数是其中的 log2()，所以总的来说我们只需要做 log2(n) 步骤，正如您的问题陈述所要求的那样。

现在，这在实际代码中是什么样子的？

from itertools import product
from math import log2, ceil

nums = [5, 9, 1, 3, 2, 7]
size = ceil(log2(len(nums)-1))

bit_table = list(product([0, 1], repeat=size))
idx_table = {x: i for i, x in enumerate(sorted(nums))}

for bit_idx in range(size)[::-1]:
    subset_vals = [x for x in nums if bit_table[idx_table[x]][bit_idx] == 0]
    nums.sort(key=lambda x: bit_table[idx_table[x]][bit_idx])

    print(" ".join(map(str, subset_vals)))

如果需要，您当然可以使用按位运算符来完成位魔术 ((thing << bit_idx) & 1)，并且您可以 del 列表切片 + 前置而不是 .sort()ing ，这只是一个概念验证，以表明它确实有效。实际输出为：

1 3 7
1 7 9 2
1 2 3 5

通过在 A 中选择一个集合然后反转该集合并将该集合插入到 A 的开头，将排列序列 A 转换为 B

Convert the permutation sequence A to B by selecting a set in A then reversing that set and inserting that set at the beginning of A

algorithm

permutation

subset