从两个数组增加序列

Question

给定两个相同长度 n 的整数列表 a 和 b。找到严格递增的整数序列的计数，i[0] < i[1] < ... < i[n-1]使得min(a[i], b[i]) <= i[i] <= max(a[i], b[i])对于每个i。例子输入：a= [1,3,1,6]b= [6,5,4,4]输出：4这四个序列将是：[1,3,4,5][1,3,4,6][2,3,4,5][2,3,4,5]这是我试过的a=[1,3,1,6]b=[6,5,4,4]P=[]for i in range(len(a)):    if i<len(a)-1:        if max(a[i],b[i])>=max(a[i+1],b[i+1]):            P.append([x for x in range(min(a[i],b[i]),min(max(a[i],b[i]),max(a[i+1],b[i+1])))])        else:            P.append([x for x in range(min(a[i],b[i]),1+min(max(a[i],b[i]),max(a[i+1],b[i+1])))])    else:        P.append([x for x in range(min(a[i],b[i]),max(a[i],b[i])+1)])for i in range(len(a)):    if i<len(a)-1 and P[i+1][-1]<=P[i][-1]:        P[i]=[x for x in range(P[i][0],P[i+1][-1])]    if i>0 and P[i][0]<=P[i-1][0]:        P[i]=[x for x in range(P[i-1][0]+1,1+P[i][-1])cnt=1for i in P:    cnt*=len(i)print(cnt)我所做的是我采用了这个设置1 2 3 4 5 6    3 4 5 1 2 3 4      4 5 6 并将其减少到这个1 2   3     4       5 6 删除所有不会进入序列的数字。现在我要做的是，只需乘以每个行序列的 len。当有这样的情况时，问题就出现了。1 2 3    3 4      4 5        5 6 现在长度的简单乘法不成立。这就是我被困的地方。

Answer 1

这是一种适合递归解决方案的问题，因此这里有一个可能的替代实现。（抱歉，我还没有尝试掌握您的代码，也许其他人会。）

def sequences(a, b, start_index=0, min_val=None):

    """

    yields a sequence of lists of partial solutions to the original

    problem for sublists going from start_index to the end of the list

    subject to the constraint that the first value cannot be less than

    min_val (if not None)

    Example: with a=[3,4,5,6], b=[6,5,0,4], start_index=2, minval=4, 

    it is looking at the [5,6] and the [0,4] part, and it would yield

     [4,5] [4,6] and [5,6]

    If the start index is not already the last one, then it uses a

    recursive call.

    """

    limits = a[start_index], b[start_index]

    lower = min(limits)

    higher = max(limits)

    if min_val is not None and min_val > lower:

        lower = min_val  # impose constraint

    options = range(lower, higher + 1)

    is_last = start_index == len(a) - 1

    for val in options:

        if is_last:

            yield [val]

        else:

            # val followed by each of the lists from the recursive 

            # callback - passing min_val=val+1 imposes the constraint

            # of strictly increasing numbers

            for seq in sequences(a, b, start_index+1, min_val=val+1):

                yield [val, *seq]

for seq in sequences([1,3,1,6], [6,5,4,4]):

    print(seq)

这给出：

[1, 3, 4, 5]

[1, 3, 4, 6]

[2, 3, 4, 5]

[2, 3, 4, 6]

请注意，我并不是说上面的方法特别有效：递归函数可能会使用相同的参数被调用不止一次——例如，无论您是从 1,3 还是 2,3 开始，它都会进行相同的计算来工作了解接下来会发生什么——因此您可能希望在将其用于大型列表之前实施某种缓存。显然，缓存有内存开销，因此制定最佳整体策略来应对这一问题可能是一个相当困难的问题。