title: Smallest list containing all elements from two lists, while preserving order
body: <p>I am unsure how to combine the items from two lists of integers such that the order of the items is preserved and the resultant list, if concatenated into one integer, is as small as possible.</p>
  
  <p>Potentially similar to this question, although the answer given doesn't address my size constraint:
  <a href="https://stackoverflow.com/questions/14241320/interleave-different-length-lists-elimating-duplicates-and-preserve-order-in-py">Interleave different length lists, elimating duplicates and preserve order in Python</a></p>
  
  <p>For instance, given:</p>
  
  <pre><code>a = [3,4,5,7,9,2]
  b = [3,5,7,4,2,8]
  </code></pre>
  
  <p>The shortest possible combination of these two lists would be:</p>
  
  <pre><code>c = [3,4,5,7,4,9,2,8]
  </code></pre>
  
  <p>With a concatenated integer value of 34574928</p>
  
  <p>There are instances in which the ordering of the numbers would not affect list length, but would affect the size of the concatenated integer. In the example given, the 4 and 9 could be swapped while still maintaining order of the items, but the final number would be larger than necessary.</p>
  
  <p>For further clarification:</p>
  
  <p>The final list must contain every instance of each digit from the two original lists. To better represent the combination of the two in the above example:</p>
  
  <pre><code>a = [3,4,5,7,  9,2  ]
  b = [3,  5,7,4,  2,8]
  c = [3,4,5,7,4,9,2,8]
  </code></pre>
  
  <p>Of course, it will not always work out so cleanly. In this case, four of the digits from the two lists (3, 5, 7, and 2) could be merged complete. Four of the digits (4, 4, 9, and 8) could not be combined without creating larger list. For example:</p>
  
  <pre><code>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]
  </code></pre>
  
  <p>In this case, I combined only the 3 and one of the 4s. When the items from those two example results are concatenated, we get:</p>
  
  <pre><code>c =     34574928
  bad_c = 357492892
  </code></pre>
  
  <p>They both satisfy the ordering requirement, but because there is a different result which satisfies the ordering requirement but is smaller than bad_c when concatenated into an integer, bad_c is an incorrect result.</p>