Combine two lists of strings

Question

Given two lists of strings that contain duplicates save for one element in each list, how would you combine the two into a single list that contains one copy of every value in list order? For example, given the following two lists in Python: ``` a = ['Second', 'Third', 'Fourth'] b = ['First', 'Second', 'Third'] ``` Or ``` a = ['First', 'Third', 'Fourth'] b = ['First', 'Second', 'Third'] ``` How would you combine the two lists to get a single list like this: ``` result = ['First', 'Second', 'Third', 'Fourth'] ``` Note that the exact values of the strings cannot necessarily be trusted to help with ordering the elements. I am aware of the possibility that there will be some cases with no definitive way to lock the list down to a particular order, and will probably have to special-case those, but for the general cases I'd rather have a procedure to follow. For example: ``` a = ['First', 'Third', 'Fourth'] b = ['First', 'Second', 'Fourth'] ``` This could have `'Third'` and `'Second'` in ei…

Accepted Answer

If we assume that your two lists are both ordered, and that they are each missing only some elements from the full set, then I can kind of see an algorithm that should work most of the time.

- Take the next index in A.

- Step through B looking for a match:

- If there was a match:

- Remove everything from the start of B up to and including the match in B, and add to C

- If there was no match:

- Add index A to C

- Repeat

- If there's anything left in B, add it to C.

This is the python code for the algorithm:

```
a1 = ['Second', 'Third', 'Fourth']
b1 = ['First', 'Second', 'Third']

a2 = ['First', 'Third', 'Fourth']
b2 = ['First', 'Second', 'Third']

a3 = ['First', 'Third', 'Fourth']
b3 = ['First', 'Second', 'Fourth']

def merge(a, b):
    c = []
    b_oldindex = 0
    for a_index in range(len(a)):
        match = False
        for b_index in range(b_oldindex, len(b)):
            if a[a_index] == b[b_index]:
                c.extend(b[b_oldindex:b_index+1])
                b_oldindex = b_index + 1
                match = True
                break
        if not match:
            c.append(a[a_index])
    if b_oldindex < len(b):
        c.extend(b[b_oldindex:])
    return c

print(merge(a1,b1))
print(merge(a2,b2))
print(merge(a3,b3))
print(merge(b1,a1))
print(merge(b2,a2))
print(merge(b3,a3))
```

Which produces the following output:

```
['First', 'Second', 'Third', 'Fourth']
['First', 'Second', 'Third', 'Fourth']
['First', 'Third', 'Second', 'Fourth']
['First', 'Second', 'Third', 'Fourth']
['First', 'Second', 'Third', 'Fourth']
['First', 'Second', 'Third', 'Fourth']
```

In all of test cases, the only one that fails to produce the correct order is `merge(a3,b3)`.

Solving the problem completely may involve implementing a correct merge algorithm (as used in merge sort), which requires the ability to evaluate the order that elements should be in. You can see a python implementation of merge sort at Rosetta code.

UPDATE:

Given that this is actually to sort the installments in a set of books, you can avoid situations you described in your third set of data by taking additional information into account. Namely, use the `merge` function on lists in the reverse order of copyright or publication date.

For example, in your case:

```
a3 = ['First', 'Third', 'Fourth']  # Second novel
b3 = ['First', 'Second', 'Fourth'] # Third novel
```

`a3`'s book would have been published before `b3`'s book. If you can harvest that kind of metadata, then you could avoid this issue.

Copyright date won't differ between different editions of the same book, but publication date might. Therefore, I'd look at copyright date before publication date.

Combine two lists of strings

Solution

Problem