在Python中计算长度为M的第N个序列

Question

我正在编写一个库，将用于验证。我将有一组元素和一个测试系统，以某种顺序消耗它们。该集合表示所有可能的输入，并且系统将接收这些元素的有限序列。

由于集有限序列的将是无限的，我并不想计算一组所有序列，而是采用蟒蛇发电机设想到完成以下任务：

def seq(s): # s is a set 
    length = 0 
    nth = 0 
    # r = calculate nth sequence of length 
    # if there are no more sequences of length, length += 1 
    # else n += 1, yield r 

我最终会延长这到内射和双射序列，但是现在这个集合的元素可以出现任何次数。

发电机是最好的方法吗？使用像这样的生成器是否消除了递归获得的任何简单性？任何人都可以指向我可以帮助我的任何itertools（或其他模块）捷径吗？

Answer 1

这听起来像你正在寻找itertools.product。我相信这会做什么你问：

def seq(s): 
    length = 1 
    while True: 
     for p in itertools.product(s, repeat=length): 
      yield p 
     length += 1 

现在你可以做这样的事情：

>>> zip(range(10), seq(set((1, 2, 3)))) 
[(0, (1,)), (1, (2,)), (2, (3,)), (3, (1, 1)), (4, (1, 2)), 
(5, (1, 3)), (6, (2, 1)), (7, (2, 2)), (8, (2, 3)), (9, (3, 1))] 

或者这样：

>>> test_seq = itertools.izip(itertools.count(), seq(set((1, 2, 3)))) 
>>> for i in range(10): 
...  next(test_seq) 
... 
(0, (1,)) 
(1, (2,)) 
(2, (3,)) 
(3, (1, 1)) 
(4, (1, 2)) 
(5, (1, 3)) 
(6, (2, 1)) 
(7, (2, 2)) 
(8, (2, 3)) 
(9, (3, 1)) 

这也可以被进一步压缩，使用其他itertools：

>>> from itertools import chain, product, count 
>>> s = set((1, 2, 3)) 
>>> test_seq = chain.from_iterable(product(s, repeat=n) for n in count(1)) 
>>> zip(range(10), test_seq) 
[(0, (1,)), (1, (2,)), (2, (3,)), (3, (1, 1)), (4, (1, 2)), (5, (1, 3)), 
(6, (2, 1)), (7, (2, 2)), (8, (2, 3)), (9, (3, 1))]