Создать порядковый номер из иерархического пути

Question

Допустим, у меня есть набор структур, подобных траектории:

A1 -> B1 -> C1
A1 -> B1 -> C2
A1 -> B2
A2
A3 -> B1
A4 -> B2 -> C3

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

Если вы представляете пути для представления чего-то вроде узлов XML, то As будут узлами корневого уровня, сначала дочерними элементами B и т. Д. Сначала я хочу отсортировать по A, затем B, затем C и т. Д. Пути имеют произвольные глубина и произвольное количество узлов на каждом уровне.

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

Редактировать: На самом деле мне было бы легко получить общее количество путей в наборе и иметь это значение доступным во время вычисления. Я собираюсь вернуться к доске с учетом этого; спасибо @ ррено.

Answer 1

Если вы хотите сохранить порядок, вам действительно нужно знать некоторые границы для коэффициента ветвления, глубины или общего количества записей, чтобы сделать это.

Доказательство от противного.Считай меня своим злым противником.Предположим, у вас есть система нумерации, которая не знает границы общего размера, я спрошу у вас номер («A»), а затем номер («B»).Тогда я возьму N = Число ('B') - Число ('A') и попрошу вас набрать номер ('A', 1), ('A', 2), ... ('A', N + 1).Теперь, когда вы облажались, вы не можете присвоить постоянное число («A», N + 1).Вы исчерпали пространство, если выполнили лучшую возможную работу, указав порядковый номер каждого из детей предшествующего А.Если вы не сделали лучшую работу, вы уже потеряли.

Answer 2

Представление у вас там есть частичный заказ.То есть не все элементы сопоставимы.Вы ищете линеаризацию частичного заказа (то есть общий заказ, который содержит этот частичный заказ).Например, предположим, что у нас есть A1 -> B1 A1 -> B2. Из этой информации я знаю, что A1> B1 и A1> B2. Но я ничего не знаю о B1 и B2.Таким образом, есть две возможности.A1 -> B1 -> B2 или A1 -> B2 -> B1.Эта проблема также называется топологической сортировкой, и она выполняется в O (n + m) n: количество узлов, m: ребра.

Возьмите эти ссылки: http://en.wikipedia.org/wiki/Linear_extension http://en.wikipedia.org/wiki/Topological_sorting