如何检查两个列表是否在Python中是循环相同的

问题:

例如,我有列表:

a[0] = [1, 1, 1, 0, 0]
a[1] = [1, 1, 0, 0, 1]
a[2] = [0, 1, 1, 1, 0]
# and so on

他们似乎是不同的,但如果假设开始和结束是连接的,那么它们是circularly相同的。
问题是,我的每个列表的长度为55,只包含三个和52个零。没有圆形条件,有26,235(55选3)清单。然而,如果条件“循环”存在,则存在大量循环相同的列表
目前我通过以下方式检查循环身份:

def is_dup(a, b):
    for i in range(len(a)):
        if a == list(numpy.roll(b, i)): # shift b circularly by i
            return True
    return False

该功能在最坏的情况下需要55次循环移位操作。并有26,235个列表进行比较。总之,我需要55 * 26,235 *(26,235 – 1)/ 2 = 18,926,847,225计算。大约将近20吉加!
有没有什么好办法用较少的计算呢?或支持circular的任何数据类型

回答:

首先,这可以在列表的长度方面在O(n)中完成
您可以注意到,如果您将复制您的列表2次([1, 2, 3])将是[1, 2, 3, 1, 2, 3],那么您的新列表将一定会保留所有可能的循环列表。
所以你需要的是检查你正在搜索的列表是否是你的起始列表的2倍。在python中,您可以通过以下方式实现此目的(假设长度相同)。

list1 = [1, 1, 1, 0, 0]
list2 = [1, 1, 0, 0, 1]
print ' '.join(map(str, list2)) in ' '.join(map(str, list1 * 2))

关于我的老板的一些解释:
 list * 2将列表与其自身组合,map(str, [1, 2])将所有数字转换为字符串,' '.join()将数组['1', '2', '111']转换为字符串'1 2 111'
正如一些人在评论中所指出的,oneliner可能会给出一些假阳性,以便涵盖所有可能的边缘案例:

def isCircular(arr1, arr2):
    if len(arr1) != len(arr2):
        return False

    str1 = ' '.join(map(str, arr1))
    str2 = ' '.join(map(str, arr2))
    if len(str1) != len(str2):
        return False

    return str1 in str2 + ' ' + str2

 P.S.1当谈到时间复杂性时,值得注意的是,如果在O(n)时间内可以找到子字符串,则O(n)将被实现。它并不总是如此,取决于你的语言的实现(例如,although potentially it can be done in linear时间KMP)。
 P.S.2对于那些害怕字符串操作的人,由于这个事实认为答案不好。重要的是复杂性和速度。该算法潜在地运行在O(n)时间和O(n)空间中,这使得它比O(n^2)域中的任何内容好得多。要自己看这个,你可以运行一个小的基准(创建一个随机列表,弹出第一个元素,并将其附加到最后,从而创建一个循环列表,你可以自由地进行操作)

from random import random
bigList = [int(1000 * random()) for i in xrange(10**6)]
bigList2 = bigList[:]
bigList2.append(bigList2.pop(0))

# then test how much time will it take to come up with an answer
from datetime import datetime
startTime = datetime.now()
print isCircular(bigList, bigList2)
print datetime.now() - startTime    # please fill free to use timeit, but it will give similar results

在我的机器上0.3秒不是很长现在尝试将其与O(n^2)解决方案进行比较。在比较的时候,您可以从美国到澳大利亚旅游(最有可能是游轮)

 
 Code问答: codewenda.com
Stackoverflow:How to check whether two lists are circularly identical in Python

发表评论

电子邮件地址不会被公开。 必填项已用*标注

46 + = 49