如何在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，其中只包含3个1和52个0。如果没有循环条件，则有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千兆！
有没有更少计算量的好方法呢？或任何支持循环的数据类型
回答 13
Stack Overflow用户
发布于 2014-11-15 00:00:39
从字里行间可以看出，您似乎是在尝试用3个1和52个0来枚举每个循环等价类字符串的一个代表。让我们从密集表示切换到稀疏表示(range(55)中的一组三个数字)。在这种表示中，k对s的循环移位是由理解set((i + k) % 55 for i in s)给出的。类中的字典序最小表示总是包含位置0。给出一组带有0 < i < j的{0, i, j}形式，类中最小形式的其他候选是{0, j - i, 55 - i}和{0, 55 - j, 55 + i - j}。因此，我们需要将原始文件的(i, j) <= min((j - i, 55 - i), (55 - j, 55 + i - j))设置为最小。下面是一些枚举代码。
def makereps():
reps = []
for i in range(1, 55 - 1):
for j in range(i + 1, 55):
if (i, j) <= min((j - i, 55 - i), (55 - j, 55 + i - j)):
reps.append('1' + '0' * (i - 1) + '1' + '0' * (j - i - 1) + '1' + '0' * (55 - j - 1))
return repsStack Overflow用户
发布于 2014-11-14 19:33:58
重复第一个数组，然后使用Z algorithm (O(n)时间)查找第一个数组中的第二个数组。
(注意:您不必物理复制第一个数组。您可以在匹配过程中进行回绕。)
Z算法的优点在于，与KMP、BM等相比，它非常简单。
但是，如果您觉得自己很有野心，可以在线性时间和恒定空间中进行字符串匹配--例如，strstr就是这样做的。然而，实现它将更加痛苦。
Stack Overflow用户
发布于 2014-11-14 15:37:35
在的非常聪明的解决方案之后，处理它的最好方法是确保所有元素的长度相同，以及两个列表的长度相同。
def is_circular_equal(lst1, lst2):
if len(lst1) != len(lst2):
return False
lst1, lst2 = map(str, lst1), map(str, lst2)
len_longest_element = max(map(len, lst1))
template = "{{:{}}}".format(len_longest_element)
circ_lst = " ".join([template.format(el) for el in lst1]) * 2
return " ".join([template.format(el) for el in lst2]) in circ_lst不知道这是比AshwiniChaudhary推荐的正则表达式解决方案更快还是更慢，在Salvador的答案中是这样写的：
import re
def is_circular_equal(lst1, lst2):
if len(lst2) != len(lst2):
return False
return bool(re.search(r"\b{}\b".format(' '.join(map(str, lst2))),
' '.join(map(str, lst1)) * 2))https://stackoverflow.com/questions/26924836
复制相似问题