Sắp xếp danh sách các bộ theo thứ tự liên tiếp

Question

Tôi muốn sắp xếp danh sách các bộ dữ liệu theo thứ tự liên tiếp thứ tự liên tiếp, do đó phần tử đầu tiên của mỗi bộ tương đương với phần tử cuối cùng của phần trước.

Ví dụ:

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

tôi đã phát triển một tìm kiếm như thế này:

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)  

Có cách nào pythonic để đạt được trật tự như vậy? Và một cách để làm điều đó "tại chỗ" (chỉ với một danh sách)?

Trong vấn đề của tôi, đầu vào có thể được sắp xếp lại theo cách vòng tròn bằng cách sử dụng tất cả các bộ dữ liệu, do đó, điều quan trọng không phải là yếu tố đầu tiên được chọn.

Answer 1

Giả sử các tuple của bạn trong list sẽ tròn, bạn có thể sử dụng dict để đạt được nó trong vòng phức tạp của O (n) như:

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

giá trị cuối cùng giữ bởi new_list sẽ là:

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

Answer 2

nếu bạn không sợ để lãng phí một số bộ nhớ bạn có thể tạo ra một từ điển start_dict chứa số nguyên bắt đầu như phím và các bộ như các giá trị và làm điều gì đó như thế này:

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) 

nếu hai tuples bắt đầu với cùng số bạn sẽ mất một trong số họ ... nếu không phải tất cả các số bắt đầu được sử dụng vòng lặp sẽ không chấm dứt.

nhưng có thể đây là thứ để xây dựng.

Answer 3

Thực tế, có rất nhiều câu hỏi về những gì bạn định làm đầu ra và nếu danh sách đầu vào có cấu trúc không hợp lệ để thực hiện những gì bạn cần.

Giả sử bạn có đầu vào của các cặp trong đó mỗi số chỉ được bao gồm hai lần. Vì vậy, chúng ta có thể xem xét đầu vào như một đồ thị trong đó các số là các nút và mỗi cặp là một cạnh. Và như xa như tôi hiểu câu hỏi của bạn, bạn cho rằng biểu đồ này là cyclic và trông như thế này:

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

này cho bạn thấy rằng bạn có thể giảm danh sách để lưu trữ các đồ thị để [10, 7, 13, 4, 9].Và đây là kịch bản mà sắp xếp danh sách đầu vào:

# 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

đầu tiên tôi sẽ tạo ra một từ điển có dạng

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

Sau đó làm việc từ đó:

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

Bạn có thể thử này :

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:

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

Answer 6

đây là một (ít hiệu quả hơn t so với phiên bản từ điển) biến nơi danh sách được thay đổi tại chỗ:

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 

đây là một phiên bản hiệu quả hơn trong những ý tưởng tương tự:

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) 

danh sách được thay đổi tại chỗ; từ điển chỉ chứa các giá trị bắt đầu của các bộ dữ liệu và chỉ mục của chúng trong danh sách.

Answer 7

Dưới đây là một giải pháp mạnh mẽ sử dụng sorted chức năng và một chức năng tùy chỉnh quan trọng:

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) 

Danh sách ban đầu không được sửa đổi. Lưu ý rằng sorted được gọi là 3 lần cho danh sách chiều dài input của bạn 5. Trong mỗi cuộc gọi, một bộ tuple bổ sung được đặt chính xác. Tuple đầu tiên giữ nguyên vị trí ban đầu.

Tôi đã sử dụng từ khóa nonlocal, có nghĩa là mã này chỉ dành cho Python 3 (một người có thể sử dụng global để thay thế mã Python 2 hợp pháp).

Answer 8

tôi hai xu:

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 

Output:

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

Để có được một thuật toán O(n) người ta cần phải chắc chắn rằng chúng ta không làm một đôi vòng lặp qua mảng. Một cách để làm điều này là bằng cách giữ các giá trị đã xử lý trong một số loại bảng tra cứu (một dict sẽ là một lựa chọn tốt).

Ví dụ như một cái gì đó như thế này (Tôi hy vọng các ý kiến ​​nội tuyến giải thích các chức năng tốt).Điều này sửa đổi danh sách tại chỗ và nên tránh vòng lặp không cần thiết (thậm chí tiềm ẩn) trong danh sách:

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