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

Question

给定L不同元素的两个排列A和B，L是偶数的，让我们称这些置换为“对称的”（因为缺少更好的术语），如果存在n和{}，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

非正式地考虑

^{pr2}$

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

B = 0 5 6 3 4 1 2 7

现在，A和{}在上述意义上是“对称的”（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和{}？为了简单起见，让我们只考虑偶数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

实现既优雅又高效。在

breakintoelse: return结构确保函数在最快的时间点返回。它们还验证n和{}是否已设置为有效值，但在显式检查切片时似乎没有必要这样做。这些管路可以拆下而不会对正时产生明显影响。在

显式地比较切片也会在计算结果为False时短路。在

最初，我通过将b转换为a来检查是否存在置换：

^{pr2}$

但这比显式比较切片慢。让我知道，如果算法不能说明自己，我可以提供进一步的解释（甚至可以证明）为什么它工作，它是最小的。在

Answer 2

以下是问题的工作解决方案：

def isSymmetric(A, B):
    L = len(A) #assume equivalent to len(B), modifying this would be as simple as checking if len(A) != len(B), return []
    la = L//2 # half-list length
    Al = A[:la]
    Ar = A[la:]
    Bl = B[:la]
    Br = B[la:]
    for i in range(la):
        lai = la - i #just to reduce the number of computation we need to perform
        for j in range(1, lai + 1):
            k = lai - j #same here, reduce computation
            if Al[i] != Br[k] or Ar[k] != Bl[i]: #the key for efficient computation is here: do not proceed unnecessarily
                 continue
            n = i #written only for the sake of clarity. i is n, and we can use i directly
            m = i + j
            if A[n:m] == B[L-m:L-n] and B[n:m] == A[L-m:L-n]: #possibly symmetric
                if A[0:n] == B[0:n] and A[m:L-m] == B[m:L-m] and A[L-n:] == B[L-n:]:
                    return [n, m]
    return []

正如你所提到的，虽然这个想法看起来很简单，但实际上是一个相当棘手的想法。然而，一旦我们看到了模式，实现就很简单了。在

解决方案的中心思想是这样一行：

^{pr2}$

所有其他行要么直接从问题语句中翻译代码，要么进行优化以提高计算效率。在

---

要找到解决方案，需要几个步骤：

首先，我们需要将每个both listA和listB拆分为两个半列表（称为Al，Ar，Bl，和{}）。每个半列表将包含原始列表的一半成员：

^{3}$

---

其次，为了使评估有效，这里的目标是找到我称之为枢轴索引的东西，以确定列表（索引）中的位置是否值得评估，以检查列表是否对称。这个轴索引是找到一个有效的解决方案的中心思想。所以我会尽量详细说明一下：

考虑A列表的左半部分，假设您有一个这样的成员：

Al = [al1, al2, al3, al4, al5, al6]

我们可以想象对于上述列表，存在一个对应的索引列表，如下所示

Al  = [al1, al2, al3, al4, al5, al6]
iAl = [0,   1,   2,   3,   4,   5  ] #corresponding index list, added for explanation purpose

（注意：我之所以提到想象一个对应的索引列表是为了便于解释）

同样，我们可以想象其他三个列表可能有相似的索引列表。让我们分别将它们命名为iAr、iBl、和{}，它们的成员都与iAl相同。在

为了解决这个问题，列表的索引才是真正重要的。在

---

我的意思是：假设我们有两个参数：

1. 索引（让我们给它一个变量名i，我将使用符号^表示当前的i）
2. 长度（让我们给它一个变量名j，我将使用符号==来直观地表示它的长度值）

对于iAl中的索引元素的每个评估，则每个评估将意味着：

Given an index value i and length value of j in iAl, do something to determine if it is worth to check for symmetric qualifications starting from that index and with that length (Hence the name pivot index come).

现在，让我们以一个求值为例，当i = 0和j = 1时。评估的说明如下：

iAl = [0, 1, 2, 3, 4, 5]
       ^ <-- now evaluate this index (i) = 0
       == <-- now this has length (j) of 1

---

为了使那些索引i和长度j得到进一步的评估，那么对应的{}必须具有相同的相同的项目值，但长度不相同，但索引不相同

iBr = [0, 1, 2, 3, 4, 5]
                      ^ <-- must compare the value in this index to what is pointed by iAl
                      == <-- must evaluate with the same length = 1

例如，对于上述情况，这是两个列表Al-Br的一个可能的“对称”排列（稍后我们将考虑另两个列表Ar-Bl）：

Al = [0, x, x, x, x, x] #x means don't care for now
Br = [x, x, x, x, x, 0]

在这一刻，值得注意的是

It won't worth evaluating further if even the above condition is not true

这就是你使算法更有效的地方；也就是说，通过在所有可能的情况中只选择评估少数可能的情况。如何找到少数可能的病例？在

By trying to find relationship between indexes and lengths of the four lists. That is, for a given indexi and lengthj in a list (say Al), what must be the indexk in the counterpart list (in the case is Br). Length for the counterpart list need not be found because it is the same as in the list (that is j).

了解了这些之后，让我们进一步看看在评估过程中是否可以看到更多模式。在

---

现在考虑长度的影响（j）。例如，如果我们要从索引0求值，但是长度是2，那么与长度为1时相比，对应列表需要有不同的索引k

iAl = [0, 1, 2, 3, 4, 5]
       ^ <-- now evaluate this index (i) = 0
       ===== <-- now this has length (j) of 2

iBr = [0, 1, 2, 3, 4, 5]
                   ^ <-- must compare the value in this index to what is pointed by iAl
                   ===== <-- must evaluate with the same length = 2

或者，对于上面的例子，福克斯i = 0和y = 2真正重要的是：

# when i = 0 and y = 2
Al = [0, y, x, x, x, x] #x means don't care for now
Br = [x, x, x, x, 0, y] #y means to be checked later

请看一下，上面的模式与i = 0和y = 1时不同，在示例中，0值的索引位置发生了移动：

# when i = 0 and y = 1, k = 5
Al = [0, x, x, x, x, x] #x means don't care for now
Br = [x, x, x, x, x, 0]

# when i = 0 and y = 2, k = 4
Al = [0, y, x, x, x, x] #x means don't care for now
Br = [x, x, x, x, 0, y] #y means to be checked later

因此，长度偏移，其中必须检查对应列表的索引。在第一种情况下，当i = 0和y = 1，那么k = 5。但是在第二种情况下，当i = 0和{}时，k = 4。因此，当我们将一个固定的索引j（在本例中是0）的长度j更改为对应列表索引k时，我们发现了轴索引关系。在

---

现在，考虑长度固定的索引i对对应列表索引j的影响。例如，让我们将长度固定为y = 4，然后对于索引i = 0，我们有：

iAl = [0, 1, 2, 3, 4, 5]
       ^ <-- now evaluate this index (i) = 0
       ========== <-- now this has length (j) of 4

iAl = [0, 1, 2, 3, 4, 5]
          ^ <-- now evaluate this index (i) = 1
          ========== <-- now this has length (j) of 4

iAl = [0, 1, 2, 3, 4, 5]
             ^ <-- now evaluate this index (i) = 2
             ========== <-- now this has length (j) of 4

#And no more needed

在上面的例子中，可以看出，我们需要计算给定的i和j的可能性，但是如果索引i更改为长度相同的j = 4，则：

iAl = [0, 1, 2, 3, 4, 5]
          ^ <-- now evaluate this index (i) = 1
          ========== <-- now this has length (j) of 4

iAl = [0, 1, 2, 3, 4, 5]
             ^ <-- now evaluate this index (i) = 2
             ========== <-- now this has length (j) of 4

注意，我们只需要评估2的可能性。因此，指数的增加i减少了可能要评估的案例数量！在

---

在找到上述所有模式之后，我们几乎找到了使算法工作所需的所有基础。但要完成这一点，我们需要找到给定的Al-Br对中出现的索引与同一Ar-Bl对中的索引之间的关系。在

现在，我们实际上可以看到它们只是镜像我们在Al-Br对中发现的关系！在

（IMHO，这真是太美了！所以我认为“对称”排列这个词离事实并不遥远）

例如，如果我们用i = 0和y = 2来计算Al-Br对

Al = [0, y, x, x, x, x] #x means don't care for now
Br = [x, x, x, x, 0, y] #y means to be checked later

然后，为了使其对称，我们必须有相应的Ar-Bl：

Ar = [x, x, x, x, 3, y] #x means don't care for now
Bl = [3, y, x, x, x, x] #y means to be checked later

Al-Br对的索引是镜像（或对称于）Ar-Bl对的索引！在

---

因此，结合我们在上面找到的所有模式，我们现在可以找到用于评估Al、Ar、Bl、和{}的轴索引。在

We only need to check the values of the lists in the pivot index first. If the values of the lists in the pivot indexes of Al, Ar, Bl, and Br matches in the evaluationthen and only then we need to check for symmetric criteria (thus making the computation efficient!)

---

将上述所有知识放入代码中，下面是要检查对称性的for-loopPython代码：

for i in range(len(Al)): #for every index in the list
    lai = la - i #just simplification
    for j in range(1, lai + 1): #get the length from 1 to la - i + 1
        k = lai - j #get the mirror index
        if Al[i] != Br[k] or Ar[k] != Bl[i]: #if the value in the pivot indexes do not match
             continue #skip, no need to evaluate
        #at this point onwards, then the values in the pivot indexes match
        n = i #assign n
        m = i + j #assign m
        #test if the first two conditions for symmetric are passed
        if A[n:m] == B[L-m:L-n] and B[n:m] == A[L-m:L-n]: #possibly symmetric
            #if it passes, test the third condition for symmetric, the rests of the elements must stay in its place
            if A[0:n] == B[0:n] and A[m:L-m] == B[m:L-m] and A[L-n:] == B[L-n:]:                   
                return [n, m] #if all three conditions are passed, symmetric lists are found! return [n, m] immediately!
        #passing this but not outside of the loop means 
        #any of the 3 conditions to find symmetry are failed
        #though values in the pivot indexes match, simply continue
return [] #nothing can be found - asymmetric lists

这就是对称测试！在

（好吧，这是一个相当大的挑战，我要花相当长的时间才能弄清楚）

Answer 3

我试着为这个任务实现3种不同的算法。它们都具有O（N）时间复杂度，需要O（1）个额外的空间。有趣的事实：所有其他答案（目前已知）实现了其中的2个算法（尽管它们并不总是保持最佳的渐近时间/空间复杂度）。下面是每个算法的高级描述：

算法A

1. 比较列表，分组“不相等”的间隔，确保正好有两个这样的间隔（特别是当间隔在中间时）。在
2. 检查“非等间距”是否对称放置，其内容是否也“对称”。在

算法B

1. 比较列表的前半部分，猜测“要交换的间隔”在哪里。在
2. 检查这些间隔的内容是否“对称”。确保这些间隔之外的列表是相等的。在

算法C

1. 比较列表的前半部分以找到第一个不匹配的元素。在
2. 在第二个列表中找到第一个列表中不匹配的元素。这暗示了“要交换的间隔”的位置。在
3. 检查这些间隔的内容是否“对称”。确保这些间隔之外的列表是相等的。在

每种算法的步骤1有两种可选的实现：（1）使用itertools，和（2）使用普通循环（或列表理解）。itertools对于长列表是有效的，但是对于短列表则相对较慢。在

这是算法C，第一步是用itertools实现的。它看起来比其他两种算法更简单（在本文末尾）。而且它的速度非常快，即使对于短名单：

import itertools as it
import operator as op

def test_C(a, b):
    length = len(a)
    half = length // 2
    mismatches = it.imap(op.ne, a, b[:half]) # compare half-lists

    try:
        n = next(it.compress(it.count(), mismatches))
        nr = length - n
        mr = a.index(b[n], half, nr)
        m = length - mr
    except StopIteration: return None
    except ValueError: return None

    if a[n:m] == b[mr:nr] and b[n:m] == a[mr:nr] \
            and a[m:mr] == b[m:mr] and a[nr:] == b[nr:]:
        return (n, m)

---

这可以主要使用itertools来完成：

^{pr2}$

@j_random_hacker已经在OP评论中提供了该算法的高级描述。以下是一些细节：

从比较列表开始：

^{3}$

然后找出相等/不相等间隔之间的边界：

=  E N N E E N N E
B  _ * _ * _ * _ *

然后确定非相等元素的范围：

B  _ * _ * _ * _ *
    [1 : 3] [5 : 7]

然后检查是否正好有两个范围（特别是当两个范围在中间相交时），范围本身是对称的，它们的内容也是对称的。在

---

另一种选择是使用itertools只处理每个列表的一半。这使得算法更简单（也更快），因为不需要处理特殊情况：

def test_B(a, b):
    equals = it.imap(op.eq, a, b[:len(a) // 2]) # compare half-lists
    e1, e2 = it.tee(equals)
    l = it.chain(e1, [True])
    r = it.chain([True], e2)
    borders = it.imap(op.ne, l, r) # delimit equal/non-equal intervals
    ranges = list(it.islice(it.compress(it.count(), borders), 2))

    if len(ranges) != 2:
        return None

    n, m = ranges[0], ranges[1]
    nr, mr = len(a) - n, len(a) - m

    if a[n:m] == b[mr:nr] and b[n:m] == a[mr:nr] \
            and a[m:mr] == b[m:mr] and a[nr:] == b[nr:]:
        return (n, m)