7

我有一个循环遍历一系列四个（或更少）字符串的脚本。例如：

aaaa
aaab
aaac
aaad

如果能够使用嵌套的 for 循环来实现它，如下所示：

chars = string.digits + string.uppercase + string.lowercase

for a in chars:
    print '%s' % a   
    for b in chars:
        print '%s%s' % (a, b)
        for c in chars:
            print '%s%s%s' % (a, b, c)
            for d in chars:
                print '%s%s%s%s' % (a, b, c, d)

这种循环嵌套是一件坏事吗？如果是这样，完成我正在做的事情的更好方法是什么？

4

7 回答 7

16 
import string
import itertools

chars = string.digits + string.letters
MAX_CHARS = 4
for nletters in range(MAX_CHARS):
    for word in itertools.product(chars, repeat=nletters + 1):
        print (''.join(word))

这将打印15018570您要查找的所有单词。如果您想要更多/更少的单词，只需更改MAX_CHARS变量即可。对于任意数量的字符，它仍然只有两个fors，您不必重复自己。并且可读性很好。.

于 2009-01-27T02:46:03.343 回答
6

我将提交我的答案作为最具可读性和可扩展性的答案:)

import string
chars = [''] + list(string.lowercase)

strings = (a+b+c+d for a in chars
                   for b in chars
                   for c in chars
                   for d in chars)

for string in strings:
    print string

编辑：实际上，这是不正确的，因为它会产生长度<4的所有字符串的重复项。从数组中删除空字符串chars只会产生 4 个字符的字符串。

通常我会删除这个答案，但如果你需要生成相同长度的字符串，我仍然有点喜欢它。

于 2009-01-27T03:07:09.103 回答
4

首先为程序员写 - 其次是计算机。
如果它是清晰易懂的，那么它是正确的。

如果速度很重要并且编译器无论如何都没有优化它并且如果你测量它并且这是问题 - 然后想一个更快更聪明的方法！

于 2009-01-27T02:37:32.360 回答
3

我不认为这是一件坏事，只要你理解（并记录:-)它。我不怀疑可能有更 Pythonic 的方式或更聪明的解决方案（使用 lambdas 或诸如此类），但我一直更喜欢可读性而不是聪明。

由于您必须生成 1、2、3 和 4 字符“单词”的所有可能性，因此此方法与任何方法一样好。我不确定要花多长时间才能有效地生成（非常粗略）1400 万行输出（但可能每个解决方案都会遇到这个问题）。

预先计算公共前缀可能会提高速度，但你最好测量它来检查（总是检查，永远不要假设）：

chars = string.digits + string.uppercase + string.lowercase
for a in chars:
    print a
    for b in chars:
        ab = '%s%s' % (a, b)
        print ab
        for c in chars:
            abc = '%s%s' % (ab, c)
            print abc
            for d in chars:
                print '%s%s' % (abc, d)

编辑：我实际上做了一些基准测试（使用 Windows-Python 2.6.1）——这个版本与原来的 2.84 相比需要大约 2.25 个时间单位，所以它快了 26%。我认为这可能保证它的使用（同样，只要它清楚地记录了它试图实现的目标）。

于 2009-01-27T02:35:03.833 回答
2

@nosklo和@Triptych的解决方案产生不同的结果：

>>> list(map(''.join, itertools.chain.from_iterable(itertools.product("ab", 
...     repeat=r) for r in range(4)))) # @nosklo's 

[''，'a'，'b'，'aa'，'ab'，'ba'，'bb'，'aaa'，'aab'，'aba'，'abb'，'baa'，
 'bab'，'bba'，'bbb']

>>> ab = ['']+list("ab")
>>> list(map(''.join, (a+b+c for a in ab for b in ab for c in ab)))  

[''，'a'，'b'，'a'，'aa'，'ab'，'b'，'ba'，'bb'，'a'，'aa'，'ab'，'aa ',
 'aaa'，'aab'，'ab'，'aba'，'abb'，'b'，'ba'，'bb'，'ba'，'baa'，'bab'，
 'bb'、'bba'、'bbb']

这是修改后的@Triptych 的解决方案，它产生与@nosklo 相同的输出：

>>> ab = "ab"
>>> list(map(''.join, itertools.chain([''], ab, (a+b for a in ab for b in ab),
...     (a+b+c for a in ab for b in ab for c in ab))))

[''，'a'，'b'，'aa'，'ab'，'ba'，'bb'，'aaa'，'aab'，'aba'，'abb'，'baa'，
 'bab'，'bba'，'bbb']
于 2009-01-27T11:01:47.320 回答
1

有许多算法可以生成集合的每个排列。你在这里想要的是一个相关的问题，但不是直接类似的。 推荐阅读

于 2009-01-27T02:34:44.957 回答
1

它并不能完全回答问题，但这将返回n给定最大长度的第 th 个组合和要使用的字母表中的字符：

#!/usr/bin/python

def nth_combination(n, maxlen=4, alphabet='abc'):
    """
    >>> print ','.join(nth_combination(n, 1, 'abc') for n in range(3))
    a,b,c
    >>> print ','.join(nth_combination(n, 2, 'abc') for n in range(12))
    a,aa,ab,ac,b,ba,bb,bc,c,ca,cb,cc
    >>> import string ; alphabet = string.ascii_letters + string.digits
    >>> print ','.join(nth_combination(n, 4, alphabet) for n in range(16))
    a,aa,aaa,aaaa,aaab,aaac,aaad,aaae,aaaf,aaag,aaah,aaai,aaaj,aaak,aaal,aaam
    >>> print ','.join(nth_combination(n, 4, alphabet)
    ...                for n in range(0, 14000000, 10**6))
    a,emiL,iyro,mKz2,qWIF,u8Ri,zk0U,Dxav,HJi9,LVrM,P7Ap,UjJ1,YvSE,2H1h
    """
    if maxlen == 1:
        return alphabet[n]
    offset, next_n = divmod(n, 1 + len(alphabet)**(maxlen-1))
    if next_n == 0:
        return alphabet[offset]
    return alphabet[offset] + nth_combination(next_n-1, maxlen-1, alphabet)

if __name__ == '__main__':
    from doctest import testmod
    testmod()

这当然只有当您需要随机访问组合集合而不是总是遍历它们时才有意义。

如果maxlen很高，则可以实现一些速度优化，例如通过摆脱字符串连接并重新计算递归的每个级别的alphabet长度maxlen-1。非递归方法也可能有意义。

于 2009-01-27T12:15:51.990 回答