如何检查两个列表在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

它们似乎不同,但是如果假定起点和终点相连,则它们在 循环上是 相同的。

问题是,我拥有的每个列表的长度为55,并且仅包含三个1和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 Giga!

有什么好方法可以减少计算量吗?还是支持 循环的 任何数据类型?

回答:

首先,这可以根据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))

关于我的oneliner的一些解释: 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

在谈到时间复杂性时,值得注意的是,O(n)如果可以及时找到子字符串,则可以实现O(n)。它并非总是如此,并且取决于您所用语言的实现方式(尽管可能可以例如在线性时间KMP中完成)。

对于那些害怕弦乐操作的人,由于这个事实,他们认为答案并不理想。重要的是复杂性和速度。该算法可能会在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)解决方案进行比较。在进行比较时,您可以从美国到澳大利亚旅行(很可能乘游轮旅行)

以上是 如何检查两个列表在Python中是否循环相同 的全部内容, 来源链接: utcz.com/qa/412278.html

回到顶部