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

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是三角数.

我用这段代码来测试你的答案.

赏金更新:这里有很多优秀的答案.@Jared Goguen的解决方案似乎是最快的.

最后时间:

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 []

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

解决方案的核心思想是这一行:

if Al[i] != Br[k] or Ar[k] != Bl[i]: #the key for efficient computation is here: do not proceed unnecessarily

所有其他行只是问题陈述中的直接代码转换或为更有效的计算而进行的优化.

为了找到解决方案,涉及的步骤很少:

首先,我们需要将每个列表都拆分A和列表B分为两半列表(称为Al,Ar,Bl,和Br).每个半列表将包含原始列表的一半成员:

Al = A[:la]
Ar = A[la:]
Bl = B[:la]
Br = B[la:]

其次,为了使评估有效,这里的目标是找到我所谓的枢轴索引来决定列表(索引)中的位置是否值得评估,以检查列表是否对称.此分支索引是找到有效解决方案的核心思想.所以我会尝试详细说明一下:

考虑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以及iBr分别和它们都具有相同的成员iAl.

这是列表的索引,这对我们来说真正重要 - 为了解决问题.

这就是我的意思:假设我们有两个参数:

1. index(让我们给它一个变量名i,我会用^当前的符号i)
2. length(让我们给它一个变量名j,我会用符号==直观地表示它的长度值)

每个评价的的指标在元素iAl-那么每个评估将意味着:

给定in 的索引值i和长度值,做一些事情以确定是否值得检查从该索引开始并具有该长度的对称限定 (因此名称pivot index来).jiAl

现在,让我们举一个实例评估时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必须具有相同的项目值,具有相同的 长度但是在不同的索引上(让我们将其命名为索引 k)

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]

此刻,值得注意的是

它不会值得进一步评估,如果即使上述条件不成立

这就是让算法更有效的地方 ; 也就是说,通过有选择地仅评估所有可能情况中的少数可能情况.如何找到几个可能的案例？

通过尝试查找索引和四个列表的长度之间的关系.也就是说,对于一个给定的指标 i和长度 j在列表中(比如说Al),要做就要做到指数 k在对应 列表(在的情况下Br).无需找到对应列表的长度,因为它与列表中的长度相同(即j).

知道了这一点,现在让我们继续看看我们是否可以在评估过程中看到更多的模式.

现在考虑一下length(j)的效果.例如,如果我们要从索引 进行评估0,但是长度是2那么对应列表需要评估不同的索引而 k不是长度是1

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和y = 1,然后k = 4.因此,当我们将固定索引(在本例中为)的长度更改为对应列表索引时,我们找到了轴索引关系. j i0 k

现在,考虑具有固定长度的索引 对应列表索引的影响.例如,让我们将长度固定为,然后对于索引,我们有:i j ky = 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

在上面的例子中,可以看出,我们需要评估3种为给定的可能性i和j,但如果索引 i被改变为1具有相同的长度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

请注意,我们只需要评估两种可能性.因此,索引 的增加i减少了要评估的可能案例的数量!

通过上述所有模式,我们几乎找到了使算法运行所需的所有基础.但要完成这一点,我们需要找到之间的关系指标,其出现在Al-Br对给定一个[i, j] => [k, j]与索引中Ar-Bl对为同一[i, j].

现在,我们实际上可以看到它们只是反映了我们在Al-Br对中发现的关系!

(恕我直言,这真的很漂亮!因此我认为术语"对称"排列与真相并不遥远)

例如,如果我们Al-Br使用i = 0和评估了以下对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

然后,为了使它对称,我们必须有相应的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,和Br.

我们只需要首先检查数据透视索引中的列表值 .如果在列表的价值支点指标的Al,Ar,Bl,并Br 在比赛的评价 ,然后才把我们需要检查是否对称标准(从而使计算效率!)

将上述所有知识放入代码中,以下是for-loop检查对称性的结果Python代码:

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 2

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

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

实现既优雅又高效。

intobreak结构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

但这比显式比较切片要慢。让我知道该算法是否不言自明，我可以提供进一步的解释（甚至可能是证据）来说明它为何有效且最小。