交换 2 个排列的子序列的算法
Algorithm to swap subsequences of 2 permutations
给定 n 个元素（1 到 n）的 2 个无序排列，我需要检查是否可以使用以下交换方法从第一个排列到第二个排列：
选择一个包含 3 个元素的子序列，我们称它们为 (a,b,c)
您可以这样交换它们：(a,b,c) => (c,a,b)。你可以无限次使用这个方法
例如：对于输入{1,3,4,2}{4,3,2,1}是可能的
但它不适用于 {1,2,3,4,5,6} {6,5,4,3,2,1}
我的第一种方法是从第一个排列中取出第一个元素，在第二个排列中找到它，然后模拟交换直到第一个元素相同，然后对每个元素执行以下操作直到只有 3 个元素保持。那么很容易看出是否可以从第一个到达第二个。
但是时间复杂度是O(n^2)，我必须在O(n*log(n))或更少的时间内完成。
有什么办法吗？
让我们称 a[i] > a[j] 为 i < j 的情况为错位。请注意，如果元素是唯一的，则由交换 (a, b, c) -> (c, a, b) 引起的错位数量的变化是偶数。所以，这种排列成为可能的必要条件是错位数量（换位距离）的差异必须是偶数。
示例：
{1,2,3,4,5,6}：0 个错位，{6,5,4,3,2,1}：15 个错位。 15的差是奇数，这样的排列是不可能的。
{1,3,4,2}: 2个错位（3在2之前，4在2之前）
{4,3,2,1}: 6个错位。 4个错位相差偶数
缺少什么：我有点懒得正式证明这是一个充分条件，即所有偶数变化都是可能的。此外，这不适用于具有非唯一元素的集合 - 我猜想任何排列都是可能的。
要计算错位的数量，请检查 Kendall tau distance 算法。它需要一些调整，但会在 ~O(n log n) 中计算距离。
给定 n 个元素（1 到 n）的 2 个无序排列，我需要检查是否可以使用以下交换方法从第一个排列到第二个排列：
选择一个包含 3 个元素的子序列，我们称它们为 (a,b,c)
您可以这样交换它们：(a,b,c) => (c,a,b)。你可以无限次使用这个方法
例如：对于输入{1,3,4,2}{4,3,2,1}是可能的
但它不适用于 {1,2,3,4,5,6} {6,5,4,3,2,1}
我的第一种方法是从第一个排列中取出第一个元素，在第二个排列中找到它，然后模拟交换直到第一个元素相同，然后对每个元素执行以下操作直到只有 3 个元素保持。那么很容易看出是否可以从第一个到达第二个。
但是时间复杂度是O(n^2)，我必须在O(n*log(n))或更少的时间内完成。
有什么办法吗？
让我们称 a[i] > a[j] 为 i < j 的情况为错位。请注意，如果元素是唯一的，则由交换 (a, b, c) -> (c, a, b) 引起的错位数量的变化是偶数。所以，这种排列成为可能的必要条件是错位数量（换位距离）的差异必须是偶数。
示例：
{1,2,3,4,5,6}：0 个错位，{6,5,4,3,2,1}：15 个错位。 15的差是奇数，这样的排列是不可能的。
{1,3,4,2}: 2个错位（3在2之前，4在2之前）
{4,3,2,1}: 6个错位。 4个错位相差偶数
缺少什么：我有点懒得正式证明这是一个充分条件，即所有偶数变化都是可能的。此外，这不适用于具有非唯一元素的集合 - 我猜想任何排列都是可能的。
要计算错位的数量，请检查 Kendall tau distance 算法。它需要一些调整，但会在 ~O(n log n) 中计算距离。