Home > Back-end >  Find missing sequences in list that cycles
Find missing sequences in list that cycles

Time:10-22

Given 2 lists:

target = [0, 1, 2, 3, 4, 5, 6, 7]
given = [1, 2, 5, 6]

The missing numbers is [[0], [3,4], [7]]. However, both list circulates, which means the end of the list is linked to the first, so they actually look like this:

target = [0,1,2,3,4,5,6,7,0,1,2,3,4,5,......]
given = [1,2, 5,6, 1,2, 5,6,......] # I put a space to better tell where numbers missing

That way, the desired output of missing numbers should actually be [[7,0], [3,4]] since 7 and 0 is consecutive.

How do I make up the function that does the job?

CodePudding user response:

First you can construct a list of missing patches using itertools.groupby and then glue the left-most and right-most sublists if necessary:

import itertools

def missing(target, given):
    output = [list(g) for k, g in itertools.groupby(target, key=lambda x: x in given) if not k]
    if output and output[0][0] == target[0] and output[-1][-1] == target[-1]:
        output[-1]  = output.pop(0)
    return output

print(missing([0, 1, 2, 3, 4, 5, 6, 7], [1, 2, 5, 6])) # [[3, 4], [7, 0]]
print(missing([0, 1, 2, 3, 4, 5, 6, 7, 8], [1, 2, 5, 6, 8])) # [[0], [3, 4], [7]]

Update: If you don't want to import itertools module, then replace the line output = [list(g) ...] with the following:

    output, temp = [], [] # an empty "temporary bucket"
    for x in target:
        if x in given:
            if temp: # if temp is nonempty
                output.append(temp) # put the bucket into output
                temp = [] # a new empty bucket
        else: # if x is "missing"
            temp.append(x) # append x into the bucket
    else: # this is called when for loop is over (or target is empty)
        if temp: # if the last temporary bucket is nonempty
            output.append(temp)
  • Related