在一系列数字中检测重复循环（Python）

Question

我想知道一个相对'普通'或正常的方法来完成这个任务。并不是寻找最短的解决方案，如两行代码等。我只是快速地编写了这段代码，但感觉里面有太多内容了。 如果有任何可帮助完成此任务的库，那将非常好。

def get_cycle(line):
    nums = line.strip().split(' ')

    # 2 main loops, for x and y
    for x in range(2, len(nums)): # (starts at 2, assuming the sequence requires at least 2 members)
        for y in range(0, x):
            # if x is already in numbers before it
            if nums[x] == nums[y]:
                seq = [nums[x]] # (re)start the sequence
                adder = 1       # (re)set the adder to 1
                ok = True       # (re)set ok to be True
                # while the sequence still matches (is ok) and
                # tail of y hasn't reached start of x
                while ok and y + adder < x:
                    if nums[x + adder] == nums[y + adder]:  # if next y and x match
                        seq.append(nums[x + adder])         # add the number to sequence
                        adder += 1                          # increase adder
                    else:
                        ok = False                          # else the sequence is broken
                # if the sequence wasn't broken and has at least 2 members
                if ok and len(seq) > 1:
                    print(' '.join(seq))    # print it out, separated by an empty space
                    return

- SuperLemon

---

请尝试用语言描述这段代码的作用，它非常复杂。 - Fred Foo

如果这个程序正常运行，那么在http://codereview.stackexchange.com/上提问可能会更好。 - Adam Wagner

抱歉内容有些密集。它读取一串数字，例如'3 0 5 5 1 5 1 6 8'，并且需要找出第一个重复的数字序列，在这个例子中是 '5 1 5 1'，然后输出该序列（'5 1'）。 编辑：是的，这个方法可以实现，但肯定还有更好的方法。----输入文本文件： 2 0 6 3 1 6 3 1 6 3 1 ---- 输出结果： 6 3 1 - SuperLemon

为什么它不打印（'5'）？它应该打印最长的序列吗？只有长度大于2的序列吗？ - Niklas B.

如果序列没有被中断且至少有2个成员 ----如果ok并且len(seq)>1：---- 必须至少有2个成员……我想一个数字不算是一个序列。 - SuperLemon

@falconvk - 感谢您的澄清，我编辑了我的答案，现在应该可以满足您的要求。 - Andrew Clark

Answer 1

我可能没有完全理解这个问题，但我认为可以用正则表达式非常简单地解决。

(.+ .+)( \1)+

这里有一个例子：

>>> regex = re.compile(r'(.+ .+)( \1)+')
>>> match = regex.search('3 0 5 5 1 5 1 6 8')
>>> match.group(0)    # entire match
'5 1 5 1'
>>> match.group(1)    # repeating portion
'5 1'
>>> match.start()     # start index of repeating portion
6

>>> match = regex.search('2 0 6 3 1 6 3 1 6 3 1')
>>> match.group(1)
'6 3 1'

这是它的工作原理，(.+ .+)将匹配至少两个数字（尽可能多），然后将结果放入捕获组1中。 ( \1)+将匹配空格，后跟捕获组1的内容，至少一次。

对于字符串'3 0 5 5 1 5 1 6 8'的详细说明:

• (.+ .+)最初将匹配整个字符串，但会从结尾减去一些字符因为( \1)+会失败，这种回溯会一直发生直到(.+ .+)在字符串开头无法匹配，此时正则表达式引擎将向前移动并再次尝试
• 这将一直发生直到捕获组从第二个5开始，它将从结尾减去一些字符，直到捕获'5 1'，此时正则表达式正在寻找任意数量的' 5 1'以进行( \1)+，它当然会找到这个并且匹配成功

- Andrew Clark

---

它不必是最长的序列，只需要是一个重复循环，比如1 3 6 5 1 3 6这样的就不算，因为中间有一个5。需要找到第一次出现的循环，而不是最长的循环。 - SuperLemon

非常期待看到解释。 我已经学习Python大约一周了，对于整个正则表达式的东西还很陌生。我想我应该更多地关注它。 - SuperLemon

谢谢。现在我只需要认真研究一下它，看看每个部分都是做什么的以及为什么要这样做。我甚至从未使用过compile()，非常感激！ - SuperLemon

(.+ .+) 我以为这个正则表达式总是能找到两个或更多字符的两个组，组之间用一个空格分隔。然后 ( \1)+ 部分将匹配其后的任意数量的这些两个部分组合，这就是为什么我对它如何匹配 6 3 1 6 3 1 仍然感到困惑。 - SuperLemon

Answer 2

您的问题实际上是“x：x + k中的所有项是否与y：y + k中的所有项匹配”。也就是说，一行中是否存在重复的k长度子集？

您希望x：x + k与y：y + k不重叠。简单的方法是将y定义为x加上某个偏移量d。如果确保k <= d < len(line)-x-k，则始终在线路边界内查找。

然后，您需要将k从1变化到len(line)//2，查找给定偏移量之间各种长度的重复项。

从x到y的偏移量d将在1到len(line)-x-k之间变化。

类似地，x的起始位置也将在0到len(line)//2之间变化。

因此，“all”部分类似于以下内容：all( line[i] == line[i+d] for i in range(x,x+k) ) ，对于d、x和k的各种合法值。

- S.Lott

---

+1 是将一个模糊的问题转化为可行的问题规范。 - Raymond Hettinger

我仅凭你所写的那一行很难确定，但是这个序列必须在“itself”之后重复出现，而不仅仅是在该行中的任意两个位置出现两次。不过我会尝试一下，谢谢。 - SuperLemon

如果x和y之间的偏移量d == k，则您要查找相邻的k长度序列。 - S.Lott