生成序列

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