Python如何在整数列表中查找重复的序列？

Question

Python如何在整数列表中查找重复的序列？

7

我有一个列表嵌套多个列表，每个子列表中都有重复的整数序列。我想要统计这些序列的重复长度：

list_a = [111,0,3,1,111,0,3,1,111,0,3,1] 

list_b = [67,4,67,4,67,4,67,4,2,9,0]

list_c = [1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,23,18,10]

这将返回：

list_a count = 4 (for [111,0,3,1])

list_b count = 2 (for [67,4])

list_c count = 10 (for [1,2,3,4,5,6,7,8,9,0])

任何建议或提示都将受到欢迎。我现在正在尝试使用re.compile解决它，但还不太对。

- tijko

这个列表是否百分之百地只包含了相同的重复模式？ - Sebastian Hoffmann

是的，肯定存在重复模式。它可以是从1位数字到200位数字的任何模式。 - tijko

1

正则表达式几乎肯定不是您要寻找的，因为您没有处理字符串，并且将列表转换为字符串将会给您带来比2个问题更多的问题。 - Wooble

我已经将这些列表转换为字符串。你认为会遇到什么问题？ - tijko

3个回答

0

我采用了Maria更快且符合stackoverflow标准的答案，并将其修改为先查找最大序列：

def guess_seq_len(seq, verbose=False):
    seq_len = 1
    initial_item = seq[0]
    butfirst_items = seq[1:]
    if initial_item in butfirst_items:
        first_match_idx = butfirst_items.index(initial_item)
        if verbose:
            print(f'"{initial_item}" was found at index 0 and index {first_match_idx}')
        max_seq_len = min(len(seq) - first_match_idx, first_match_idx)
        for seq_len in range(max_seq_len, 0, -1):
            if seq[:seq_len] == seq[first_match_idx:first_match_idx+seq_len]:
                if verbose:
                    print(f'A sequence length of {seq_len} was found at index {first_match_idx}')
                break
    
    return seq_len

- Dave Babbitt

-1

这个方法对我起作用了。

def repeated(L):
    '''Reduce the input list to a list of all repeated integers in the list.'''
    return [item for item in list(set(L)) if L.count(item) > 1]

def print_result(L, name):
    '''Print the output for one list.'''
    output = repeated(L)
    print '%s count = %i (for %s)' % (name, len(output), output)

list_a = [111, 0, 3, 1, 111, 0, 3, 1, 111, 0, 3, 1]
list_b = [67, 4, 67, 4, 67, 4, 67, 4, 2, 9, 0]
list_c = [
    1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2,
    3, 4, 5, 6, 7, 8, 9, 0, 23, 18, 10
]

print_result(list_a, 'list_a')
print_result(list_b, 'list_b')
print_result(list_c, 'list_c')

Python的set()函数将列表转换为集合，这种数据类型只能包含给定值中的一个，就像代数中的集合一样。我将输入列表转换为集合，然后再将其转换回列表，从而将列表减少到仅包含其唯一值。然后我测试了原始列表中的每个值，以查看它是否包含该值超过一次。我返回了所有重复项的列表。其余代码仅用于演示目的，以展示它的工作原理。

编辑：语法高亮不喜欢我的文档字符串中的撇号。

- vinnydiehl

2

这并没有回答问题。 - Joel Cornett

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Maria Zverina · Accepted Answer

通过迭代猜测2到序列长度的一半来猜测序列长度。如果没有发现模式，则默认返回1。

def guess_seq_len(seq):
    guess = 1
    max_len = len(seq) / 2
    for x in range(2, max_len):
        if seq[0:x] == seq[x:2*x] :
            return x

    return guess

list_a = [111,0,3,1,111,0,3,1,111,0,3,1] 
list_b = [67,4,67,4,67,4,67,4,2,9,0]
list_c = [1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,23,18,10]

print guess_seq_len(list_a)
print guess_seq_len(list_b)
print guess_seq_len(list_c)
print guess_seq_len(range(500))   # test of no repetition

这将得到（如预期）：

根据要求，这个新方法可以找到最长的重复序列。因此，对于list_b它将返回4。唯一的变化是将return x改为guess = x。

def guess_seq_len(seq):
    guess = 1
    max_len = len(seq) / 2
    for x in range(2, max_len):
        if seq[0:x] == seq[x:2*x] :
            guess = x

    return guess