Уведомления

Группа в Telegram: @pythonsu

#1 Фев. 11, 2014 07:51:02

Senhion
Зарегистрирован: 2012-08-13
Сообщения: 37
Репутация: +  0  -
Профиль   Отправить e-mail  

Класическая задача с подсчетом подстрок в строке python 2.7

День добрый,
Не могу сообразить как решить на 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}

Отредактировано Senhion (Фев. 11, 2014 07:51:50)

Офлайн

#2 Фев. 11, 2014 10:49:42

amfoterius
Зарегистрирован: 2014-02-11
Сообщения: 4
Репутация: +  0  -
Профиль   Отправить e-mail  

Класическая задача с подсчетом подстрок в строке python 2.7

Как я понимаю, Вы хотите это сделать без перебора, потому что если с ним, то все делается довольно таки просто:

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)

Офлайн

#3 Фев. 11, 2014 11:19:16

Senhion
Зарегистрирован: 2012-08-13
Сообщения: 37
Репутация: +  0  -
Профиль   Отправить e-mail  

Класическая задача с подсчетом подстрок в строке python 2.7

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

т.е. для

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 и более… так что я сомневаюсь что мой способ будет с этим нормально работать…

Отредактировано Senhion (Фев. 11, 2014 12:10:12)

Офлайн

#4 Фев. 11, 2014 13:48:53

amfoterius
Зарегистрирован: 2014-02-11
Сообщения: 4
Репутация: +  0  -
Профиль   Отправить e-mail  

Класическая задача с подсчетом подстрок в строке python 2.7

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

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

думаю, на сей раз понял задачу))

Офлайн

#5 Фев. 11, 2014 14:38:01

Senhion
Зарегистрирован: 2012-08-13
Сообщения: 37
Репутация: +  0  -
Профиль   Отправить e-mail  

Класическая задача с подсчетом подстрок в строке python 2.7

В принципе да… можно построить словарь - и перевести список в строку.
хорошо, тогда как в строке

str('1,1,1,1,0,0,1,0')
решить выше поставленную задачу? С регулярками вообще ни разу не сталкивался поэтому мозги и пытаются решать привычными методами.

Офлайн

#6 Фев. 11, 2014 16:41:32

nekey975
Зарегистрирован: 2014-02-11
Сообщения: 1
Репутация: +  0  -
Профиль   Отправить e-mail  

Класическая задача с подсчетом подстрок в строке python 2.7

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))

Отредактировано nekey975 (Фев. 11, 2014 16:42:01)

Офлайн

#7 Фев. 11, 2014 17:00:26

TroSer
От: Харьков
Зарегистрирован: 2013-11-13
Сообщения: 65
Репутация: +  3  -
Профиль   Отправить e-mail  

Класическая задача с подсчетом подстрок в строке python 2.7

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}

Отредактировано TroSer (Фев. 11, 2014 17:01:08)

Офлайн

#8 Фев. 12, 2014 07:58:10

Senhion
Зарегистрирован: 2012-08-13
Сообщения: 37
Репутация: +  0  -
Профиль   Отправить e-mail  

Класическая задача с подсчетом подстрок в строке python 2.7

TroSer, Спасибо - похоже то что надо.
А можно обьяснить что происходит в

occurrences_list = [len(list(group)) for key, group in groupby(a)]
?

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


Отредактировано Senhion (Фев. 12, 2014 08:03:19)

Офлайн

#9 Фев. 12, 2014 09:09:37

JOHN_16
От: Россия, Петропавловск-Камчатск
Зарегистрирован: 2010-03-22
Сообщения: 3292
Репутация: +  221  -
Профиль   Отправить e-mail  

Класическая задача с подсчетом подстрок в строке python 2.7

Senhion
генератор списка зовется, это чутка особая конструкция; groupby из itertools модуля



_________________________________________________________________________________
полезный блог о python john16blog.blogspot.com

Офлайн

#10 Фев. 12, 2014 09:18:19

PanovSergey
От: Екатеринбург
Зарегистрирован: 2013-12-29
Сообщения: 269
Репутация: +  19  -
Профиль   Адрес электронной почты  

Класическая задача с подсчетом подстрок в строке python 2.7

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

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version