Может ли кто-нибудь предоставить более питонный способ генерации последовательности Морриса? - PullRequest
Новая
       28

Может ли кто-нибудь предоставить более питонный способ генерации последовательности Морриса?

5 голосов
/ 16 февраля 2009

Я пытаюсь сгенерировать последовательность Морриса в python. Мое текущее решение ниже, но я чувствую, что только что написал c на Python. Кто-нибудь может предложить более питонное решение? 

def morris(x):
    a = ['1', '11']
    yield a[0]
    yield a[1]
    while len(a) <= x:
        s = ''
        count = 1
        al = a[-1]
        for i in range(0,len(al)):
            if i+1 < len(al) and al[i] == al[i+1]:
                count += 1
            else:
                s += '%s%s' % (count, al[i])
                count = 1
        a.append(s)
        yield s
a = [i for i in morris(30)]

Ответы [ 2 ]

25 голосов
/ 16 февраля 2009

itertools.groupby, кажется, идеально подходит! Просто определите функцию next_morris следующим образом: 

def next_morris(number):
    return ''.join('%s%s' % (len(list(group)), digit)
                   for digit, group in itertools.groupby(str(number)))

Вот и все !!! Посмотрите: 

print next_morris(1)
11
print next_morris(111221)
312211

Я мог бы использовать это для создания генератора: 

def morris_generator(maxlen, start=1):
    num = str(start)
    while len(num) < maxlen:
        yield int(num)
        num = next_morris(num)

Использование: 

for n in morris_generator(10):
    print n

Результаты: 

1
11
21
1211
111221
312211
13112221
6 голосов
/ 16 февраля 2009 
from itertools import groupby, islice

def morris():
    morris = '1'
    yield morris
    while True:
        morris = groupby(morris)
        morris = ((len(list(group)), key) for key, group in morris)
        morris = ((str(l), k) for l, k in morris)
        morris = ''.join(''.join(t) for t in morris)
        yield morris

print list(islice(morris(), 10))

Прежде всего я бы сделал итератор бесконечным и позволил бы потребителю решать, сколько он хочет. Таким образом, он мог либо получить каждое число Морриса, которое короче x, либо первые x числа и т. Д.

Тогда, очевидно, нет необходимости хранить весь список предыдущих чисел Морриса в списке, так как рекурсия в любом случае только n := f(n-1).

Наконец, использование itertools для придания ему функциональности всегда стоит того, чтобы разобраться с ним; два;) Я разбил выражение генератора на несколько строк, чтобы сделать его немного более привлекательным.

Главное уродство в этом решении проистекает из того факта, что len() не может быть вызван итератором и дает нам int, где нам нужна str. Другой хит - это вложенный str.join), чтобы снова сплющить все это в str.

Если вы хотите начать последовательность с произвольных чисел, определите функцию следующим образом: 

def morris(morris=None):
    if morris is None:
        morris = '1'
[...]

Если вы хотите развернуть этот генератор, вы можете написать его так: 

def morris():
    morris = '1'
    yield morris
    while True:
        print morris
        morris = ''.join(''.join(t) 
                     for t in ((str(len(list(group))), key) 
                        for key, group in groupby(morris)))
        yield morris

Я не уверен, что мне нравится разделение на две функции, но это, кажется, самое читаемое решение: 

def m_groupby(s):
    for key, group in groupby(s):
        yield str(len(list(group)))
        yield key

def morris():
    morris = '1'
    yield morris
    while True:
        morris = ''.join(m_groupby(morris))
        yield morris

Надеюсь, вам понравится!

...