python - 如何检查两个排列是否对称？

Question

给定 A 不同元素的两个排列 B 和 L ， L 是偶数，让我们称这些排列为“对称”(因为缺少更好的术语)，如果存在 n 和 m ，则 m > n 如(在 python 符号中):

 - A[n:m] == B[L-m:L-n]
 - B[n:m] == A[L-m:L-n]
 - all other elements are in place

非正式地，考虑

A = 0 1 2 3 4 5 6 7

取任何一部分，例如 1 2 。它从第二个索引开始，长度为 2。现在取一个与其对称的切片:它在倒数第二个索引处结束，也是 2 个字符长，所以它是 5 6 。交换这些切片给出

B = 0 5 6 3 4 1 2 7

现在， A 和 B 在上述意义上是“对称的”( n=1, m=3 )。另一方面

A = 0 1 2 3 4 5 6 7
B = 1 0 2 3 4 5 7 6

不是“对称的”(不存在具有上述属性的 n,m)。
如何在python中编写一个算法来查找两个给定的排列(=列表)是否是“对称的”，如果是，则找到 n 和 m ？为简单起见，让我们只考虑偶数 L (因为可以通过消除中间固定元素将奇数情况简单地减少为偶数情况)并假设正确的输入( set(A)==set(B), len(set(A))==len(A) )。
(我对所有可能的对称性进行暴力破解没有问题，但正在寻找比这更智能、更快的东西)。
有趣的事实:给定 L 的对称排列数是 Triangular number 。
我使用 this code 来测试你的答案。
赏金更新:这里有很多优秀的答案。 @Jared Goguen's solution 似乎是最快的。
最终时间:

testing 0123456789 L= 10
    test_alexis ok in 15.4252s
    test_evgeny_kluev_A ok in 30.3875s
    test_evgeny_kluev_B ok in 27.1382s
    test_evgeny_kluev_C ok in 14.8131s
    test_ian ok in 26.8318s
    test_jared_goguen ok in 10.0999s
    test_jason_herbburn ok in 21.3870s
    test_tom_karzes ok in 27.9769s

Answer 1

我重写了代码，没有一些复杂性(和错误)。

def test_o_o(a, b):

    L = len(a)
    H = L//2
    n, m = 0, H-1

    # find the first difference in the left-side
    while n < H:
        if a[n] != b[n]: break
        n += 1
    else: return

    # find the last difference in the left-side
    while m > -1:
        if a[m] != b[m]: break 
        m -= 1
    else: return

    # for slicing, we want end_index+1
    m += 1

    # compare each slice for equality
    # order: beginning, block 1, block 2, middle, end
    if (a[0:n] == b[0:n] and \
        a[n:m] == b[L-m:L-n] and \
        b[n:m] == a[L-m:L-n] and \
        a[m:L-m] == b[m:L-m] and \
        a[L-n:L] == b[L-n:L]):

        return n, m

实现既优雅又高效。
break进入 else: return结构确保函数在尽可能快的点返回。他们还验证了 n和 m已设置为有效值，但在显式检查切片时似乎没有必要这样做。可以删除这些线，而不会对时序产生明显影响。

一旦评估为 False，显式比较切片也会短路。 .

最初，我通过转换 b 来检查是否存在排列。进入 a :

b = b[:]
b[n:m], b[L-m:L-n] = b[L-m:L-n], b[n:m]
if a == b:
   return n, m

但这比明确比较切片要慢。让我知道算法是否不言自明，我可以提供进一步的解释(甚至可能是证据)，说明它为什么有效并且是最小的。