Merge pairs on common integer with restrictions

I need an efficient way to merge a list of nodes (pairs of integers).

The merge should happen only if there is one common number in the pair and the common number is on the first or the last position (otherwise its allready connected).

For example:

mylist = [[4, 3], [6, 3]]
merge_links(mylist) # should output [4, 3, 6]


another example:

mylist = [[4, 3], [6, 3], [6, 4]]
merge_links(mylist)
# should output again [4, 3, 6] because both 6 and 4 allready exist in array.


and yet another example:

mylist = [[4, 3], [6, 3], [6, 4], [6, 2], [7, 4], [4, 9]]
merge_links(mylist)
# should output [7, 4, 3, 6, 2]


# [4, 3] ✔
# [4, 3] + [6, 3] ✔ -> [4, 3, 6]
# [4, 3, 6] + [6, 3] ✘ both 6 and 3 exist in [4, 3, 6]
# [4, 3, 6] + [6, 4] ✘ both 6 and 4 exist in [4, 3, 6]
# [4, 3, 6] + [6, 2] ✔ -> [4, 3, 6, 2]
# [4, 3, 6, 2] + [7, 4] ✔ -> [7, 4, 3, 6, 2]
# [7, 4, 3, 6, 2] + [4, 9] ✘ 4 is allready connected "7-4-3"!


Currently I'm using:

def merge_links(a, b):
inter = np.intersect1d(a, b, True)
a = set(a) - set(inter)
b = set(b) - set(inter)
n = np.unique(list(a) + list(inter) + list(b))
return n


But it doesnt work well for the above restrictions

graph

1 Answer
1

The code below works as follows:

Note: every merging operation takes O(1). Also you can use an array of booleans instead of dictionary if you know the range of pairs values.

#The function takes a list of pairs as an argument
def merge_lst(lst):

#Dictionary to check if value is already in array
visited = dict()

#Length of old list
lst_len = len(lst)

#New list will have at most lst_len+1 elements
new_lst = [0]*(lst_len+1)

#Put the first pair values in last and first elements of the new list repectively and mark them as visited
new_lst[lst_len], new_lst[0] = lst[0][0], lst[0][1]
visited[lst[0][0]], visited[lst[0][1]] = True, True

#Maintain the positions of your first and last elements, which are the the last index and 0 respectively now
first_index, last_index = lst_len, 0

#Iterate on the rest of pairs
for i in range(1, lst_len):

#Check if pair[a, b] are already visited
a_exists, b_exists = lst[i][0] in visited, lst[i][1] in visited

#Skip if they both exist or don't exist
if(a_exists == b_exists):
continue

#Assume a was the common one
common, to_merge = lst[i][0], lst[i][1]

#If b exists (b is the common not a), then just swap
if(b_exists):
common, to_merge = lst[i][1], lst[i][0]

#If the common element is at the first index, the first element and index are updated
if(new_lst[first_index] == common):
first_index-=1
new_lst[first_index] = to_merge
visited[to_merge] = True

#If the common element is at the last index, the last element and index are updated
elif(new_lst[last_index] == common):
last_index+=1
new_lst[last_index] = to_merge
visited[to_merge] = True

#Else, the common element is somewhre in the middle (already connected)

#Return concatenation of new_lst[first_index to the end] with new_lst[0 to the last_index]
return new_lst[first_index:lst_len+1]+new_lst[0:last_index+1]


This code gives correct output for all of your mentioned test cases.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.