Стабильная сортировка, т.е. минимально разрушительная сортировка

Question

Предположим, у меня есть список вещей (цифры, чтобы все было просто), и у меня есть функция, которую я хочу использовать для сортировки, используя SortBy. Например, следующий сортирует список номеров по последней цифре:

SortBy[{301, 201}, Mod[#,10]&]

И обратите внимание, что два (то есть все) этих числа имеют одну и ту же последнюю цифру. Так что не имеет значения, в каком порядке мы их возвращаем. В этом случае Mathematica возвращает их в обратном порядке. Как я могу гарантировать, что все связи разорваны в пользу того, как предметы были заказаны в первоначальном списке?

(Я знаю, что это довольно тривиально, но я чувствую, что это время от времени возникает, поэтому я подумал, что было бы удобно разместить его в StackOverflow. Я опубликую все, что мне придет в качестве ответа, если никто не победит я к этому.)

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

PS: Спасибо Николасу за указание, что это называется стабильной сортировкой. Это было на кончике моего языка! Вот еще одна ссылка: http://planetmath.org/encyclopedia/StableSortingAlgorithm.html

Answer 1

После расспросов мне дали удовлетворительное объяснение:

Краткий ответ: Вы хотите, чтобы SortBy[list, {f}] получил стабильную сортировку.

Длинный ответ:

SortBy[list, f] сортирует список в порядке, определенном путем применения f к каждому элементу списка, разрыв связи с использованием канонического порядка, описанного в разделе Сортировка . (Это вторая документированная заметка «Дополнительная информация» в документации для SortBy .)

SortBy[list, {f, g}] разрывает связи, используя порядок, определенный путем применения g к каждому элементу.

Обратите внимание, что SortBy[list, f] совпадает с SortBy[list, {f, Identity}].

SortBy[list, {f}] не прерывает связь (и дает стабильную сортировку), что вам нужно:

In[13]:= SortBy[{19, 301, 201, 502, 501, 101, 300}, {Mod[#, 10] &}]

Out[13]= {300, 301, 201, 501, 101, 502, 19}

Наконец, решение Сакры SortBy[list, {f, tie++ &}] фактически эквивалентно SortBy[list, {f}].

Answer 2

GatherBy делает то, что вы хотите?

Flatten[GatherBy[{301, 201, 502, 501, 101}, Mod[#, 10] &]]

Answer 3

Существует вариант SortBy, который разрывает связи, используя дополнительные функции заказа:

SortBy[list,{f1, f2, ...}]

Подсчитав количество связей, вы получите стабильную сортировку:

Module[{tie = 0}, 
 SortBy[{19, 301, 201, 502, 501, 101, 300}, {Mod[#, 10] &, (tie++) &}]]

1010 * выходы *

{300, 301, 201, 501, 101, 502, 19}

Answer 4

Кажется, это работает:

stableSortBy[list_, f_] := 
  SortBy[MapIndexed[List, list], {f@First[#], Last[#]}&][[All,1]]

Но теперь я вижу, rosettacode дает гораздо более приятный способ сделать это:

stableSortBy[list_, f_] := list[[Ordering[f /@ list]]]

Итак, упорядочениеключ!Кажется, в документации Mathematica нет упоминания об этом иногда важном различии Sort и Ordering.