Как отсортировать иерархические данные, представленные в виде плоского списка?

Question

У меня есть список Python (версия 2.7) объектов с подразумеваемой иерархией. Если одно или несколько Под-вещей сразу же следуют за Вещью, они принадлежат этой Вещи. Я хочу отсортировать Вещи по их значению, и когда Вещи перемещаются для сортировки, я хочу, чтобы их Суб-вещи перемещались вместе с ними. У всех этих объектов есть значения. Пример ввода:

Thing valueA
SubThing foo
SubThing bar
Thing valueB
Thing valueC
SubThing baz
SubThing flerp
...

У меня есть рабочий код для этого в Python 2.7, но это грубая сила и выглядит неэлегантно - около 40 строк кода. Сначала я создаю промежуточную структуру данных, которая группирует Вещи с их Под-вещами, затем сортирую по значениям Вещей, а затем сглаживаю получившуюся структуру.

У меня такое чувство, что есть элегантная одна или две (или три? ) -лайнер для этого. Это даже звучит как классическая c возможность для преобразования Шварца, но я не совершаю скачок «Pythoni c», который легко группирует SubThings с вещами - может быть, что-то с itertools.groupby ()?

Для ясности: SubThings никогда не возникают без родительской Thing. Вещи могут не иметь Суб-вещей.

Я упростил, исключив тот факт, что ряду Вещей / Суб-вещей могут предшествовать и следовать несвязанные объекты. Было бы здорово увидеть решение, которое пропускает их через несортированные, то есть в том положении, в котором они находились, но для меня это не так сложно интеллектуально.

Answer 1

Вы можете использовать накопление для распространения исходного индекса родительского объекта Thing на все элементы в его группе. Затем t ie значение родителей для каждой группы и затем используйте обычную сортировку для этих кортежей, чтобы сохранить Subthings привязанными к их исходному родительскому элементу, одновременно сортируя обоих родителей между собой и дочерними элементами их родительского элемента.

Обратите внимание, что вам также нужно будет отслеживать, какой элемент является родительским, чтобы родители продолжали появляться первыми в своей группе:

things = ["Thing valueB",
          "SubThing foo",
          "SubThing bar",
          "Thing valueC",
          "Thing valueA",
          "SubThing baz",
          "SubThing flerp"]


from itertools import accumulate

parents = accumulate((t.startswith("Thing")*i for i,t in enumerate(things)),max)
keys    = ((things[p],p,p<i,things[i]) for i,p in enumerate(parents))
sortedThings = [k[-1] for k in sorted(keys)]

for thing in sortedThings: print(thing)

Thing valueA
SubThing baz
SubThing flerp
Thing valueB
SubThing bar
SubThing foo
Thing valueC

Это все итераторы и генераторы. Нет промежуточной структуры данных (кроме внутренней во время сортировки). Все это можно было бы написать в одной (чудовищной) строке, но я старался, чтобы это было понятно.

Как вы и подозревали, это действительно преобразование Шварца, поэтому вы можете играть с кортежем, используемым в keys (шаг украшения), чтобы получить разные схемы сортировки.

Например, если вы хотите сортировать только между группами «Вещи», но не элементами «Подчинения» в каждой группе, замените (things[p],p,p<i,things[i]) на (things[p],p,i,things[i]) в генераторе keys.

Если вы хотите только отсортировать элементы «SubThing» в каждой группе, не перемещая группы, измените его на (p,p<i,things[i])

[EDIT ] Я только что заметил, что вы используете Python 2.7, который, как мне кажется, не имеет функции накопления в itertools. В таком случае вы можете написать свой собственный:

def accumulate(iterable,func):
    for i,value in enumerate(iterable):
        result = func(result,value) if i else value
        yield result

Я никогда не использовал Python 2.7, поэтому могут быть некоторые другие отличия, о которых я не знаю