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

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 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 index i and length j in a list (say Al), what must be the index k 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 evaluation then 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

这就是对称测试！在

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