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

Question

例如，我有列表:

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!

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

Answer 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

P.S.1 在谈到时间复杂度时，值得注意的是，如果在 O(n) 中可以找到子字符串，则将实现 O(n) 时间。并非总是如此，这取决于您的语言的实现(例如 although potentially it can be done in linear time 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) 解决方案进行比较。在比较它的同时，您可以从美国前往澳大利亚(很可能乘游轮)