python - 生成所有长度为 X 且以 '0' 结尾且没有相邻的 '1' 的字符串

Question

我需要生成满足以下两个规则的特定长度 X 的所有可能字符串:

1. 必须以'0'结尾
2. 不能有两个或更多个相邻的'1'

例如，当 X = 4 时，所有“合法”字符串都是 [0000, 0010, 0100, 1000, 1010]。

我已经写了一段递归代码，它只是将新找到的字符串附加到列表中。

def generate(pre0, pre1, cur_len, max_len, container = []):
    if (cur_len == max_len-1):
        container.append("".join([pre0, pre1, "0"]))
        return

    if (pre1 == '1'):
        cur_char = '0'
        generate(pre0+pre1, cur_char, cur_len+1, max_len, container)
    else:   
        cur_char = '0'
        generate(pre0+pre1, cur_char, cur_len+1, max_len, container)
        cur_char = '1'
        generate(pre0+pre1, cur_char, cur_len+1, max_len, container)

if __name__ == "__main__": 
    container = []
    _generate("", "", 0, 4, container)
    print container

但是，当 X 达到 100+ 时，由于内存复杂性，此方法将不起作用。我不熟悉 Python 中的生成器方法，所以这里的任何人都可以帮我弄清楚如何将它重写成生成器吗？非常感谢!

附言我正在研究 Project Euler 问题，这不是家庭作业。

更新 1:

感谢前 3 个答案，我使用的是 Python 2.7，可以切换到 python 3.4。我要求生成器的原因是我什至无法在我的内存中保存最终结果列表。一个快速的数学证明将表明长度 X 有 Fibonacci(X) 个可能的字符串，这意味着我必须真正使用生成器并即时过滤结果。

Answer 1

Lame 基于字符串的测试“11”是否包含在格式化的字符串中，如果不包含则返回(对于每个偶数，直到 2^maxlen):

def gen(maxlen):
    pattern = "{{:0{}b}}".format(maxlen)
    for i in range(0, 2**maxlen, 2):
        s = pattern.format(i) # not ideal, because we always format to test for "11"
        if "11" not in s:
            yield s

高级数学方法(M xor M * 2 = M * 3):

def gen(maxlen):
    pattern = "{{:0{}b}}".format(maxlen)
    for i in range(0, 2**maxlen, 2):
        if i ^ i*2 == i*3:
            yield pattern.format(i)

这是 6 种不同实现(Python 3!)的基准:

from time import clock
from itertools import product

def math_range(maxlen):
    pattern = "{{:0{}b}}".format(maxlen)
    for i in range(0, 2**maxlen, 2):
        if i ^ i*2 == i*3:
            yield pattern.format(i)


def math_while(maxlen):
    pattern = "{{:0{}b}}".format(maxlen)
    maxnum = 2**maxlen - 1
    i = 0
    while True:
        if i ^ i*2 == i*3:
            yield pattern.format(i)
        if i >= maxnum:
            break
        i += 2


def itertools_generator(max_len):
    return filter(lambda i: '11' not in i, (''.join(i) + '0' for i in product('01', repeat=max_len-1)))


def itertools_list(maxlen):
    return list(filter(lambda i: '11' not in i, (''.join(i) + '0' for i in product('01', repeat=maxlen-1))))


def string_based(maxlen):
    pattern = "{{:0{}b}}".format(maxlen)
    for i in range(0, 2**maxlen, 2):
        s = pattern.format(i)
        if "11" not in s:
            yield s


def generate(pre0, pre1, cur_len, max_len):
    if (cur_len == max_len-1):
        yield "".join((pre0, pre1, "0"))
        return

    if (pre1 == '1'):
        yield from generate(pre0+pre1, "0", cur_len+1, max_len)
    else:
        yield from generate(pre0+pre1, "0", cur_len+1, max_len)
        yield from generate(pre0+pre1, "1", cur_len+1, max_len)

def string_based_smart(val):
    yield from generate("", "", 0, val)


def benchmark(val, *funcs):
    for i, func in enumerate(funcs, 1):
        start = clock()
        for g in func(val):
            g
        print("{}. {:6.2f} - {}".format(i, clock()-start, func.__name__))

benchmark(24, string_based_smart, math_range, math_while, itertools_generator, itertools_list, string_based)

字符串长度 = 24(以秒为单位)的一些数字:

1.   0.24 - string_based_smart
2.   1.73 - math_range
3.   2.59 - math_while
4.   6.95 - itertools_generator
5.   6.78 - itertools_list
6.   6.45 - string_based

shx2 的算法显然是赢家，其次是数学。如果比较两种数学方法的结果，Pythonic 代码会产生很大的不同(注意:范围也是生成器)。

值得注意:itertools_* 函数的执行速度几乎同样慢，但是 itertools_list 需要更多的内存来存储列表(在我的测试中约为 6 MB)。所有其他基于生成器的解决方案都具有最小的内存占用，因为它们只需要存储当前状态而不是整个结果。

所显示的函数都没有炸毁堆栈，因为它们不使用实际的递归。 python does not optimize tail recursion ，因此您需要循环和生成器。

//edit: math_range 的简单 C++ 实现(MSVS 2013):

#include "stdafx.h"
#include <iostream>
#include <bitset>
#include <ctime>
#include <fstream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    const unsigned __int32 maxlen = 24;
    const unsigned __int32 maxnum = 2 << (maxlen - 1);

    clock_t begin = clock();

    ofstream out;
    out.open("log.txt");
    if (!out.is_open()){
        cout << "Can't write to target";
        return 1;
    }

    for (unsigned __int32 i = 0; i < maxnum; i+=2){
        if ((i ^ i * 2) == i * 3){
            out << std::bitset<maxlen>(i) << "\n"; // dont use std::endl!
        }
    }

    out.close();

    clock_t end = clock();
    double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    cout << elapsed_secs << endl;

    return 0;
}

maxlen = 24 (/Ox) 需要 0.08 秒 (!)。

shx2 算法在 C++ 中的实现非常重要，因为递归方法会导致堆栈溢出(哈哈)，并且没有yield。见:

• Why wasn't yield added to C++0x?
• http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
• http://blog.think-async.com/2009/08/secret-sauce-revealed.html
• http://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and

但如果您想要原始速度，那就别无选择。