# Sort sequences by their "randomness"

Example matrix (rows always have equal lengths)

mat = {
{1, 2, 3, 4, 5},
{1, 1, 1, 1, 1},
{1, 3, 4, 7, 9},
{2, 2, 2, 2, 2},
{5, 4, 3, 2, 1},
{8, 4, 7, 9, 2},
{3, 2, 1, 2, 3},
{1, 3, 5, 7, 9}};


I tried to sort mat in the following manner:

{{1, 1, 1, 1, 1}, (* All elements are equal *)
{2, 2, 2, 2, 2}, (* All elements are equal *)
{1, 2, 3, 4, 5}, (* Sorted sequence with equal differences of 1 *)
{5, 4, 3, 2, 1}, (* Reverse sorted sequence with equal differences of 1 *)
{1, 3, 5, 7, 9}, (* Sorted sequence with equal differences of 2 *)
{1, 3, 4, 7, 9}, (* Sorted sequence with unequal differences *)
{3, 2, 1, 2, 3}, (* Unsorted sequence with few sort swaps needed *)
{8, 4, 7, 9, 2}} (* Unsorted sequence with many sort swaps needed *)


The closest solution I found was:

SortBy[mat, Abs @* Differences]


giving

{{1, 1, 1, 1, 1},
{2, 2, 2, 2, 2},
{1, 2, 3, 4, 5},
{3, 2, 1, 2, 3},
{5, 4, 3, 2, 1},
{1, 3, 4, 7, 9},
{1, 3, 5, 7, 9},
{8, 4, 7, 9, 2}}



Looking at {3, 2, 1, 2, 3}, which is in the wrong position, it becomes clear that we need at least one additional sort parameter for unsorted sequences: Count the number of permutations needed to Sort or ReverseSort them, but I don't know how to implement this.

Probably my description of the problem is incomplete or ambiguous, so please feel free to suggest another "entropic sort order".

• How about SortBy[mat, Entropy]? i.e., let the built-in function determine the sort order.
– Syed
Commented Sep 30, 2023 at 11:14
– eldo
Commented Sep 30, 2023 at 11:16
• I think what is missing is a statement of the consequences or goodness of a particular sort. Is there some metric that characterizes the goodness of a particular sort for which one can compare different sorts? And is it only about this particular list or is there some average performance for whatever process generates the lists? Otherwise, it's just an "I'll know it when I see it." assessment.
– JimB
Commented Sep 30, 2023 at 14:58

Using Entropy:

SortBy[mat, Entropy]


{{1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}, {1, 2, 3, 4, 5}, {1, 3, 4, 7,
9}, {1, 3, 5, 7, 9}, {5, 4, 3, 2, 1}, {8, 4, 7, 9, 2}, {3, 2, 1, 2,
3}}

Another attempt (and comparison) with the differences included:

{SortBy[mat, Entropy], SortBy[mat, {Entropy, Abs@*Differences}]} //
Map[Grid]


Variability of Differences of the input list seems to underly your verbal description of how desired output is obtained.

So, using Variance @* Differences (or MeanDeviation @* Differences or MedianDeviation @* Differences ...) as the first sorting criterion and Mean (Median or Variance also work for this case) as the second criterion gives the desired result:

sf = {Variance @* Differences, Mean};

Row[#, Spacer[20]] & @ Map[Labeled[MatrixForm@ToExpression@#, #, Top] &]@
{"mat", "desired", "SortBy[sf] @ mat"}