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

一尘不染

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

algorithm

例如，我有以下列表：

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！

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

阅读 510

2020-07-28

共1个答案

一尘不染

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

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

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

2020-07-28