Сортировка Python списка чисел, не зная их значений, но только их отношения между собой - PullRequest
Новая
       9

Сортировка Python списка чисел, не зная их значений, но только их отношения между собой

1 голос
/ 23 марта 2020

У меня есть список чисел, которые я не могу знать их реальные значения. Допустим, list = [a,b,c,d]. Но у меня есть информация о том, как они связаны друг с другом: 

a > b
b > d
d > c

Поэтому я могу сделать вывод, что список, отсортированный в порядке убывания: [ a, b, d, c].

Еще один более сложный пример 

relationships =
 - g > b
 - d > c > a
 - d > g
 - f > e > a
 - f > e > d

В этом случае у нас есть несколько возможных ответов 

            Result: 
  [ [f, e, d, c, a, g, b],
    [f, e, d, g, c, a, b],
    [f, e, d, g, c, b, a],
  ... ]

, просто чтобы назвать несколько

Я хочу, чтобы функция возвращала мне именно это: список всех возможных ответов. Отношения - это список списков, где каждый список представляет отношения сортировки в порядке убывания. Например relationships = [[a,b],[b,c]] говорит мне, что "a> b" и "b> c". Внутренние списки внутри отношений не обязательно должны быть одинакового размера. В случае неверного / невозможного ввода алгоритм должен выдать ошибку. Например:

relationships = [[a,b],[b,c],[c,a] - это невозможный случай

Какой лучший подход для этого также эффективен? Я думал об использовании теории графов, где графы не могут быть ациклически c. Например, A -> B означает, что узел A переходит в B, что означает A> B, поэтому B -> A не может существовать. Как-то похоже на двоичное дерево, но в этом случае вместо того, чтобы разрешить 2 дочерних узла на узел, мы можем разрешить только 1.

Это хорошая идея, чтобы начать с этого, или у кого-то есть идеи о том, как подойти к этому

Ответы [ 2 ]

2 голосов
/ 23 марта 2020

Вам нужно 3 идеи, чтобы понять это.

Во-первых, это топологическая сортировка по алгоритму Кана. См. https://en.wikipedia.org/wiki/Topological_sorting#Kahn 's_algorithm для описания. Я прошёл весь путь, чтобы сгенерировать топологическую сортировку по этому алгоритму и yield каждый из них.

Второй - это стековое программирование. Думай дальше, или РПН. Идея в том, что у меня есть стек действий. На каждом шаге я беру верхнее действие из списка todo и делаю это. Если я добавляю элементы в список todo, то это похоже на рекурсивные вызовы. В моем случае это действия choose (попробуйте все варианты, которые имеют смысл), add (добавление элемента в отсортированный список и ведение учета), remove (удаление элемента из отсортированного списка и ведение учета) и try (запланируйте действия добавить / выбрать / удалить - но расположить в обратном порядке, потому что стек).

Третий - генераторы. Я просто yield несколько раз, а затем продолжаю с того места, где я был. Это можно зациклить, превратить в список и т. Д. c.

Вот код. 

def topological_sorts (descending_chains):
    arrive_to = {}
    outstanding_arrivals = {}
    for chain in descending_chains:
        for x in chain:
            if x not in arrive_to:
                arrive_to[x] = set([])
                outstanding_arrivals[x] = 0
        for i in range(1, len(chain)):
            arrive_to[chain[i-1]].add(chain[i])

    for item in arrive_to:
        for x in arrive_to[item]:
            outstanding_arrivals[x] += 1

    todo = [['choose', None]]
    sorted_items = []
    chosen = set([])
    items = [x for x in arrive_to]
    while len(todo):
        action, item = todo.pop()
        if action == 'choose':
            choices = []
            for x in outstanding_arrivals:
                if x not in chosen and 0 == outstanding_arrivals[x]:
                    choices.append(x)
            if 0 == len(choices):
                if len(sorted_items) == len(items):
                    yield sorted_items
                else:
                    print((choices, outstanding_arrivals, sorted_items))
                    break
            else:
                for item in choices:
                    todo.append(['try', item])
        elif action == 'try':
            chosen.add(item)
            sorted_items.append(item)
            todo.append(['remove', item])
            todo.append(['choose', None])
            todo.append(['add', item])
        elif action == 'add':
            chosen.add(item)
            for x in arrive_to[item]:
                outstanding_arrivals[x] -= 1
        elif action == 'remove':
            chosen.remove(item)
            sorted_items.pop()
            for x in arrive_to[item]:
                outstanding_arrivals[x] += 1
        else:
            yield ('todo:', action, item)

и вот как использовать его для второго примера. 

for sort in topological_sorts([
        ['g', 'b'],
        ['d', 'c', 'a'],
        ['d', 'g'],
        ['f', 'e', 'a'],
        ['f', 'e', 'd']]):
    print(sort)
1 голос
/ 24 марта 2020

Я написал Python код для топологической сортировки на сайте. Код Rosetta здесь .

Входные данные представляют собой узлы, которые определяют отображение множества узлов, от которых оно зависит, (в вашем случае узлы они "больше чем"). используйте следующее для представления ваших примерных зависимостей: 

a,b,c,d,e,f,g = 'abcdefg'  # For ease of use
data = {c:a, d:'cag', e:'ad', f:'ead', g:b}  # <node>:<is_greater_than>
dat = {key: set(val) for key, val in data.items()}
print ('\n'.join( toposort2(dat) ))

Правильный вывод следующий: узлы в одной и той же строке могут появляться в любом порядке перед узлами из других строк над ней: 

a b
c g
d
e
f

Примечание ваше решение, которое вы даете своему примеру, неверно, так как вы не можете иметь f, e, d, за которым сразу следует b ; оно должно быть на c или g (в любом порядке); затем a или b (в любом порядке).

...