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)