如何检查两个列表是否在Python循环相同 [英] How to check whether two lists are circularly identical in 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的长度，并且只包含三个一和52个零中它。如果没有循环条件，有26235（55选3）名单。但是，如果条件通知的存在，有一个巨大的圆相同的列表号

The problem is, each list which I have has a length of 55 and contains only three ones and 52 zeros in it. Without circular condition, there are 26,235 (55 choose 3) lists. However, if the condition 'circular' exists, there are a huge number of circularly identical lists

目前我按照循环检查身份：

Currently I check circularly identity by following:

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循环移位运算。和有26235列表以彼此进行比较。总之，我需要55 * 26235 *（26235 - 1）/ 2 = 18926847225计算。这是关于近20千兆！

This function requires 55 cyclic shift operations at the worst case. And there are 26,235 lists to be compared with each other. In short, I need 55 * 26,235 * (26,235 - 1) / 2 = 18,926,847,225 computations. It's about nearly 20 Giga!

有没有什么好办法，用较少的计算做呢？或支持任何数据类型的圆的？

Is there any good way to do it with less computations? Or any data types that supports circular?

推荐答案

首先，这可以在在列表的长度方面做了O（N） 你可以看到，如果你会复制你的列表2倍（ [1，2，3] ）将 [1，2，3，1 ，2，3] 则新名单一定会容纳所有可能的循环列表。

First off, this can be done in O(n) in terms of the length of the list You can notice that if you will duplicate your list 2 times ([1, 2, 3]) will be [1, 2, 3, 1, 2, 3] then your new list will definitely hold all possible cyclic lists.

因此​​，所有你需要的是检查您正在搜索的列表是否是在你的首发名单的2倍。在python可以按以下方式实现这种（假定的长度是相同的）。

So all you need is to check whether the list you are searching is inside a 2 times of your starting list. In python you can achieve this in the following way (assuming that the lengths are the same).

list1 = [1, 1, 1, 0, 0]
list2 = [1, 1, 0, 0, 1]
print ' '.join(map(str, list2)) in ' '.join(map(str, list1 * 2))

我的oneliner一些解释： 列表* 2 将结合一个列表本身，地图（STR，[1，2]）转换所有的号码字符串和''。加入（）将转换阵列 ['1'，'2'，'111'] 转换成字符串1 2 111。

Some explanation about my oneliner: list * 2 will combine a list with itself, map(str, [1, 2]) convert all numbers to string and ' '.join() will convert array ['1', '2', '111'] into a string '1 2 111'.

正如一些人在评论，oneliner可能会给予一定的误报，所以要覆盖所有可能的边缘情况：

As pointed by some people in the comments, oneliner can potentially give some false positives, so to cover all the possible edge cases:

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例如做）。

P.S.1 when speaking about time complexity, it is worth noticing that O(n) will be achieved if substring can be found in O(n) time. It is not always so and depends on the implementation in your language (although potentially it can be done in linear time KMP for example).

PS2 的人谁是害怕的字符串操作，由于这一事实认为答案是不好的。什么重要的是复杂性和速度。该算法可能运行在 O（N）时间和 O（N）空间，这使得它比任何它好得多为O（n ^ 2）站点。要自己明白这一点，你可以运行一个小的基准（创建一个随机弹出列表的第一个元素，并将其追加从而最终建立一个循环列表，你可以自由地做自己的操作）

P.S.2 for people who are afraid strings operation and due to this fact think that the answer is not good. What important is complexity and speed. This algorithm potentially runs in O(n) time and O(n) space which makes it much better than anything in O(n^2) domain. To see this by yourself, you can run a small benchmark (creates a random list pops the first element and appends it to the end thus creating a cyclic list. You are free to do your own manipulations)

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）解决方案。虽然它是比较它，你可以（通过游轮最有可能）从美国前往澳大利亚

0.3 seconds on my machine. Not really long. Now try to compare this with O(n^2) solutions. While it is comparing it, you can travel from US to Australia (most probably by a cruise ship)

这篇关于如何检查两个列表是否在Python循环相同的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！