Clasificación estable, es decir, clasificación mínimamente disruptiva

Question

Supongamos que tengo una lista de cosas (números, para mantener las cosas simples aquí) y tengo una función que quiero usar para ordenarlas, usando SortBy. Por ejemplo, el siguiente ordena una lista de números por último dígito:

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

Y cuenta cómo dos de (es decir, todos) esos números tienen el mismo último dígito. Por lo tanto, no importa en qué orden los devolvamos. En este caso, Mathematica los devuelve en el orden opuesto. ¿Cómo puedo asegurarme de que todos los vínculos se rompen a favor de cómo se ordenaron los artículos en la lista original?

(Sé que es un tanto trivial, pero siento que esto sucede de vez en cuando, así que pensé que sería útil hacerlo en StackOverflow. Publicaré lo que sea que se me ocurra como respuesta si nadie me pega a él)

Los intentos de hacer esto más búsquedas:. género con una perturbación mínima, género con menor número de intercambios, de encargo de desempate, la clasificación con intercambio costosa, estable de clasificación.

PD: Gracias a Nicholas para señalar que esto se llama clasificación estable. ¡Estaba en la punta de mi lengua! Aquí hay otro enlace: http://planetmath.org/encyclopedia/StableSortingAlgorithm.html

Answer 1

Después de pedir a su alrededor, se me dio una explicación satisfactoria:

Respuesta corta: ¿Quieres SortBy[list, {f}] para obtener una especie estable.

Respuesta larga:

SortBy[list, f] lista de las clases en el orden determinado por la aplicación de f para cada elemento de la lista, lazos se rompen utilizando la ordenación canónica explicó en Ordenar. (Esta es la segunda nota documentada de "Más información" en el documentation for SortBy.)

SortBy[list, {f, g}] rompe lazos usando el orden determinado aplicando g a cada elemento.

Tenga en cuenta que SortBy[list, f] es lo mismo que SortBy[list, {f, Identity}].

SortBy[list, {f}] hace ningún desempate (y da una especie estable), que es lo que quiere:

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

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

Por último, la solución de Sakra SortBy[list, {f, tie++ &}] es efectivamente equivalente a SortBy[list, {f}].

Answer 2

Esto parece funcionar:

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

Pero ahora veo rosettacode da una mucho mejor manera de hacerlo:

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

Así Ordenar es la clave! Parece que la documentación de Mathematica no hace mención de esta diferencia a veces importante Ordenar y Ordenar.

Answer 3

¿GatherBy hace lo que quiere?

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

Answer 4

Hay una variante de SortBy que se rompe lazos mediante el uso de las funciones de ordenación adicionales:

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

Al contar los lazos de este modo se puede obtener una clasificación estable:

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

rendimientos

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