Сортировка списка кортежей в последовательном порядке

Ответ 1

Предполагая, что ваши кортежи в list будут круговыми, вы можете использовать dict для достижения этого в пределах сложности O (n) как:

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))

Завершение окончательного значения new_list будет:

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

Ответ 2

если вы не боитесь потерять память, вы могли бы создать словарь start_dict, содержащий начальные целые числа в качестве ключей и кортежей в качестве значений, и сделать что-то вроде этого:

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)

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

но, возможно, это то, на чем можно опираться.

Ответ 3

На самом деле есть много вопросов о том, что вы собираетесь использовать в качестве вывода, и что, если список ввода имеет недопустимую структуру, чтобы делать то, что вам нужно.

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

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

Это показывает, что вы можете уменьшить список, чтобы сохранить график до [10, 7, 13, 4, 9]. И вот script сортирует список ввода:

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

Ответ 4

Сначала я создаю словарь формы

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

Тогда работа оттуда:

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

Ответ 5

Вы можете попробовать следующее:

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

Вывод:

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

Ответ 6

это вариант (менее эффективный, чем версия словаря), где список изменяется на месте:

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

вот более эффективная версия той же идеи:

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)

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

Ответ 7

Вот надежное решение, использующее функцию sorted и функцию пользовательского ключа:

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)

Исходный список не изменяется. Обратите внимание, что sorted вызывается 3 раза для вашего списка input длины 5. В каждом вызове корректно помещается один дополнительный кортеж. Первый кортеж сохраняет исходное положение.

Я использовал ключевое слово nonlocal, что означает, что этот код предназначен только для Python 3 (вместо этого можно использовать global, чтобы сделать его законным кодом Python 2).

Ответ 8

Мои два цента:

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

Выход

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

Ответ 9

Чтобы получить алгоритм O(n), нужно убедиться, что он не выполняет двойной цикл над массивом. Один из способов сделать это - сохранить уже обработанные значения в какой-то таблице lookup (a dict будет хорошим выбором).

Например, что-то вроде этого (я надеюсь, что встроенные комментарии хорошо объясняют функциональность). Это изменяет список на месте и избегает ненужных (даже неявных) циклов по списку:

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