Цепь последнего элемента списка с равным первым элементом другого списка

Question

это уже заняло половину дня ... Я пытаюсь связать последний и первый элементы вложенного списка. Я проиллюстрирую это на простом примере:

input = [(8, 2), (8, 5), (2, 12), (12, 13), (5, 6), (6, 7), (13, 14), 
     (14, 3), (7, 4), (3, 4)] 
result = [(8, 2), (2, 12), (12, 13), (13, 14), (14, 3), (3, 4), (4, 7), 
      (7, 6), (6, 5), (5, 8)] 

Я попытался следующий код:

def ChainNew(L): 
    R = copy.deepcopy(L) 
    for pair in R: 
     pair.reverse() 
    stop = len(L) 
    chain = [L.pop(0)] 
    L = sorted(L) 
    R = sorted(R) 
    while len(chain) < stop: 
     for i, j in zip(L, R): 
      if i[0] == chain[len(chain)-1][1]: 
       chain.append((i)) 
       L.remove(i) 
       R.remove(i[::-1]) 
       break 
      if j[0] == chain[len(chain)-1][1]: 
       chain.append((j)) 
       L.remove(j[::-1]) 
       R.remove(j) 
       break 
    return chain 

, но это не только неэффективна, но и глючит: это не похоже, возвращают все элементы исходного списка. Например:

L = [[20, 56], [23, 24], [23, 12], [22, 21], [26, 48], [26, 24], 
     [55, 48], [55, 39], [56, 40], [19, 6], [19, 12], [6, 15], 
     [40, 39], [21, 57], [14, 15], [14, 16], [57, 50], [45, 9], 
     [45, 53], [18, 42], [18, 9], [38, 53], [38, 44], [50, 42], 
     [16, 17], [17, 35], [36, 37], [36, 35], [37, 44]] 

return = [[20, 56], [56, 40], [40, 39], [39, 55], [55, 48], [48, 26], 
      [26, 24], [24, 23], [23, 12], [12, 19], [19, 6], [6, 15], 
      [15, 14], [14, 16], [16, 17], [17, 35], [35, 36], [36, 37], 
      [37, 44], [44, 38], [38, 53], [53, 45], [45, 9], [9, 18], 
      [18, 42], [42, 50], [50, 57]] 

Там должна быть более простой способ сделать это ...

EDIT: жаль! Я забыл упомянуть, что целые числа внутри каждого списка (пары) могут быть заменены. Например, (7, 4) - (4, 7).

В основном то, что у меня здесь, в каждой паре чисел, является индексом края полилинии. Все ребра вместе образуют полилинию. Поэтому путем «цепочки» каждой пары чисел я могу отсортировать индексы вершин полилинии.

EDIT СНОВА: Правильный результат списка L будет:

return = [[22, 21], [21, 57], [57, 50], [50, 42], [42, 18], [18, 9], 
      [9, 45], [45, 53], [53, 38], [38, 44], [44, 37], [37, 36], 
      [36, 35], [35, 17], [17, 16], [16, 14], [14, 15], [15, 6], 
      [6, 19], [19, 12], [12, 23], [23, 24], [24, 26], [26, 48], 
      [48, 55], [55, 39], [39, 40], [40, 56], [56, 20]] 

Спасибо!

Answer 1

Как насчет:

def path(a, b): 
    if not b: 
     return a 
    for n, (p, q) in enumerate(b): 
     if p == a[-1][1]: 
      return path(a + [(p, q)], b[:n] + b[n+1:]) 
     if q == a[-1][1]: 
      return path(a + [(q, p)], b[:n] + b[n+1:]) 
    raise ValueError("no path", a, b) 

L = [(8, 2), (8, 5), (2, 12), (12, 13), (5, 6), (6, 7), (13, 14), (14, 3), (7, 4), (3, 4)] 
print path([L[0]], L[1:]) 
#[(8, 2), (2, 12), (12, 13), (13, 14), (14, 3), (3, 4), (4, 7), (7, 6), (6, 5), (5, 8)] 

Answer 2

Вот решение, которое находит все возможные цепочки:

def find_chains(points): 
    """For a list of points, take the first point and finds all chains that 
    could be made from the following points. 

    Returns a list of lists of tuples. Each sublist is a possible chain. 
    """ 

    def find_solutions(start, choices): 
     """For a starting point and a list of choices, return all choices that 
     might succeed that point. 

     Returns a list of tuples. These tuples contain the next choice, and all 
     of the remaining points should that choice be used. 
     """ 

     ret = [] 
     for i, possible_choice in enumerate(choices): 
      # Determine whether or not the choice is appropriate. 
      added_choice = None 
      if start[1] == possible_choice[0]: 
       added_choice = possible_choice 
      elif start[1] == possible_choice[-1]: 
       added_choice = possible_choice[::-1] 

      # If it is, add a tuple of that choice and all other choices to the 
      # return list. 
      if added_choice: 
       ret.append((
        added_choice, 
        [ 
         k 
         for j, k 
         in enumerate(choices) 
         if i != j 
        ] 
       )) 

     return ret 

    solutions = [] 
    start = points[0] 
    other_points = points[1:] 
    if not other_points: 
     # If there aren't any remaining points, then the only possible path is 
     # that of just the first point. 
     return [[start]] 

    # Find all chains through `other_points` and add them to our solutions. 
    for next_point, remaining_points in find_solutions(start, other_points): 
     for subchain in find_chains([next_point] + remaining_points): 
      solutions.append([start] + subchain) 
    return solutions 

Разница между этим раствором и другими, более короткими решениями является то, что другие просто взять первый возможный пункт и найти подцепину оттуда, тогда как это занимает все возможное. Пример:

test = [(1, 2), (2, 3), (2, 4), (3, 4)] 
print(find_chains(test)) 
# Finds two possible solutions: 
# [[(1, 2), (2, 3), (3, 4), (4, 2)], 
# [(1, 2), (2, 4), (4, 3), (3, 2)]] 

test = [(8, 2), (8, 5), (2, 12), (12, 13), (5, 6), (6, 7), (13, 14), 
     (14, 3), (7, 4), (3, 4)] 
print(find_chains(test)) 
# Finds the only solution: 
# [[(8, 2), (2, 12), (12, 13), (13, 14), (14, 3), (3, 4), (4, 7), (7, 6), (6, 5), (5, 8)]] 

test = [(1, 2), (3, 4)] 
print(find_chains(test)) 
# There weren't any solutions: 
# []