例如，我有列表：
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个零。没有循环条件，有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吉加！
有没有什么好方法可以用更少的计算来做到这一点？或者支持循环的任何数据类型？
首先，这可以在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))
关于我的一个班轮的一些解释：qazxsw poi将列表与自身结合，qazxsw poi将所有数字转换为字符串，list * 2将数组map(str, [1, 2])转换为字符串' '.join()。
正如一些人在评论中指出的那样，oneliner可能会给出一些误报，所以要涵盖所有可能的边缘情况：
['1', '2', '111']P.S.1在谈到时间复杂性时，值得注意的是，如果在'1 2 111'时间可以找到子串，那么将实现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
。它并非总是如此，取决于您的语言的实现（例如，O(n)时间KMP）。
P.S.2对于害怕弦乐操作的人而言，由于这个事实认为答案并不好。复杂性和速度至关重要。该算法可能在O(n)时间和although potentially it can be done in linear空间中运行，这使得它比O(n)域中的任何东西都要好得多。要自己看这个，你可以运行一个小的基准测试（创建一个随机列表弹出第一个元素并将其追加到最后，从而创建一个循环列表。你可以自由地进行自己的操作）
O(n)在我的机器上0.3秒。不是很久。现在尝试将其与O(n^2)解决方案进行比较。在进行比较时，您可以从美国到澳大利亚（最有可能乘坐游轮）
这不是一个完整的，独立的答案，但关于通过减少比较进行优化的主题，我也在考虑规范化的表示。
也就是说，如果输入字母为{0,1}，则可以显着减少允许的排列数。将第一个列表旋转为（伪）标准化形式（根据您的问题中的分布，我会选择一个位于最左侧的1位中的一个，并且0位中的一个位于最右侧）。现在，在每次比较之前，通过具有相同对齐模式的可能位置连续旋转另一个列表。
例如，如果总共有4个1位，则此对齐最多可以有4个排列，如果有相邻1位的簇，则此类簇中的每个附加位都会减少位置数。
list1, list2 = [0,1,1,1,0,0,1,0], [1,0,0,1,0,0,1,1]
str_list1="".join(map(str,list1))
str_list2="".join(map(str,list2))
def rotate(string_to_rotate, result=[]):
result.append(string_to_rotate)
for i in xrange(1,len(string_to_rotate)):
result.append(result[-1][1:]+result[-1][0])
return result
for x in rotate(str_list1):
if cmp(x,str_list2)==0:
print "lists are rotationally identical"
break
这推广到更大的字母和不同的对齐模式;主要的挑战是找到一个很好的规范化，只有几个可能的表示。理想情况下，这将是一个适当的规范化，具有单一的唯一表示，但考虑到问题，我认为这是不可能的。
进一步构建RocketRoy的答案：将所有列表转换为无符号的64位数字。对于每个列表，旋转这些55位以找到最小的数值。
现在，您可以为每个列表留下一个无符号的64位值，您可以直接与其他列表的值进行比较。函数is_circular_identical（）不再需要了。
（实际上，您为列表创建了一个不受列表元素轮换影响的标识值）如果您的列表中有一个任意数量的列表，那么这甚至可以起作用。
这与Salvador Dali的想法相同，但不需要字符串转换。背后是同样的KMP恢复想法，以避免不可能的轮班检查。他们只调用KMP Modified（list1，list2 + list2）。
def rollmatch(a,b):
bb=b*2
return any(not any(ax^bbx for ax,bbx in zip(a,bb[i:])) for i in range(len(a)))
l1 = [1,0,0,1]
l2 = [1,1,0,0]
l3 = [1,0,1,0]
rollmatch(l1,l2) # True
rollmatch(l1,l3) # False
希望这有帮助！
简化问题
List 1 1 1 1 0 1 0
List 2 1 0 1 1 1 0 1st permutation
1 1 1 0 1 0 2nd permutation, final permutation, match, done
public class KmpModified
{
public int[] CalculatePhi(int[] pattern)
{
var phi = new int[pattern.Length + 1];
phi[0] = -1;
phi[1] = 0;
int pos = 1, cnd = 0;
while (pos < pattern.Length)
if (pattern[pos] == pattern[cnd])
{
cnd++;
phi[pos + 1] = cnd;
pos++;
}
else if (cnd > 0)
cnd = phi[cnd];
else
{
phi[pos + 1] = 0;
pos++;
}
return phi;
}
public IEnumerable<int> Search(int[] pattern, int[] list)
{
var phi = CalculatePhi(pattern);
int m = 0, i = 0;
while (m < list.Length)
if (pattern[i] == list[m])
{
i++;
if (i == pattern.Length)
{
yield return m - i + 1;
i = phi[i];
}
m++;
}
else if (i > 0)
{
i = phi[i];
}
else
{
i = 0;
m++;
}
}
[Fact]
public void BasicTest()
{
var pattern = new[] { 1, 1, 10 };
var list = new[] {2, 4, 1, 1, 1, 10, 1, 5, 1, 1, 10, 9};
var matches = Search(pattern, list).ToList();
Assert.Equal(new[] {3, 8}, matches);
}
[Fact]
public void SolveProblem()
{
var random = new Random();
var list = new int[10];
for (var k = 0; k < list.Length; k++)
list[k]= random.Next();
var rotation = new int[list.Length];
for (var k = 1; k < list.Length; k++)
rotation[k - 1] = list[k];
rotation[rotation.Length - 1] = list[0];
Assert.True(Search(list, rotation.Concat(rotation).ToArray()).Any());
}
}
s映射到计数来减少问题(0,1)s成负数例
1检查过程
握把
0和A = [ 1, 1, 1, 0, 0, 1, 1, 0 ]
B = [ 1, 1, 0, 1, 1, 1, 0, 0 ]
~
A = [ +3, -2, +2, -1 ]
B = [ +2, -1, +3, -2 ]
伪代码
lookuplook-ahead功能
FUNCTION IS_DUPLICATE (LIST L1, LIST L2) : BOOLEAN
LIST A = MAP_LIST(L1)
LIST B = MAP_LIST(L2)
LIST ALPHA = LOOKUP_INDEX(B, A[0])
IF A.SIZE != B.SIZE
OR COUNT_CHAR(A, 0) != COUNT_CHAR(B, ALPHA[0]) THEN
RETURN FALSE
END IF
FOR EACH INDEX IN ALPHA
IF ALPHA_NGRAM(A, B, INDEX, 1) THEN
IF IS_DUPLICATE(A, B, INDEX) THEN
RETURN TRUE
END IF
END IF
END FOR
RETURN FALSE
END FUNCTION
返回列表中的元素FUNCTION IS_DUPLICATE (LIST L1, LIST L2, INTEGER INDEX) : BOOLEAN
INTEGER I = 0
WHILE I < L1.SIZE DO
IF L1[I] != L2[(INDEX+I)%L2.SIZE] THEN
RETURN FALSE
END IF
I = I + 1
END WHILE
RETURN TRUE
END FUNCTION
列表中的MAP_LIST(LIST A):LISTLOOKUP_INDEX(LIST A, INTEGER E):LIST COUNT多年来一个元素E发表在列表中ACOUNT_CHAR(LIST A , INTEGER E):INTEGER检查如果E等同于A ALPHA_NGRAM(LIST A,LIST B,INTEGER I,INTEGER N):BOOLEAN两个方向最后
如果列表大小非常大或者我们开始检查循环的元素通常很高，那么我们可以执行以下操作：
有问题的列表的高效，快速计算的“规范形式”可以导出为：
B[I]）必须介于A[0]和N-GRAM（包括）之间。在a和18之间重新编码。52）必须介于0和34之间，但这并不重要。b并且不添加任何信息规范形式是整数0，它位于26和52 - (a + b)（包括）之间，这是相当紧凑的（总共有b * 35 + a循环唯一列表）。
我写了一个简单的解决方案，它比较了两个列表，只是增加（并包装）每次迭代的比较值的索引。
我不太了解python，所以我用Java编写它，但它非常简单，因此应该很容易使它适应任何其他语言。
通过这个你也可以比较其他类型的列表。
0正如其他人所提到的，一旦找到列表的标准化轮换，就可以比较它们。
下面是一些工作代码，基本方法是为每个列表找到一个标准化的旋转并比较：
请注意，此方法不依赖于数字，您可以传入字符串列表（可以比较的任何值）。
我们不是在列表中进行列表搜索，而是希望列表以最小值开始 - 所以我们可以遍历最小值，搜索直到找到哪个具有最低的连续值，并将其存储以进行进一步比较直到我们拥有最好的。
计算索引时有很多机会提前退出，有些优化的细节。
请注意，在Python中，列表中的列表搜索可能会更快，但我有兴趣找到一种有效的算法 - 也可以在其他语言中使用。此外，避免创建新列表也有一些优势。
936请参阅：477了解更多测试/示例。
你可以很容易地检查列表A是否等于预期O（N）时间内列表B的循环移位。
我将使用多项式散列函数来计算列表A的散列，以及列表B的每个循环移位。如果列表B的移位具有与列表A相同的散列，我将比较实际元素以查看它们是否相等。
这很快的原因是，使用多项式散列函数（非常常见！），您可以在恒定时间内计算每个循环移位的散列，因此您可以计算O中所有循环移位的散列（ N）时间。
它的工作原理如下：
假设B有N个元素，那么使用素数P的B的散列是：
public class Main {
public static void main(String[] args){
int[] a = {0,1,1,1,0};
int[] b = {1,1,0,0,1};
System.out.println(isCircularIdentical(a, b));
}
public static boolean isCircularIdentical(int[] a, int[]b){
if(a.length != b.length){
return false;
}
//The outer loop is for the increase of the index of the second list
outer:
for(int i = 0; i < a.length; i++){
//Loop trough the list and compare each value to the according value of the second list
for(int k = 0; k < a.length; k++){
// I use modulo length to wrap around the index
if(a[k] != b[(k + i) % a.length]){
//If the values do not match I continue and shift the index one further
continue outer;
}
}
return true;
}
return false;
}
}
这是评估P中多项式的优化方法，相当于：
def normalize_rotation_index(ls, v_min_other=None):
""" Return the index or -1 (when the minimum is above `v_min_other`) """
if len(ls) <= 1:
return 0
def compare_rotations(i_a, i_b):
""" Return True when i_a is smaller.
Note: unless there are large duplicate sections of identical values,
this loop will exit early on.
"""
for offset in range(1, len(ls)):
v_a = ls[(i_a + offset) % len(ls)]
v_b = ls[(i_b + offset) % len(ls)]
if v_a < v_b:
return True
elif v_a > v_b:
return False
return False
v_min = ls[0]
i_best_first = 0
i_best_last = 0
i_best_total = 1
for i in range(1, len(ls)):
v = ls[i]
if v_min > v:
v_min = v
i_best_first = i
i_best_last = i
i_best_total = 1
elif v_min == v:
i_best_last = i
i_best_total += 1
# all values match
if i_best_total == len(ls):
return 0
# exit early if we're not matching another lists minimum
if v_min_other is not None:
if v_min != v_min_other:
return -1
# simple case, only one minimum
if i_best_first == i_best_last:
return i_best_first
# otherwise find the minimum with the lowest values compared to all others.
# start looking after the first we've found
i_best = i_best_first
for i in range(i_best_first + 1, i_best_last + 1):
if (ls[i] == v_min) and (ls[i - 1] != v_min):
if compare_rotations(i, i_best):
i_best = i
return i_best
def compare_circular_lists(ls_a, ls_b):
# sanity checks
if len(ls_a) != len(ls_b):
return False
if len(ls_a) <= 1:
return (ls_a == ls_b)
index_a = normalize_rotation_index(ls_a)
index_b = normalize_rotation_index(ls_b, ls_a[index_a])
if index_b == -1:
return False
if index_a == index_b:
return (ls_a == ls_b)
# cancel out 'index_a'
index_b = (index_b - index_a)
if index_b < 0:
index_b += len(ls_a)
index_a = 0 # ignore it
# compare rotated lists
for i in range(len(ls_a)):
if ls_a[i] != ls_b[(index_b + i) % len(ls_b)]:
return False
return True
assert(compare_circular_lists([0, 9, -1, 2, -1], [-1, 2, -1, 0, 9]) == True)
assert(compare_circular_lists([2, 9, -1, 0, -1], [-1, 2, -1, 0, 9]) == False)
assert(compare_circular_lists(["Hello" "Circular", "World"], ["World", "Hello" "Circular"]) == True)
assert(compare_circular_lists(["Hello" "Circular", "World"], ["Circular", "Hello" "World"]) == False)
注意每个B [i]如何乘以P ^（N-1-i）。如果我们将B向左移动1，则每个B [i]将乘以额外的P，除了第一个。由于乘法在加法上分布，我们可以通过乘以整个散列来一次乘以所有分量，然后修复第一个元素的因子。
B的左移的哈希就是
this snippet
第二个左移：
Hb=0;
for (i=0; i<N ; i++)
{
Hb = Hb*P + B[i];
}
等等...
注意：以上所有数学运算都是以某些机器字大小为模，并且您只需计算一次P ^ N.
要粘贴到最pythonic方式，使用集合！
Hb=0;
for (i=0; i<N ; i++)
{
Hb += B[i] * P^(N-1-i); //^ is exponentiation, not XOR
}
在Python中没有足够的知识来满足您所要求的语言，但在C / C ++中，根据您的问题的参数，我将零和1转换为位并将它们推送到uint64_t的最低有效位。这将允许您一举比较所有55位 - 1个时钟。
错误快速，整个事情将适合片上缓存（209,880字节）。用于同时移动所有55个列表成员的硬件支持仅在CPU的寄存器中可用。同样比较所有55个成员也是如此。这允许将问题映射到软件解决方案。 （并使用SIMD / SSE 256位寄存器，如果需要，最多256个成员）因此，代码对读者来说是显而易见的。
您可能能够在Python中实现这一点，我只是不太了解它是否可能或性能可能是什么。
在睡觉之后，一些事情变得明显，并且一切都变得更好。
1.）使用比特旋转圆形链表非常容易，Dali的非常聪明的技巧是不必要的。在64位寄存器内部，标准位移动将非常简单地完成旋转，并试图通过使用算术而不是位操作使这更加友好。
2.）使用除以2可以轻松完成位移。
3.）通过模2可以很容易地检查列表的结尾是0还是1。
4.）从尾部“移动”0到列表的头部可以通过除以2来完成。这是因为如果零实际移动了它将使第55位为假，它已经完全没有做任何事情。
5.）从尾部“移动”1到列表的头部可以通过除以2并添加18,014,398,509,481,984来完成 - 这是通过将第55位标记为真而其余全部为假而创建的值。
6.）如果在任何给定的旋转之后锚和组合uint64_t的比较为TRUE，则中断并返回TRUE。
我会将整个列表数组转换为前面的uint64_ts数组，以避免重复进行转换。
在花了几个小时试图优化代码之后，研究汇编语言我能够节省20％的运行时间。我应该补充一点，O / S和MSVC编译器也在昨天中午更新了。无论出于何种原因，C编译器生成的代码质量在更新后（2014年11月15日）都得到了显着改善。运行时间现在约为70个时钟，17纳秒组成并比较一个锚环与测试环的所有55匝，所有环的NxN与所有其他环相比在12.5秒内完成。
除了4个寄存器在99％的时间内无所事事之外，这个代码非常紧凑。汇编语言几乎与行代码匹配。非常容易阅读和理解。一个伟大的装配项目，如果有人在教自己。
硬件是Hazwell i7，MSVC 64位，完全优化。
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
在行之间进行读取，听起来好像是在尝试枚举每个循环等价类的一个代表，其中包含3个1和52个零。让我们从密集表示切换到稀疏表示（O(n^2)中的三个数字集合）。在这个表示中，#include "stdafx.h"
#include "stdafx.h"
#include <string>
#include <memory>
#include <stdio.h>
#include <time.h>
const uint8_t LIST_LENGTH = 55; // uint_8 supports full witdth of SIMD and AVX2
// max left shifts is 32, so must use right shifts to create head_bit
const uint64_t head_bit = (0x8000000000000000 >> (64 - LIST_LENGTH));
const uint64_t CPU_FREQ = 3840000000; // turbo-mode clock freq of my i7 chip
const uint64_t LOOP_KNT = 688275225; // 26235^2 // 1000000000;
// ----------------------------------------------------------------------------
__inline uint8_t is_circular_identical(const uint64_t anchor_ring, uint64_t test_ring)
{
// By trial and error, try to synch 2 circular lists by holding one constant
// and turning the other 0 to LIST_LENGTH positions. Return compare count.
// Return the number of tries which aligned the circularly identical rings,
// where any non-zero value is treated as a bool TRUE. Return a zero/FALSE,
// if all tries failed to find a sequence match.
// If anchor_ring and test_ring are equal to start with, return one.
for (uint8_t i = LIST_LENGTH; i; i--)
{
// This function could be made bool, returning TRUE or FALSE, but
// as a debugging tool, knowing the try_knt that got a match is nice.
if (anchor_ring == test_ring) { // test all 55 list members simultaneously
return (LIST_LENGTH +1) - i;
}
if (test_ring % 2) { // ring's tail is 1 ?
test_ring /= 2; // right-shift 1 bit
// if the ring tail was 1, set head to 1 to simulate wrapping
test_ring += head_bit;
} else { // ring's tail must be 0
test_ring /= 2; // right-shift 1 bit
// if the ring tail was 0, doing nothing leaves head a 0
}
}
// if we got here, they can't be circularly identical
return 0;
}
// ----------------------------------------------------------------------------
int main(void) {
time_t start = clock();
uint64_t anchor, test_ring, i, milliseconds;
uint8_t try_knt;
anchor = 31525197391593472; // bits 55,54,53 set true, all others false
// Anchor right-shifted LIST_LENGTH/2 represents the average search turns
test_ring = anchor >> (1 + (LIST_LENGTH / 2)); // 117440512;
printf("\n\nRunning benchmarks for %llu loops.", LOOP_KNT);
start = clock();
for (i = LOOP_KNT; i; i--) {
try_knt = is_circular_identical(anchor, test_ring);
// The shifting of test_ring below is a test fixture to prevent the
// optimizer from optimizing the loop away and returning instantly
if (i % 2) {
test_ring /= 2;
} else {
test_ring *= 2;
}
}
milliseconds = (uint64_t)(clock() - start);
printf("\nET for is_circular_identical was %f milliseconds."
"\n\tLast try_knt was %u for test_ring list %llu",
(double)milliseconds, try_knt, test_ring);
printf("\nConsuming %7.1f clocks per list.\n",
(double)((milliseconds * (CPU_FREQ / 1000)) / (uint64_t)LOOP_KNT));
getchar();
return 0;
}
的range(55)的循环移位由理解s给出。类中的词典最小代表总是包含位置0.给定k与set((i + k) % 55 for i in s)形式的集合，类中最小的其他候选者是{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))（O（n）time）在第一个数组中找到第二个数组。
（注意：您不必在物理上复制第一个数组。您可以在匹配期间进行环绕。）
关于Z算法的好处是它与KMP，BM等相比非常简单。
但是，如果你有野心，你可以在线性时间和恒定空间中进行字符串匹配 - 例如，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
就是这样做的。但是，实施它会更加痛苦。
继萨尔瓦多·达利非常聪明的解决方案之后，处理它的最佳方法是确保所有元素的长度相同，并且两个LISTS的长度相同。
Z algorithm
不知道这是否比AshwiniChaudhary在Salvador Dali的回答中推荐的正则表达式解决方案更快或更慢，其答案如下：
strstr鉴于您需要进行许多比较，您可能值得在初始通过列表时将它们转换为某种可以轻松比较的规范形式吗？
您是否想要获得一组循环唯一的列表？如果是这样，你可以在转换为元组后将它们放入集合中。
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
向David Eisenstat道歉，因为他没有发现他的v.similar答案。
您可以像这样滚动一个列表：
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))
首先将每个列表元素（如果需要，在副本中）转换为词法上最大的旋转版本。
然后对结果列表进行排序（将索引保留在原始列表位置）并统一排序列表，根据需要标记原始列表中的所有重复项。
捎带@ SalvadorDali关于在b + b中查找任何一个加长大小的切片中a的匹配的观察，这里是一个仅使用列表操作的解决方案。
def normalise(lst):
# Pick the 'maximum' out of all cyclic options
return max([lst[i:]+lst[:i] for i in range(len(lst))])
a_normalised = map(normalise,a)
a_tuples = map(tuple,a_normalised)
a_unique = set(a_tuples)
第二种方法：[删除]