生成序列

Question

我試圖寫一個函數，將作爲輸入長度L和距離D（均爲整數>1）和輸出適合以下參數的所有可能的序列：

1. 開始用數字1
2. 具有L元件
3. 必須每個元素和以下元件之間的D一個1距離

所以，L = 4和D = 2，可能的順序將是：

1 2 3 4 (distance of 1 between each consecutive element) 
1 2 3 5 
1 2 4 5 
1 2 4 6 
1 3 4 5 
1 3 4 6 
1 3 5 6 
1 3 5 7 (distance of 2 between each consecutive element) 

或者，L = 3和D = 3，可能的順序將是：

1 2 3 (distance of 1 between each consecutive element) 
1 2 4 
1 2 5 
1 3 4 
1 3 5 (distance of 2 between each consecutive element) 
1 3 6 
1 4 5 
1 4 6 
1 4 7 (distance of 3 between each consecutive element) 

從手工編碼其中幾個，可能的序列數似乎是D ** (L-1)。起初我只需要2\**7，128個序列不是很難手工創建。不過，我現在需要3**7，甚至可能更大，所以我需要編寫一個函數。

Python是我正在學習的語言。遞歸似乎是做到這一點的方式，但我只練習簡單的遞歸，而且我堅持寫下這個如何精確。盡我所能，我需要一個從for循環中調用自己的函數。這有意義嗎？同樣的結構化功能的方向也將不勝感激。

Answer 1

這裏是一個快速和骯髒的實施

def gen_seq(D, L): 
    for uple in itertools.product(range(1, D+1), repeat=L-1): 
     yield tuple(numpy.cumsum((1,) + uple)) 

Answer 2

您可以使用itertools.product和itertools.accumulate實現你需要的功能：

import itertools 

def f(l, d): 
    for sub in itertools.product(range(1, d+1), repeat=l-1): 
     yield tuple(itertools.accumulate((1,) + sub)) 

for l in f(4, 2): 
    print(l) 

(1, 2, 3, 4) 
(1, 2, 3, 5) 
(1, 2, 4, 5) 
(1, 2, 4, 6) 
(1, 3, 4, 5) 
(1, 3, 4, 6) 
(1, 3, 5, 6) 
(1, 3, 5, 7) 

Answer 3

遞歸的點不僅是正式的代碼在遞歸方式，但以遞歸的方式定向你的思想。仔細比較長度爲3和長度爲4的距離爲2的結果。

a。長度3

1 2 3 
1 2 4 
1 3 4 
1 3 5 

b。長度4

1 2 3 | 4 
1 2 3 | 5 
1 2 4 | 5 
1 2 4 | 6 
1 3 4 | 5 
1 3 4 | 6 
1 3 5 | 6 
1 3 5 | 7 

在長度爲4的結果中，只是長度爲3的結果。這意味着N長度的結果可以從N-1長度導出。

假設我們已經有一個程序來解決k-1長度solve_part(k-1)，通過將k-1的結果擴展到下一個長度k next_len(solve_part(k-1) ...)，這個問題自然是以遞歸方式解決的。

import itertools 

def flatmap(func, *iterable): 
    return itertools.chain.from_iterable(map(func, *iterable)) 

def next_distance(eachlist, D): 
    return map(lambda eachdis: eachlist + [eachlist[-1] + eachdis], range(1,D+1)) 

def next_len(L,D): 
    return flatmap(lambda eachlist: next_distance(eachlist, D), L) 

def solve_it(leng,dis): 
    def solve_part(k): 
    if k == 0: 
     return [[]] 
    elif k == 1: 
     return [[1]] 
    else: 
     return next_len(solve_part(k-1),dis) 
    return solve_part(leng) 

result=solve_it(4,2) 

print([[i for i in j] for j in result])