Sortuj listę krotek w następującej kolejności

Question

Chcę posortować listę krotek w kolejno następujących po sobie , więc pierwszy element każdej krotki jest równy ostatniemu elementowi poprzedniej.

Na przykład:

input = [(10, 7), (4, 9), (13, 4), (7, 13), (9, 10)] 
output = [(10, 7), (7, 13), (13, 4), (4, 9), (9, 10)] 

I opracowali szukanie takiego:

output=[] 
given = [(10, 7), (4, 9), (13, 4), (7, 13), (9, 10)] 
t = given[0][0] 
for i in range(len(given)): 
     # search tuples starting with element t 
     output += [e for e in given if e[0] == t] 
     t = output[-1][-1] # Get the next element to search 

print(output)  

Czy istnieje pythonic sposobem osiągnięcia takiego zamówienia? A sposób to zrobić "w miejscu" (tylko z listą)?

W moim problemie, dane wejściowe mogą zostać zmienione w sposób okrągły za pomocą wszystkich krotek, więc nie jest ważne, aby pierwszy element został wybrany.

Answer 1

Zakładając, że krotki w list będzie okrągła, można użyć dict osiągnąć go w złożoności O (n) jak:

input = [(10, 7), (4, 9), (13, 4), (7, 13), (9, 10)] 
input_dict = dict(input) # Convert list of `tuples` to dict 

elem = input[0][0] # start point in the new list 

new_list = [] # List of tuples for holding the values in required order 

for _ in range(len(input)): 
    new_list.append((elem, input_dict[elem])) 
    elem = input_dict[elem] 
    if elem not in input_dict: 
     # Raise exception in case list of tuples is not circular 
     raise Exception('key {} not found in dict'.format(elem)) 

końcowa wartość zawieszone przez new_list będzie:

>>> new_list 
[(10, 7), (7, 13), (13, 4), (4, 9), (9, 10)] 

Answer 2

jeśli nie boją się tracić trochę pamięci można utworzyć słownik start_dict zawierający liczby całkowite rozpocząć się klawiszami i krotki jako wartości i zrobić coś takiego:

tpl = [(10, 7), (4, 9), (13, 4), (7, 13), (9, 10)] 
start_dict = {item[0]: item for item in tpl} 

start = tpl[0][0] 
res = [] 
while start_dict: 
    item = start_dict[start] 
    del start_dict[start] 
    res.append(item) 
    start = item[-1] 

print(res) 

jeśli dwie krotki zacząć z tym samym numer stracisz jedną z nich ... jeśli nie wszystkie numery początkowe zostaną użyte, pętla się nie zakończy.

, ale może jest to coś, na czym można się oprzeć.

Answer 3

Właściwie jest wiele pytań na temat tego, co zamierzasz mieć jako wynik, a co jeśli lista wejściowa ma nieprawidłową strukturę, aby zrobić to, czego potrzebujesz.

Zakładając, że masz dane wejściowe z parami, w których każdy numer jest zawarty tylko dwa razy. Możemy więc rozważyć takie dane wejściowe jako wykres, w którym liczby są węzłami, a każda para jest krawędzią. I o ile rozumiem Twoje pytanie myślisz, że ten wykres jest cykliczny i wygląda następująco:

10 - 7 - 13 - 4 - 9 - 10 (same 10 as at the beginning) 

To pokazuje, że można zmniejszyć listę zapisać wykres do [10, 7, 13, 4, 9].A oto skrypt, który sortuje listę wejściowy:

# input 
input = [(10, 7), (4, 9), (13, 4), (7, 13), (9, 10)] 

# sorting and archiving 
first = input[0][0] 
last = input[0][1] 
output_in_place = [first, last] 

while last != first: 
    for item in input: 
     if item[0] == last: 
      last = item[1] 
      if last != first: 
       output_in_place.append(last) 

print(output_in_place) 

# output 
output = [] 
for i in range(len(output_in_place) - 1): 
    output.append((output_in_place[i], output_in_place[i+1])) 
output.append((output_in_place[-1], output_in_place[0])) 

print(output) 

Answer 4

bym najpierw utworzyć słownika postaci

{first_value: [list of tuples with that first value], ...} 

Następnie pracować stamtąd:

from collections import defaultdict 

chosen_tuples = input[:1] # Start from the first 

first_values = defaultdict() 
for tup in input[1:]: 
    first_values[tup[0]].append(tup) 

while first_values: # Loop will end when all lists are removed 
    value = chosen_tuples[-1][1] # Second item of last tuple 
    tuples_with_that_value = first_values[value] 
    chosen_tuples.append(tuples_with_that_value.pop()) 
    if not chosen_with_that_value: 
     del first_values[value] # List empty, remove it 

Answer 5

Można spróbować :

input = [(10, 7), (4, 9), (13, 4), (7, 13), (9, 10)] 

output = [input[0]] # output contains the first element of input 
temp = input[1:] # temp contains the rest of elements in input 

while temp: 
    item = [i for i in temp if i[0] == output[-1][1]].pop() # We compare each element with output[-1] 
    output.append(item) # We add the right item to output 
    temp.remove(item) # We remove each handled element from temp 

wyjściowa:

>>> output 
[(10, 7), (7, 13), (13, 4), (4, 9), (9, 10)] 

Answer 6

to jest (mniejszej wydajności t niż wersja słownika) wariantu, w którym lista jest zmieniana na miejscu:

tpl = [(10, 7), (4, 9), (13, 4), (7, 13), (9, 10)] 

for i in range(1, len(tpl)-1): # iterate over the indices of the list 
    item = tpl[i] 
    for j, next_item in enumerate(tpl[i+1:]): # find the next item 
               # in the remaining list 
     if next_item[0] == item[1]: 
      next_index = i + j 
      break 
    tpl[i], tpl[next_index] = tpl[next_index], tpl[i] # now swap the items 

tutaj jest bardziej wydajna wersja tej samej idei:

tpl = [(10, 7), (4, 9), (13, 4), (7, 13), (9, 10)] 
start_index = {item[0]: i for i, item in enumerate(tpl)} 

item = tpl[0] 
next_index = start_index[item[-1]] 
for i in range(1, len(tpl)-1): 
    tpl[i], tpl[next_index] = tpl[next_index], tpl[i] 
    # need to update the start indices: 
    start_index[tpl[next_index][0]] = next_index 
    start_index[tpl[i][0]] = i 
    next_index = start_index[tpl[i][-1]] 
print(tpl) 

lista jest zmieniana na miejscu; słownik zawiera tylko wartości początkowe krotek i ich indeks na liście.

Answer 7

Oto niezawodne rozwiązanie przy użyciu funkcji sorted i niestandardową funkcję klucza:

input = [(10, 7), (4, 9), (13, 4), (7, 13), (9, 10)] 

def consec_sort(lst): 
    def key(x): 
     nonlocal index 
     if index <= lower_index: 
      index += 1 
      return -1 
     return abs(x[0] - lst[index - 1][1]) 
    for lower_index in range(len(lst) - 2): 
     index = 0 
     lst = sorted(lst, key=key) 
    return lst 

output = consec_sort(input) 
print(output) 

Oryginalny lista nie jest modyfikowany. Zauważ, że sorted jest wywoływana 3 razy dla twojej listy input o długości 5. W każdym wywołaniu jedna dodatkowa krotka jest umieszczana poprawnie. Pierwsza krotka zachowuje oryginalną pozycję.

Użyłem słowa kluczowego nonlocal, co oznacza, że ​​ten kod dotyczy tylko Pythona 3 (zamiast tego można użyć global, aby legalny kod Python 2).

Answer 8

Moje dwa centy:

def match_tuples(input): 
    # making a copy to not mess up with the original one 
    tuples = input[:]   # [(10,7), (4,9), (13, 4), (7, 13), (9, 10)] 
    last_elem = tuples.pop(0) # (10,7) 

    # { "first tuple's element": "index in list"} 
    indexes = {tup[0]: i for i, tup in enumerate(tuples)} # {9: 3, 4: 0, 13: 1, 7: 2} 

    yield last_elem # yields de firts element 

    for i in range(len(tuples)): 
     # get where in the list is the tuple which first element match the last element in the last tuple 
     list_index = indexes.get(last_elem[1]) 
     last_elem = tuples[list_index] # just get that tuple 
     yield last_elem 

wyjścia:

input = [(10,7), (4,9), (13, 4), (7, 13), (9, 10)] 
print(list(match_tuples(input))) 
# output: [(10, 7), (7, 13), (13, 4), (4, 9), (9, 10)] 

Answer 9

Aby uzyskać O(n) algorytm jeden musi mieć pewność, że nie robi podwójną pętlę nad tablicą. Jednym ze sposobów, aby to zrobić, jest zachowanie już przetworzonych wartości w jakimś rodzaju tabeli odnośników (dobrym wyborem byłaby dict).

Na przykład coś takiego (mam nadzieję, że komentarze śródtekstowe dobrze wyjaśniają funkcjonalność).Modyfikuje to listę w miejscu i powinno unikać niepotrzebnego (nawet niejawnego) zapętlenia na liście:

inp = [(10, 7), (4, 9), (13, 4), (7, 13), (9, 10)] 

# A dictionary containing processed elements, first element is 
# the key and the value represents the tuple. This is used to 
# avoid the double loop 
seen = {} 

# The second value of the first tuple. This must match the first 
# item of the next tuple 
current = inp[0][1] 

# Iteration to insert the next element 
for insert_idx in range(1, len(inp)): 
    # print('insert', insert_idx, seen) 
    # If the next value was already found no need to search, just 
    # pop it from the seen dictionary and continue with the next loop 
    if current in seen: 
     item = seen.pop(current) 
     inp[insert_idx] = item 
     current = item[1] 
     continue 

    # Search the list until the next value is found saving all 
    # other items in the dictionary so we avoid to do unnecessary iterations 
    # over the list. 
    for search_idx in range(insert_idx, len(inp)): 
     # print('search', search_idx, inp[search_idx]) 
     item = inp[search_idx] 
     first, second = item 
     if first == current: 
      # Found the next tuple, break out of the inner loop! 
      inp[insert_idx] = item 
      current = second 
      break 
     else: 
      seen[first] = item