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