Найти - Пользователи
Полная версия: Класическая задача с подсчетом подстрок в строке python 2.7
Начало » Python для новичков » Класическая задача с подсчетом подстрок в строке python 2.7
1 2
Senhion
День добрый,
Не могу сообразить как решить на python 2.7 задачку с подсчетом “подстрок” в “строке”.

дан список например
a = [0,1,2,1,1,1,1]
необходимо найти сумму непрерывных повторений (неуверен в правильности формулировки)
т.е. на выходе получить словарь
 b = {1:3, 4:1}
или например:
a = [a,a,a,b,b,b,a,a,a] 
b = {3:3}

a = [1,1,1,1,0,1,0,1,1,1,1]
b = {1:3, 4:2}

a = [1,0,0,1,1,1,0,0,0,0,1,1,1,1,1]
b = {1:1, 2:1, 3:1, 4:1, 5:1}
amfoterius
Как я понимаю, Вы хотите это сделать без перебора, потому что если с ним, то все делается довольно таки просто:
a = [0,1,2,1,1,1,1,2,3,0] # исходный массив
b = {} #результат
for row in a:
    try:
        b[row] += 1
    except KeyError:
        b[row] = 1
        
print(b)
Senhion
Видимо я не совсем верно описал условие задачи
Мне необходимо подсчитать не количество каждого символа в списке а количество “островов” (непрерывных последовательностей) символов одинакового размера…

т.е. для
a = [1,1,1,1,0,1,0,1,1,1,1]
ваше ренение выдает
b = {0: 2, 1: 9}
а должно
b = {1:3, 4:2}

сейчас пытаюсь решить через формирование частотного словаря (возможно опять в терминах ошибаюсь), но пока все движется очень туго и с большими “а” это наврятли сможет работать.

a = [1,1,1,1,0,0,1,0]
#построение частотного словаря
dictionary = []
for x1 in range(len(a)):
    for y in range(1,len(a) - x1 + 1):
        if dictionary.count(a[x1:(x1+y)]) == 0: dictionary.append(a[x1:(x1+y)])
#оставляем только моно резульаты
mono_dictionary = []
for ent in dictionary:
    if ent.count(ent[0]) == len(ent) : mono_dictionary.append(ent)

дальше скорее всего посчитаю для каждого количесво вхождений и сложу по длинам - но как конкретно я буду это делать дальше еще не придумал

К сожалению “а” планируется длиной в 65000 и более… так что я сомневаюсь что мой способ будет с этим нормально работать…
amfoterius
Senhion
Видимо я не совсем верно описал условие задачи Мне необходимо подсчитать не количество каждого символа в списке а количество “островов” (непрерывных последовательностей) символов одинакового размера…т.е. для

если предположить, что вы знаете, какие символы могут быть в массиве, можно этот массив перевести в строку с разделителем и регулярным выражение искать эти “острова”. Вы получите и количество вхождений и длинну каждого из них.

думаю, на сей раз понял задачу))
Senhion
В принципе да… можно построить словарь - и перевести список в строку.
хорошо, тогда как в строке
str('1,1,1,1,0,0,1,0')
решить выше поставленную задачу? С регулярками вообще ни разу не сталкивался поэтому мозги и пытаются решать привычными методами.
nekey975
Senhion
К сожалению “а” планируется длиной в 65000 и более… так что я сомневаюсь что мой способ будет с этим нормально работать…

Не знаю, подойдет ли Вам, но вот решение “в лоб” :
#!/usr/bin/python
test_data=[['a','a','a','b','b','b','a','a','a'],
           [1,1,1,1,0,1,0,1,1,1,1],
           [1,0,0,1,1,1,0,0,0,0,1,1,1,1,1]]
          
def get_consecutive_stat(in_list):
    resDict = dict()
    counter = 1
    for i in xrange(len(in_list)-1):
        if in_list[i] == in_list[i+1]:
            counter += 1
        else:
            if counter in resDict:
                resDict[counter] += 1
            else:
                resDict[counter] = 1
            counter = 1
    if counter in resDict:
        resDict[counter] += 1
    else:
        resDict[counter] = 1
    return resDict
        
for test in test_data:
    print(get_consecutive_stat(test))
TroSer
from itertools import groupby
from collections import Counter
 
a = [1,0,0,1,1,1,0,0,0,0,1,1,1,1,1]
dictionary = {}
 
occurrences_list = [len(list(group)) for key, group in groupby(a)]
for key1, value in Counter(occurrences_list).items():
    dictionary[key1] = value
 
print dictionary

{1: 1, 2: 1, 3: 1, 4: 1, 5: 1}
Senhion
TroSer, Спасибо - похоже то что надо.
А можно обьяснить что происходит в
occurrences_list = [len(list(group)) for key, group in groupby(a)]
?

я первый раз сталкиваюсь с подобной конструкцией когда перед for стоит что-то, и непонятно что за group? и почему если не брать все это в квадратные скобки вываливается синтаксическая шибка, а квадратные скобки все ставят на свои места?


JOHN_16
Senhion
генератор списка зовется, это чутка особая конструкция; groupby из itertools модуля
PanovSergey
я первый раз сталкиваюсь с подобной конструкцией когда перед for стоит что-то
Это генератор, одна и лучших возможностей в питоне.
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB