Ordinamento stabile, ovvero ordinamento minimamente dirompente

Question

Supponiamo di avere una lista di cose (numeri, per mantenere le cose semplici qui) e ho una funzione che voglio usare per ordinarle, usando SortBy. Ad esempio, il seguente ordina un elenco di numeri da ultima cifra:

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

e notare come due (cioè tutti) questi numeri hanno lo stesso ultima cifra. Quindi non importa quale ordine li restituiamo. In questo caso Mathematica li restituisce nell'ordine opposto. Come posso garantire che tutte le cravatte siano rotte a favore di come gli articoli sono stati ordinati nell'elenco originale?

(So che è un po 'banale, ma mi sembra che questo di tanto in tanto venga fuori così ho pensato che sarebbe stato utile per ottenerlo su StackOverflow.Però postare qualsiasi cosa mi venga in mente come risposta se nessuno mi batte ad esso)

tentativi di rendere questo più ricercabile:. liste con il minimo disturbo, specie con minor numero di swap, personalizzati tie-rottura, smistamento con costosi scambio, stabile ordinamento.

PS: grazie a Nicholas per indicare che questo è chiamato ordinamento stabile. Era sulla punta della mia lingua! Ecco un altro link: http://planetmath.org/encyclopedia/StableSortingAlgorithm.html

Answer 1

Dopo aver chiesto in giro, mi è stata data una spiegazione soddisfacente:

Risposta breve: Volete SortBy[list, {f}] ottenere una sorta stabile.

Risposta lunga:

SortBy[list, f] lista sorta nell'ordine determinato applicando f ad ogni elemento della lista, rompendo i legami con l'ordinamento canonico spiegato sotto Sort. (Questa è la seconda nota "Ulteriori informazioni" documentata nello documentation for SortBy.)

SortBy[list, {f, g}] interrompe i legami utilizzando l'ordine determinato applicando g a ciascun elemento.

Si noti che SortBy[list, f] corrisponde a SortBy[list, {f, Identity}].

SortBy[list, {f}] fa nessuna rottura cravatta (e dà una sorta stabile), che è ciò che si desidera:

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

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

Infine, la soluzione di Sakra SortBy[list, {f, tie++ &}] è effettivamente equivalente a SortBy[list, {f}].

Answer 2

Questo sembra funzionare:

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

ma ora vedo rosettacode offre un modo molto più piacevole per farlo:

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

Così Ordinare è la chiave! Sembra che la documentazione di Mathematica non menzioni questa differenza a volte importante Ordina e ordina.

Answer 3

Fa Gather Fai quello che vuoi?

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

Answer 4

C'è una variante di SortBy che rompe i legami utilizzando le funzioni di ordinamento aggiuntive:

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

Contando legami si può quindi ottenere un ordinamento stabile:

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

rendimenti

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