tri stable, à savoir, minimalement Disruptive tri

Question

Supposons que j'ai une liste de choses (nombres, de garder les choses simples ici) et j'ai une fonction que je veux utiliser pour les trier par, en utilisant SortBy. Par exemple, le suivant trie une liste de numéros par le dernier chiffre:

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

Et remarquez comment deux (c.-à-tous) ces chiffres ont le même chiffre. L'ordre dans lequel nous les renvoyons n'a pas d'importance. Dans ce cas, Mathematica les renvoie dans l'ordre inverse. Comment puis-je m'assurer que tous les liens sont rompus en faveur de la façon dont les articles ont été commandés dans la liste originale?

(Je sais que c'est un peu trivial mais j'ai l'impression que cela arrive de temps en temps, alors j'ai pensé que ce serait pratique pour l'obtenir sur StackOverflow. me bat à elle)

Les tentatives de faire de ce plus des recherches. genre avec une perturbation minimale, sorte avec moins nombre de swaps, bRIS sur mesure, le tri avec swapping coûteux, stable de tri.

PS: Merci à Nicholas de remarquer que ce qu'on appelle le tri stable. C'était sur le bout de ma langue! Voici un autre lien: http://planetmath.org/encyclopedia/StableSortingAlgorithm.html

Answer 1

Après avoir demandé autour, on m'a donné une explication satisfaisante:

Réponse courte: Vous voulez SortBy[list, {f}] obtenir une sorte stable.

Réponse longue:

SortBy[list, f] liste des sortes dans l'ordre déterminé par l'application f à chaque élément de la liste, ex aequo en utilisant l'ordre canonique expliqué dans Trier. (Ceci est la deuxième note "Plus d'informations" documentée dans le documentation for SortBy.

SortBy[list, {f, g}] casse les attaches en utilisant l'ordre déterminé en appliquant g à chaque élément.

Notez que SortBy[list, f] est la même que SortBy[list, {f, Identity}].

SortBy[list, {f}] ne fait pas bris d'égalité (et donne une sorte stable), ce qui est ce que vous voulez:

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

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

Enfin, la solution de Sakra SortBy[list, {f, tie++ &}] est effectivement équivalent à SortBy[list, {f}].

Answer 2

Cela semble fonctionner:

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

Mais maintenant je vois rosettacode donne une beaucoup plus agréable façon de le faire:

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

Alors commande est la clé! Il semble que la documentation de Mathematica ne mentionne pas cette différence parfois importante. Trier et commander.

Answer 3

Est-ce que GatherBy fait ce que vous voulez?

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

Answer 4

Il existe une variante de SortBy qui rompt les liens en utilisant des fonctions de commande supplémentaires:

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

par des liens de comptage, vous pouvez ainsi obtenir un tri stable:

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

rendements

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