Phân loại ổn định, tức là phân loại tối thiểu

Question

Giả sử tôi có một danh sách các thứ (số, để giữ mọi thứ đơn giản ở đây) và tôi có một hàm tôi muốn sử dụng để sắp xếp chúng bằng cách sử dụng SortBy. Ví dụ, sau đây sắp xếp một danh sách các số bằng chữ số cuối cùng:

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

Và hãy chú ý cách hai (ví dụ, tất cả) những con số có cùng chữ số cuối cùng. Vì vậy, nó không quan trọng mà trật tự chúng tôi trả lại cho họ. Trong trường hợp này Mathematica trả về chúng theo thứ tự ngược lại. Làm cách nào để đảm bảo rằng tất cả các mối quan hệ đều bị hỏng trong việc ưu tiên các mục được đặt hàng trong danh sách gốc?

(Tôi biết đó là loại tầm thường nhưng tôi cảm thấy như thế này đi lên theo thời gian vì vậy tôi nghĩ rằng nó sẽ là tiện dụng để có được nó trên StackOverflow. Tôi sẽ đăng bất cứ điều gì tôi đưa ra như là một câu trả lời nếu không có ai đánh bại tôi với nó.)

Cố gắng thực hiện điều này dễ tìm kiếm hơn: sắp xếp với ít nhiễu nhất, sắp xếp ít nhất số lần hoán đổi, tùy chỉnh vi phạm, phân loại với trao đổi tốn kém, phân loại ổn định.

PS: Nhờ Nicholas để chỉ ra rằng đây được gọi là sắp xếp ổn định. Nó ở trên đầu lưỡi tôi! Đây một đường link khác: http://planetmath.org/encyclopedia/StableSortingAlgorithm.html

Answer 1

Sau khi hỏi xung quanh, tôi đã được giải thích thỏa mãn:

Câu trả lời ngắn: Bạn muốn SortBy[list, {f}] để có được loại ổn định.

Long trả lời:

SortBy[list, f] cả các loại danh sách theo thứ tự xác định bằng cách áp dụng f để mỗi phần tử của danh sách, quan hệ vi phạm sử dụng trật tự kinh điển giải thích dưới Sắp xếp. (Đây là ghi chú "Thông tin Bổ sung" được ghi lại lần thứ hai trong số documentation for SortBy.)

SortBy[list, {f, g}] ngắt liên kết bằng cách sử dụng thứ tự được xác định bằng cách áp dụng g cho từng phần tử.

Lưu ý rằng SortBy[list, f] giống với SortBy[list, {f, Identity}].

SortBy[list, {f}] làm không phá vỡ tie (và đưa ra một loại ổn định), đó là những gì bạn muốn:

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

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

Cuối cùng, Sakra của giải pháp SortBy[list, {f, tie++ &}] là có hiệu quả tương đương với SortBy[list, {f}].

Answer 2

Điều này dường như làm việc:

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

Nhưng bây giờ tôi thấy rosettacode đưa ra một cách rất đẹp làm:

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

Vì vậy, đặt hàng chính là chìa khóa! Có vẻ như tài liệu Mathematica không đề cập đến sự khác biệt quan trọng này khi sắp xếp và sắp xếp thứ tự.

Answer 3

GatherBy có làm những gì bạn muốn không?

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

Answer 4

Có một biến thể của SortBy mà phá vỡ mối quan hệ bằng cách sử dụng thêm chức năng đặt hàng:

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

Bằng cách đếm các mối quan hệ như vậy, bạn có thể lấy một sắp xếp ổn định:

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

sản lượng

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