5

我正在尝试在 python中生成莫里斯序列。我目前的解决方案如下，但我觉得我只是用python写了c。任何人都可以提供更pythonic的解决方案吗？

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

2 回答 2

24

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
于 2009-02-16T18:07:12.907 回答
6 
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()不能在迭代器上调用，并在我们需要 str 的地方给了我们一个 int。另一个小问题是嵌套的 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

希望你喜欢！

于 2009-02-16T18:01:25.573 回答