A= [[], [2, 3], [1], [1], [3]]
I have a list of lists. What I want to do is determine a best number (represent a choice) among the lists. --- a general algorithm to do so
The rules:
1) All the lists are ordered descendingly (left to right), so we always choose the number in the earlier sub-list (in this case [2, 3])
2) If there are multiple numbers(can't decided), we keep going down, until the number appears in the following earliest sub-list. In the case of A, both [1] does not contain 2 or 3 and as the last item [3] contains 3, we decide the best number in A is 3.
I all make more examples to be more clear.
B=[[5], [0, 8], [0, 8], [0, 8], [1]]
The best number is 5.
C=[[0, 1], [0, 3], [0], [0], [2]]
The best number is 0.
D=[[], [3, 6], [3, 5, 6], [6], [1]]
The best number is 6.
Anyone has any idea how to write the algorithm... got stuck.
Thanks.
Here is a function that works fine for all cases and return the list of all first candidates encountered if no choice can be made to separate them.
def find_best(list_of_lists):
i = 0
while len(list_of_lists[i]) == 0:
i+=1
list_containing_candidates = list_of_lists[i][:]
if len(list_containing_candidates) == 1 :
return list_containing_candidates[0]
else:
if i+1 < len(list_of_lists):
for next_list in list_of_lists[i+1:]:
for candidate in list_containing_candidates[:]:
if candidate not in next_list:
list_containing_candidates.remove(candidate)
if len(list_containing_candidates) == 0:
list_containing_candidates = list_of_lists[i][:]
elif len(list_containing_candidates) == 1:
return list_containing_candidates[0]
return list_of_lists[i] # ambigous case, entire list of candidates returned
print(find_best([[], [2, 3], [1], [1], [3]])) # 3
print(find_best([[5], [0, 8], [0, 8], [0, 8], [1]])) # 5
print(find_best([[0, 1], [0, 3], [0], [0], [2]])) # 0
print(find_best([[], [3, 6], [3, 5, 6], [6], [1]])) # 6
print(find_best([[], [3, 6], [3, 5], [6], [1]])) # 3
print(find_best([[1,3 ], [1, 3], [1,2,3], [1,3], []])) # [1,3]