python - 包含两个列表中所有元素的最小列表，同时保留顺序

Question

我不确定如何组合两个整数列表中的项目，以便保留项目的顺序，并且如果将结果列表连接成一个整数，则结果列表尽可能小。

可能类似于这个问题，虽然给出的答案没有解决我的大小限制: Interleave different length lists, elimating duplicates and preserve order in Python

例如，给定:

a = [3,4,5,7,9,2]
b = [3,5,7,4,2,8]

这两个列表的最短可能组合是:

c = [3,4,5,7,4,9,2,8]

连接整数值为 34574928

在某些情况下，数字的排序不会影响列表长度，但会影响串联整数的大小。在给出的示例中，可以交换 4 和 9，同时仍然保持项目的顺序，但最终的数字会比必要的大。

进一步说明:

最终列表必须包含两个原始列表中每个数字的每个实例。为了更好地表示上述示例中两者的组合:

a = [3,4,5,7,  9,2  ]
b = [3,  5,7,4,  2,8]
c = [3,4,5,7,4,9,2,8]

当然，它不会总是那么干净。在这种情况下，两个列表(3、5、7 和 2)中的四个数字可以完全合并。如果不创建更大的列表，则无法组合其中的四个数字(4、4、9 和 8)。例如:

a =     [3,    4,5,7,  9,2]
b =     [3,5,7,4,  2,8    ]
bad_c = [3,5,7,4,9,2,8,9,2]

在这种情况下，我只组合了 3 和 4 之一。当将这两个示例结果中的项目连接起来时，我们得到:

c =     34574928
bad_c = 357492892

它们都满足排序要求，但由于有一个满足排序要求但拼接成整数时小于bad_c的结果不同，所以bad_c是不正确的结果。

Answer 1

这是一个相当长但正确的(据我从问题讨论中可以看出)使用递归的实现。

要点:

• 我使用 .pop(index) 遍历两个列表。这让我可以使用递归，因为随着函数的递归，两个列表都变得越来越小，导致一个列表属于 len(0)。
• 可以从任一列表中选择数字，并且可以从单个列表中连续选择的数字没有限制。
• 不允许连续重复。
• 比较两个不相等的数字时，较小的数字总是在较大的位置。 23xxx 始终低于 32xxx。

基本上，如果我有类似 [1,2,3] 的东西，然后是 [6,0,4]，所有第一个列表中的数字将在第二个列表中的第一个数字之前，因为 1236xx 将始终小于 6xxxxx，1236xx 小于 16xxxx，而 1236xx 小于 126xxx，无论为 x 选择的值如何.

z = [None]
#set to None so that z[-1] doesn't throw an out-of-range error

def small_list(a,b): #recursive function

    ### BASE CASE ###

    if len(a) == 0: #if one list empty, can only add rest of other list
        for i in b:
            if i != z[-1]: #account for duplicates
                z.append(i)
            # else: #don't add duplicates

        return z.pop(0) #end recursion, remove extraneous None

    elif len(b) == 0: #if one list empty, can only add rest of other list
        for j in a:
            if j != z[-1]:#account for duplicates
                z.append(j)
            # else: #don't add duplicates

        return z.pop(0) #end recursion, remove extraneous None

    #Otherwise, we need to check whichever is smaller.  
    #The smaller number should ALWAYS go in the larger place (tens,hundreds,etc.) to make a smaller number.

    ### RECURSIVE CASE ###

    if a[0] < b[0]:
        if a[0] != z[-1]:
            z.append(a.pop(0))
        else:
            a.pop(0)
    elif a[0] > b[0]:
        if b[0] != z[-1]:
            z.append(b.pop(0))
        else:
            b.pop(0)
    elif a[0] == b[0]:
        a.pop(0)

    small_list(a,b) # recur

例子:

z = [None]

l1 = [1,2,3,2]
l2 = [2,1,1,1]

small_list(l1,l2)
print z

第一个示例打印 [1, 2, 1, 3, 2]，现在是正确的。

z = [None]

l1 = [1,2,3]
l2 = [4,5,6]

small_list(l1,l2)
print z

第二个示例打印 [1, 2, 3, 4, 5, 6] 这也是现在正确的。

下面是它如何计算您上面给出的示例的流程:

# The format is: [final list]  len(a)  [list a]  len(b)  [list b]

[] len(a) = 6 [3, 4, 5, 7, 9, 2] len(b) = 6 [3, 5, 7, 4, 2, 8]
# 3 repeated, so remove it.
[] len(a) = 5 [4, 5, 7, 9, 2] len(b) = 6 [3, 5, 7, 4, 2, 8]
# add lower of first two indices to final (4 v 3), and remove from corresponding list
[3] len(a) = 5 [4, 5, 7, 9, 2] len(b) = 5 [5, 7, 4, 2, 8]
# add lower of first two indices to final (4 v 5), and remove from corresponding list
[3, 4] len(a) = 4 [5, 7, 9, 2] len(b) = 5 [5, 7, 4, 2, 8]
# 5 repeated, so remove it.
[3, 4] len(a) = 3 [7, 9, 2] len(b) = 5 [5, 7, 4, 2, 8]
# add lower of first two indices to final (7 v 5), and remove from corresponding list
[3, 4, 5] len(a) = 3 [7, 9, 2] len(b) = 4 [7, 4, 2, 8]
# 7 repeated, so remove it.
[3, 4, 5] len(a) = 2 [9, 2] len(b) = 4 [7, 4, 2, 8]
# add lower of first two indices to final (9 v 7), and remove from corresponding list
[3, 4, 5, 7] len(a) = 2 [9, 2] len(b) = 3 [4, 2, 8]
# add lower of first two indices to final (9 v 4), and remove from corresponding list
[3, 4, 5, 7, 4] len(a) = 2 [9, 2] len(b) = 2 [2, 8]
# add lower of first two indices to final (9 v 2), and remove from corresponding list
[3, 4, 5, 7, 4, 2] len(a) = 2 [9, 2] len(b) = 1 [8]
# add lower of first two indices to final (9 v 8), and remove from corresponding list
[3, 4, 5, 7, 4, 2, 8] len(a) = 2 [9, 2] len(b) = 0 []
# list b is empty, add first element of list a (if non-duplicate)
[3, 4, 5, 7, 4, 2, 8, 9] len(a) = 1 [2] len(b) = 0 []
# list b is empty, add first element of list a (if non-duplicate)

#Finally:
[3, 4, 5, 7, 4, 2, 8, 9, 2]