merging multiple lists with shifting elements into one big list

Question

How can I merge/extend a list to include the elements in another list which contains more information? The problem is the index where shifting occurs is not constant.

[1,2,3,4], [2,3,4,5], [5,6,7,8], [7,8,9,10] into [1,2,3,4,5,6,7,8,9,10]

Lists are a timed snapshot of a time sereis so the sequence and order of the elements should remain and duplicate elements are allowed i.e [1,2,3,4,5,5,6,7,8] and [4,5,5,6,7,8,9,10,11]

the second list contains elements from the first list and more, you could say the second list is the same as the first but it has been shifted to the left and more elements added to it.

For example

l1 = [1,2,3,4,5,5,6,7,8]

l2 = [4,5,5,6,7,8,9,10,11]

results to

l3 = [1,2,3,4,5,5,6,7,8,9,10,11]

Answer 1

As per your second example, even duplicates are allowed. Therefore you can use a dictionary to keep track of elements in first list, along with their counts and compare it with the second list and append/update accordingly.

l1 = [1,2,3,4,5,5,6,7,8]
l2 = [4,5,5,6,7,8,9,10,11]

lookup = {}

for elem in l1:
    if elem in lookup:
        lookup[elem] += 1

    else:
        lookup[elem] = 1

for elem in l2:
    if elem in lookup and lookup[elem] > 0:
        lookup[elem] -= 1

    else:
        l1.append(elem)

print(l1)

Output:

[1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10, 11]

Answer 2

IIUC, you can try (based on assumption that "second list is the same as the first but it has been shifted to the left and more elements added to it"):

l1 = np.array([1,2,3,4,5,5,6,7,8])
l2 = np.array([4,5,5,6,7,8,9,10,11])

idx = np.searchsorted(l1, l2[0])
out = np.hstack([l1[:idx], l2])
print(out)

Prints:

[ 1  2  3  4  5  5  6  7  8  9 10 11]

Answer 3

You can check for the ending sublists of l1 and compare them with the beginning of l2. If they match, you merge them.

def merge_series(l1,l2):
    
    for i in range(len(l1)):

        #check if the end sub-list of l1 matches the beginning sublist of l2 for this index
        if l1[i:] == l2[:(len(l1)-i)]:
            #marge them if they do
            l1.extend(l2[(len(l1)-i):])
            return l1
    # there is no match, just merge lists
    l1.extend(l2)
    return l1

Answer 4

You could use the next function to identify the part of the first list that is no longer at the beginning of the second list and add the corresponding subscript to form the 3rd list:

l1 = [1,2,3,4,5,5,6,7,8]

l2 = [4,5,5,6,7,8,9,10,11]

start = l1.index(l2[0]) if l2[0] in l1 else len(l1)
keep  = next(i for i in range(start,len(l1)+1) if l1[i:] == l2[:len(l1)-i])

l3   = l1[:keep] + l2

print(l3)
[1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10, 11]

To make this a bit faster, a binary search can be used to identify a starting point. It cannot provide a precise range because of duplicates but it may reduce the time needed to get the starting position if the lists are very large:

from bisect import bisect_left

l1 = [1,2,3,4,4,5,5,6,7,8]
l2 = [4,5,5,6,7,8,9,10,11]

start = bisect_left(l1,l2[0])
keep  = next(i for i in range(start,len(l1)+1) if l1[i:] == l2[:len(l1)-i])
l3    = l1[:keep]+l2

print(l3)
[1, 2, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 11]