Нужна сортировка массива 5х2 (5 звеньев), чтобы получилась цепочка

469 просмотра
0
0 Комментариев

Нужен принцип сортировки для массива типа:

ids = [[22,33],
       [44,55],
       [33,44],
       [11,22],
       [55,66]]

чтобы в результате вышло:

res = [[11,22],
       [22,33],
       [33,44],
       [44,55],
       [55,66]]

Числа могут быть любыми главное условие чтобы вышла цепочка

11,22 ~> 22,33 ~> 33,44 ~> ...

Не обращайте внимание на первые цифры, они не важны.

вот пример списка

ids = [[203, 11], [1, 203], [5001, 1], [333, 22], [22, 5001]]

а вот как он должен выглядеть:

ids = [[333,22], [22,5001], [5001,1], [1,203], [203,11]]

образуется цепочка ids[0][1] = ids[1][0], ids[1][1]=ids[2][0] ...


Добавить комментарий

4 Answers

Python Опубликовано 16.12.2018
0

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

Так как звенья являются частью Гамильтонова пути, то каждая вершина имеет не более одного входящего и исходящего ребра и чтобы найти путь, достаточно попробовать все рёбра в качестве начального звена и вернуться когда все звенья использованы:

def hamiltonian_path(edges):
    for link in edges: # try all edges as the starting point
        left = {link[0]: link for link in edges} # left -> link
        left.pop(link[0], None) # remove the first link (cut the cycle)
        chain = []
        while link:
            chain.append(link)
            link = left.pop(link[1], None) # right -> left
        if len(chain) == len(edges): # found Hamiltonian path
            return chain
    raise ValueError('failed to find Hamiltonian path for ' + str(edges))

Это квадратичный алгоритм. Примеры:

>>> ids = [[22,33],
...        [44,55],
...        [33,44],
...        [11,22],
...        [55,66]]
>>> hamiltonian_path(ids)
[[11, 22], [22, 33], [33, 44], [44, 55], [55, 66]]
>>> ids = [[203, 11], [1, 203], [5001, 1], [333, 22], [22, 5001]]
>>> hamiltonian_path(ids)
[[333, 22], [22, 5001], [5001, 1], [1, 203], [203, 11]]

Заметив, что начальная вершина не является исходящей ни в одном из звеньев (если нет цикла), можно линейный алгоритм реализовать:

def hamiltonian_path(edges):
    chain = []
    if not edges: # empty
        return chain
 
    # edge == (inbound, outbound)
    inbound = {edge[0]: edge for edge in edges}   # inbound -> edge
    outbound = {edge[1]: edge for edge in edges}  # outbound -> edge
 
    # find the first link
    try:  # its inbound vertice is not present in any outbound vertices
        link = next(inbound[v] for v in inbound if v not in outbound)
    except StopIteration: # edges form Hamiltonian cycle (graph)
        link = inbound.pop(edges[0][0]) # use any edge
 
    # build chain
    while link:
        chain.append(link)
        link = inbound.pop(link[1], None) # outbound -> inbound
    if len(chain) != len(edges):
        raise ValueError('failed to find Hamiltonian path for %s (got %s)' % (
            edges, chain))
    return chain

Результаты для примеров те же.

Добавить комментарий
0

res = sorted(ids, key=lambda x: x[0])

Сортировка по первому элементу в паре.

Добавить комментарий
0

На самом деле, даже обычная сортировка будет работать так, как вы хотите:

res = sorted(ids)

Питон и так сравнивает списки сначала по первому элементу, и только если они равны, будет учитывать последующие элементы.

Добавить комментарий
0

ids = [[203, 11], [1, 203], [5001, 1], [333, 22], [22, 5001]]
 
res = []
 
while ids:
    if len(res) == 0:
        res.append(ids[0])
        ids.remove(ids[0])
    else:
        for i in range(len(res)):
            for c in range(len(ids)):
                if res[i][1] == ids[c][0]:
                    res.insert(res.index(i)+1,ids[c])
                    ids.remove(ids[c])
                    break
                elif res[0][0] == ids[c][1]:
                    res.insert(0,ids[c])
                    ids.remove(ids[c])
                    break
print(res)

Вот моё решение, данной задачки для сортировки списка цепочкой.

Добавить комментарий
Напишите свой ответ на данный вопрос.
Scroll Up