例如,我有一些列表:
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千兆!
有没有更少计算量的好方法呢?或任何支持循环的数据类型
发布于 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 reps
发布于 2014-11-14 19:33:58
重复第一个数组,然后使用Z algorithm (O(n)时间)查找第一个数组中的第二个数组。
(注意:您不必物理复制第一个数组。您可以在匹配过程中进行回绕。)
Z算法的优点在于,与KMP、BM等相比,它非常简单。
但是,如果您觉得自己很有野心,可以在线性时间和恒定空间中进行字符串匹配--例如,strstr
就是这样做的。然而,实现它将更加痛苦。
发布于 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
复制相似问题