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

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

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

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

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

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

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

15
задан Community 23 May 2017 в 12:25
поделиться

4 ответа

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

Краткий ответ: вы хотите, чтобы 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}

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

18
ответ дан 1 December 2019 в 02:01
поделиться

Does GatherBy do what you want?

Flatten[GatherBy[{301, 201, 502, 501, 101}, Mod[#, 10] &]]
6
ответ дан 1 December 2019 в 02:01
поделиться

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

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

Считая связи, можно получить стабильную сортировку:

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

yields

{300, 301, 201, 501, 101, 502, 19}
4
ответ дан 1 December 2019 в 02:01
поделиться

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

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

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

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

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

3
ответ дан 1 December 2019 в 02:01
поделиться
Другие вопросы по тегам:

Похожие вопросы: