logo标签列表

在Python中计算列表中一个模式的出现次数

pythonpython-3.xpython-2.7listcount
5
给定模式[1,1,0,1,1]，和一个长度为100的二进制列表[0,1,1,0,0,...,0,1]。我想要计算在这个列表中出现该模式的次数。是否有一种简单的方法来做到这一点，而不需要使用变量跟踪每个索引处的每个项目？请注意，像这样的内容[...,1, 1, 0, 1, 1, 1, 1, 0, 1, 1,...,0]可能会发生，但应该计为2次出现。
我相信你需要至少访问列表中的每个项目一次，以检查它是否与模式中的起始项相同。也就是说，至少你必须进行 n-l+1 次访问，其中 "n" 是列表元素的数量，"l" 是模式的长度。 - Lauro Bravar
你可以将两个列表转换为字符串，然后使用正则表达式或查找函数... - YesThatIsMyName
这是一个关于编程的问题，你可以在以下链接中找到答案：https://dev59.com/8XA85IYBdhLWcg3wCe9Z。希望对你有所帮助。 - Puffin GDI
8个回答
5

使用join将你的列表转换为字符串。然后执行：

text.count(pattern)

如果你需要计算重叠的匹配项，那么你将需要使用正则表达式匹配或定义自己的函数。

编辑 以下是完整的代码：

def overlapping_occurences(string, sub):
    count = start = 0
    while True:
        start = string.find(sub, start) + 1
        if start > 0:
            count+=1
        else:
            return count

given_list = [1, 1, 0, 1, 1, 1, 1, 0, 1, 1]
pattern = [1,1,0,1,1]

text = ''.join(str(x) for x in given_list)
print(text)
pattern = ''.join(str(x) for x in pattern)
print(pattern)
print(text.count(pattern)) #for no overlapping
print(overlapping_occurences(text, pattern))
他可以查看这篇文章：https://dev59.com/nm445IYBdhLWcg3w3Nwf，或者https://dev59.com/zG865IYBdhLWcg3wUs7z，但是如果不将其转换为字符串，我没有看到除了迭代之外的简单方法。 - YesThatIsMyName
3
l1 = [1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0]
l1str = str(l1).replace(" ", "").replace("[", "").replace("]", "")

l3 = [1, 1, 0, 1, 1]
l3str = str(l3).replace(" ", "").replace("[", "").replace("]", "")


l1str = l1str.replace(l3str, "foo")
foo = l1str.count("foo")
print(foo)
3
您可以始终使用朴素的方法：对列表切片进行循环（与从第i个索引开始并以i+[模式长度]结尾的切片相同）。
而且，您可以改进它-请注意，如果您在索引i'中找到了出现，则可以跳过i+1和i+2，并从i+3及以后检查（意味着-您可以检查是否存在子模式，以便简化搜索） 这将花费O(n*m)的时间。
您可以使用反向卷积（称为模式匹配算法），这将花费O(n*log(n))的时间，更好。
2
您可以通过以下两个步骤解决这个问题：
  • Combine all elements of the list in a single string

  • Use python count function to match the pattern in the string

    a_new = ''.join(map(str,a))

pattern = ''.join(map(str,pattern))

a_new.count(pattern)
2
from collections import Counter

a = [1,1,0,1,1]
b = [1,1,0,1,1,1,1,0,1,1]

lst = list()
for i in range(len(b)-len(a)+1):
    lst.append(tuple(b[i:i+len(a)]))

c = Counter(lst)
print c[tuple(a)]

输出

2

循环可以写成一行，更加简洁，但代码的可读性会降低。
lst = [tuple(b[i:i+len(a)]) for i in range(len(b)-len(a)+1)]

注意，我使用元组是因为它们是不可变对象且可以被哈希

你也可以使用哈希功能并创建自己的哈希方法，例如将每个变量乘以10的位置上的幂

[1,0,1] = 1 * 1 + 0 * 10 + 1 * 100 = 101

这样你可以在列表上一次遍历中检查是否包含该模式，只需简单地检查 if sub_list == 101。

2

我认为一个简单的正则表达式就足够了:

def find(sample_list):
    list_1 = [1,1,0,1,1]
    str_1 = str(list_1)[1:-1]
    print len(re.findall(str_1, str(sample_list)))

希望这能解决你的问题。
1
你可以将查找列表分成与要查找的模式大小相同的块。您可以使用简单的配方来实现这一点，其中包括 itertools.islice 来产生一个滑动窗口迭代器。
>>> from itertools import islice

>>> p = [1,1,0,1,1]
>>> l = [0,1,1,0,0,0,1,1,0,1,1,1,0,0,1]
>>> [tuple(islice(l,k,len(p)+k)) for k in range(len(l)-len(p)+1)]

这将会给你输出如下内容：
>>> [(0, 1, 1, 0, 0), (1, 1, 0, 0, 0), (1, 0, 0, 0, 1), (0, 0, 0, 1, 1), (0, 0, 1, 1, 0), (0, 1, 1, 0, 1), (1, 1, 0, 1, 1), (1, 0, 1, 1, 1), (0, 1, 1, 1, 0), (1, 1, 1, 0, 0), (1, 1, 0, 0, 1)]

现在你可以使用 collections.Counter 来计算序列中每个子列表的出现次数，例如：
 >>> from collections import Counter
 >>> c = Counter([tuple(islice(l,k,len(p)+k)) for k in range(len(l)-len(p)+1)])
 >>> c 
 >>> Counter({(0, 1, 1, 0, 1): 1, (1, 1, 1, 0, 0): 1, (0, 0, 1, 1, 0): 1, (0, 1, 1, 1, 0): 1, (1, 1, 0, 0, 0): 1, (0, 0, 0, 1, 1): 1, (1, 1, 0, 1, 1): 1, (0, 1, 1, 0, 0): 1, (1, 0, 1, 1, 1): 1, (1, 1, 0, 0, 1): 1, (1, 0, 0, 0, 1): 1})

获取您所需序列的频率，请使用：

 >>> c.get(tuple(p),0)
 >>> 1

注意，我已经在所有地方使用了tuple作为dict键，因为在Python中list不是可哈希的类型，所以不能用作dict键。
0
你可以尝试使用 range 方法：
pattern_data=[1,1,0,1,1]
data=[1,1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,0,1,1,1,1,0,1,1,0,0,0,0,0,1,1,0,1,0,1,1,0,1,1,1,1,0,1,1,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1]

count=0
for i in range(0,len(data),1):
    if data[i:i+len(pattern_data)]==pattern_data:
        print(i,data[i:i+len(pattern_data)])
        j+=1

print(count)

输出：

0 [1, 1, 0, 1, 1]
15 [1, 1, 0, 1, 1]
20 [1, 1, 0, 1, 1]
35 [1, 1, 0, 1, 1]
40 [1, 1, 0, 1, 1]
52 [1, 1, 0, 1, 1]
55 [1, 1, 0, 1, 1]
60 [1, 1, 0, 1, 1]
75 [1, 1, 0, 1, 1]
80 [1, 1, 0, 1, 1]
95 [1, 1, 0, 1, 1]
11
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接