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

Question

我不太确定怎么把两个整数列表里的项组合在一起，要求保持原来的顺序，并且最终合成的整数尽可能小。

这个问题可能和这个问题有点相似，不过给出的答案没有考虑到我的大小限制：交错不同长度的列表，消除重复并保持顺序

比如，假设有：

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

这里有一个简单的算法，我觉得可以用，具体的实现比较简单，所以我就不贴代码了。

1. 对于两个列表，先找出第一个相同的元素，然后把这个元素之前的所有元素收集起来。假设这两个列表是：a 和 b。

2. a. 如果没有任何相同的元素，那就通过比较两个列表的第一个元素来合并它们，然后把较小的列表的索引加一，再继续比较。你明白这个意思了吧！

2. b. 然后假设我们说，a[3] 和 b[4] 是相同的元素，那么就把 a[0] 到 a[2] 和 b[0] 到 b[3] 的元素都收集起来，然后用没有共同元素的情况来合并这7个元素，最后在末尾加上 a[3] 的值。

3. 类似地，继续这个过程直到列表的末尾。在最后一个添加的元素之后，再合并剩下的元素。

4. 为此，我们可以写一个函数，接受两个列表的起始和结束索引，用来合并子列表。

我希望这个解决方案有效，看起来是对的，但我还没有尝试过。如果我漏掉了什么，请告诉我。

Answer 2

这里有一个比较长但正确的实现方法，主要是用递归来完成的（根据问题讨论来看，我觉得是对的）。

重要的几点：

• 我用 .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]