Слияние пар по общему числу с ограничениями

Question

Мне нужен эффективный способ объединения списка узлов (пар целых чисел).
Объединение должно происходить только в том случае, если в паре есть одно общее число и общее число в первой или последней позиции (иначе он уже подключен).

Например:

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

другой пример:

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.

и еще один пример:

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"!

В настоящее время я использую:

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

Но для вышеуказанных ограничений это не очень хорошо работает

Answer 1

Код ниже работает следующим образом:

1. Создать новый список с размером старого списка + 1 (Максимальный размер выход может достигать).
2. Начните с первой пары в вашем списке пар с ее первым значением в конце вашего нового списка, и его второе значение в начале ваш новый список. И пометить их как посещенные с помощью словаря Python например.
3. Поддерживать два индекса вашей первой и последней позиций, указывающих на конец и начало вашего нового списка соответственно изначально.
4. Выполните итерации по остальным парам, если для пары i оба значения существуют или не существует в словаре, пропустите его. Остальное, слить то не посетил значение элемента по первому или последнему индексу (в зависимости от положение посещенного значения), и обновите свой индекс. Обратите внимание, что слияние не произойдет, если посещенное значение не будет первым или последний индекс (если он где-то посередине).
5. Возвращает конкатенацию нового списка [первый индекс в конец] с новым список [начало до последнего индекса].

Примечание: каждая операция слияния занимает O (1). Также вы можете использовать массив логических значений вместо словаря, если вы знаете диапазон значений пар.

#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]

Этот код дает правильный вывод для всех упомянутых вами тестовых случаев.