数字和字母的组合

Question

#!/usr/bin/python
import random
lower_a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
upper_a = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
num = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

all = []
all = " ".join("".join(lower_a) + "".join(upper_a) + "".join(num))
all = all.split()
x = 1
c = 1
while x < 10:
    y = []
    for i in range(c):
            a = random.choice(all)
            y.append(a)
    print "".join(y)
    x += 1
    c += 1

我现在的输出结果大概是这样的：

5
hE
HAy
1kgy
Pt6JM
2pFuCb
Jv5osaX
5q8PwWAO
SvHWRKfI5

我该怎么做才能让它有条理地遍历所有字母的组合（包括大写和小写），然后在这个长度的基础上加1，再重复这个过程呢？

Answer 1

看看itertools模块中的组合函数（http://docs.python.org/library/itertools.html#itertools.combinations）

import itertools
... setup all ...
for ilen in range(1, len(all)):
  for combo in itertools.combinations(all, ilen):
    print combo

Answer 2

用Python的方式来做这件事；)

打印出所有的组合：

from itertools import combinations

symbols = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
          "abcdefghijklmnopqrstuvwxyz"
          "0123456789"
max_length = len(symbols)

for length in xrange(1, max_length + 1):
    for word in map(''.join, combinations(symbols, length)):
        print word

更好的方法是创建一个生成器对象，它可以逐个产生组合，这样你就可以在后面决定怎么处理这些组合，而不需要在内存中存储 2 ** 62 个字符串（大约 7.6040173890593902e+35 字节）。

from itertools import combinations, product

symbols = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
          "abcdefghijklmnopqrstuvwxyz"
          "0123456789"
max_length = len(symbols)

# generator of all combinations
def words1(chars=symbols, max_len=max_length):
    for length in xrange(1, max_length + 1):
        for word in map(''.join, combinations(symbols, length)):
            yield word

# generator of all combinations allowing repetitions
def words1(chars=symbols, max_len=max_length):
    for length in xrange(1, max_length + 1):
        for word in map(''.join, product(*[symbols]*length)):
            yield word


for word in words1():
    #do something with word
    print word

像 combinations 和 product 这样的函数，还有很多其他函数，都是返回迭代器而不是列表，这样可以节省内存：

>>> print combinations('0123456789',2)
<itertools.combinations object at 0x13e34b0>
>>> print list(combinations('0123456789',2))
[('0', '1'), ('0', '2'), ('0', '3'), ('0', '4'), ('0', '5'), ('0', '6'), ('0', '7'), ('0', '8'), ('0', '9'), ('1', '2'), ('1', '3'), ('1', '4'), ('1', '5'), ('1', '6'), ('1', '7'), ('1', '8'), ('1', '9'), ('2', '3'), ('2', '4'), ('2', '5'), ('2', '6'), ('2', '7'), ('2', '8'), ('2', '9'), ('3', '4'), ('3', '5'), ('3', '6'), ('3', '7'), ('3', '8'), ('3', '9'), ('4', '5'), ('4', '6'), ('4', '7'), ('4', '8'), ('4', '9'), ('5', '6'), ('5', '7'), ('5', '8'), ('5', '9'), ('6', '7'), ('6', '8'), ('6', '9'), ('7', '8'), ('7', '9'), ('8', '9')]

Answer 3

最好不要重复实现标准库中已经有的功能。

可以看看标准库模块 itertools。特别是里面的 combinations()、permutations() 和 product() 这几个函数。

import itertools

lower_a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
upper_a = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
num = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

all = lower_a + upper_a + num

for r in range(1, 3):
    for s in itertools.product(all, repeat=r):
         print ''.join(s)

如果你的Python版本比较旧，可能用不了这些函数。不过你可以看看Python 2.6的文档，里面有这些函数的实现方法。例如，itertools.product的实现是：

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

你也可以尝试用递归的方法来解决这个问题：

lower_a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
upper_a = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
num = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

all = lower_a + upper_a + num

def recursive_product(myList, length, myString = ""):
    if length == 0:
        print myString
        return
    for c in myList:
        recursive_product(myList, length-1, myString + c)
    
for r in range(1, 3):
    recursive_product(all, r)