1
$\begingroup$


As mentionned in the topic title, I try to apply my own sorting functions to a set of elements via the Sort command. I make here a quick presentation of the subject before.


1) Method


We will remain in 2D throughout the description of the problem

1-1) Treatment of the component

We consider a component of a vector as a real number.
To sort two real, it is necessary to compare them.
The particularity of the sort that I want to apply is that the comparison depend of a specific criterion c which can take two values ("max" and "min").

In this case, to qualify the order relation between the two numbers, we won't say that :
- something1 is superior/inferior to something2 but,
- something1 dominate/don't dominate something2.

You can either :
- Wanting to maximize the value of the component. c = "max"
- Wanting to minimize the value of the component. c = "min"

Example :

With :

Group n°1 : a1 = 5 and a2 = 3
Group n°2 : a3 = -2 and a4 = -3

  • If c = "max"
    We have a1 > a2, so a1 dominates a2.
    We have a3 > a4, so a1 dominates a2.

  • If c = "min"
    We always have a1 > a2, but now a2 dominates a1.
    We always have a3 > a4, but now a1 dominates a2.

Remarks :
- We can not decide in case of equality, so no number dominates another.
- The criterion c allows you to change the sort direction.


1-2) Treatment of the vector

The functions that I want to use, are based on the principle of dominance (translated from french), and its variations.

Principle 1 :
We say that a vector J dominates a vector K if :
- J is at least as good as K in all component.
- J is strictly better than K in at least one component.

Examples :

Take two vector such as :

v1 = {2, 5};
v2 = {1, 6};

We have several possibilities to compare this two vector according to the value of the criterion c for each of these components.

  • v1[[1]] > v2[[1]]
  • v1[[2]] < v2[[2]]

Case 1 : {"max","max"}
We can't say if a vector dominate an other.

Case 2 : {"max","min"}
v1 dominate v2.

Case 3 : {"min","max"}
v2 dominate v1.

Case 4 : {"min","min"}
We can't say if a vector dominate an other.

So we can see here, that the sort of this two vector depend directly of the value of c.


2) My code


CompO[w_, x_, y_] :=
  Block[
       {Res},
        Res = If[
                 x == y,
                 {0},
                 If[w == "max", Ordering[{x, y}, -1], Ordering[{x, y}, 1]]]
       ];

BoolCompVDS[w__, x__, y__] :=
  Block[
        {step1, step2, step3, Res},
         step1 = MapThread[CompO, {w, x, y}];
         step2 = DeleteCases[Union@step1, 0, Infinity];
         step3 =
               If[
                  Count[step2, _Integer, Infinity] == 1,
                  Flatten@step2,
                 {0}
                 ];
          Res = If[step3 == {1}, True, False]
        ];

To understand :

We need to compare two vector :

v1 = {2, 5};
v2 = {1, 6};

The rule (for this example) are the following :
- We want to maximize the first component.
- We want to minimize the second component.

According to the principle 1 :

  • v1[[1]] > v2[[1]] so v1[[1]] dominate v2[[1]] (we want to maximize)
  • v1[[2]] < v2[[2]] so v1[[2]] dominate v2[[2]] (we want to minimize)

So v1 dominate v2 and :

BoolCompVDS[{"max","min"}, v1, v2]  

give "True"


3) Problem


Thanks to the post of Mr. Wizards, my original question can be formulated like this :
Why the use of Sort with my personal function does not produce a strict order as may be the case with the use of the Norm function (for example) ?

As seen in the post of Mr Wizards, the Sort command is designed to work with strict order relations.
I would write an answer for an update on sorting with function based on dominance relations soon.

$\endgroup$
  • $\begingroup$ Please explain what do you exactly mean by "If the sort function BoolCompVDL Work, this is not the case with the functions BoolCompVDS and BoolCompVDM." (in which way/s they don't "work") $\endgroup$ – Dr. belisarius Feb 17 '16 at 10:38
  • 3
    $\begingroup$ Agree "that's a lot of information to integrate", a more minimalistic question would be easier to answer. $\endgroup$ – rhermans Feb 17 '16 at 11:22
  • 4
    $\begingroup$ You are giving too much irrelevant information. This is a serious mental load on all those who would try to answer. My first reaction is to ignore the question, and I am sure I am not alone. Look at some of the reasonably voted questions for examples of how to formulate a question well, and construct a minimal example, if you want to increase the chances for good answers. $\endgroup$ – Leonid Shifrin Feb 17 '16 at 13:01
  • $\begingroup$ Could you specify a general rule, how two vectors {a, b} and {c, d} should be ordered? I find part 2 of your question incredibly hard to comprehend. As I think I have gathered, the ordering {{a, b}, {c, d}} is correct if a < c and b > d, but for the example functions #^2 and #^3 this is never simultaneously realized. $\endgroup$ – LLlAMnYP Feb 17 '16 at 13:12
  • $\begingroup$ Why is BoolCompVDS defined with three parameters of variable length i.e. BoolCompVDS[w__, x__, y__] and what do you expect this to do? $\endgroup$ – Mr.Wizard Feb 17 '16 at 17:40
6
$\begingroup$

Establishing the question

Working through this post was confusing but I think I at least understand your question now.

First let me see if I can reduce your code quite a lot. :-) I believe your BoolCompVDS can be replaced with merely this:

fn1[c_][v1_, v2_] := Min[#] >= 0 && Max[#] > 0 &[(v1 - v2) c]

The c parameter takes a list of 1 or -1 representing "max" or "min" respectively.

There is equivalence:

rnd = RandomReal[{-9, 9}, {100, 2, 2}];

Equal[
 BoolCompVDS[{"max", "max"}, #1, #2] & @@@ rnd,
 fn1[{1, 1}] @@@ rnd
]
True

Now the question is why the final output of this is not all True:

{{-2, -2}, {1, -4}, {1, 0}, {-1, -4}, {-3, 1}};
Sort[%, fn1[{1, 1}]]
Partition[%, 2, 1]
fn1[{1, 1}] @@@ %
{{-3, 1}, {1, 0}, {1, -4}, {-1, -4}, {-2, -2}}

{{{-3, 1}, {1, 0}}, {{1, 0}, {1, -4}}, {{1, -4}, {-1, -4}}, {{-1, -4}, {-2, -2}}}

{False, True, True, False}

Is my understanding correct?

Examining the situation

I believe Sort operates assuming that the ordering function produces a strict order, meaning among other things that a < b and b < c implies a < c, and I believe your ordering function does not conform to this requirement. Here is a simpler example of the issue:

fn = Mod[#, 2] < Mod[#2, 3] &;

Sort[Range @ 10, fn]

fn @@@ Partition[%, 2, 1]
{9, 6, 7, 1, 2, 4, 3, 5, 8, 10}

{False, True, False, True, True, False, True, True, True}

I recall that there are ways to work with this kind of ordering though I cannot recall the details. I think in any case the problem requires additional specification. Some references that may help with that:

$\endgroup$
  • $\begingroup$ Min[#] >= 0 && Max[#] > 0 & - if the smallest of two quantities is positive, no need to test if the larger quantity is also positive, no? $\endgroup$ – J. M. is away Feb 17 '16 at 19:23
  • $\begingroup$ @J.M. The minimum needs to be zero-or-greater, while the maximum must be strictly greater-than-zero. This is by my understanding of the OP's Principle 1 and it appears to agree with his own function. I suppose another way to write this would be NonNegative @ Min[#] && Max[#] != 0. $\endgroup$ – Mr.Wizard Feb 17 '16 at 19:39
  • 1
    $\begingroup$ What I had in mind was something like Min[#] > 0 || Min[#] < Max[#], so that it short-circuits as soon as it is known that the minimum is positive. $\endgroup$ – J. M. is away Feb 17 '16 at 19:46
  • $\begingroup$ @J.M. That didn't occur to me. :-) $\endgroup$ – Mr.Wizard Feb 17 '16 at 20:24
  • 1
    $\begingroup$ @Mr.Wizard. Based on your results, you understood everything. $\endgroup$ – Doedalos Feb 18 '16 at 14:15
1
$\begingroup$

I make here a rapid conclusion on the various sorting methods that I want to study.

The different elements to understand the problem and presented in the first post still valid.

Here you can see the various principles that I wanted to implement and the associated code.


Principle


  • Principle 1 :
    We say that a vector J dominates a vector K if :
    -J is at least as good as K in all component.
    -J is strictly better than K in at least one component.

  • Principle 2 :
    We say that a vector J dominates a vector K if :
    -If the value of the worst component of J is smaller than the worst component of K.

  • Principle 3 :
    We say that a vector J dominates a vector K if :
    -There is an index value q such as all the components between 0 and q (included) are equal.
    -The component of J at the position (q + 1) dominates the component of K on the same position.

Here you can see the corresponding code :

CompO[w_, x_, y_] :=
  Block[
        {Res},
        Res = If[
                 x == y,
                 {0},
                 If[w == "max", Ordering[{x, y}, -1], Ordering[{x, y},1]]
                ]
       ];


BoolCompVDS[w__, x__, y__] :=
  Block[
        {step1, step2, step3, Res},
         step1 = MapThread[CompO, {w, x, y}];
         step2 = DeleteCases[Union@step1, 0, Infinity];
         step3 =
               If[
                  Count[step2, _Integer, Infinity] == 1,
                  Flatten@step2,
                  {0}
                 ];
               Res = If[step3 == {1}, True, False]
        ];


BoolCompVDM[w__, x__, y__] :=
  Block[
        {step0, step1, step2, step3, step4, Res},
         step0 = {x, y};
         step1 = MapThread[CompO, {w, x, y}];
         step2 = (Flatten@step1) /. {1 -> 2, 2 -> 1};
         step3 = Ordering[Abs@Table[step0[[i, step2[[i]]]], {i, 1, 2, 1}], -1];
         step4 = (step2[[step3]]) /. {1 -> 2, 2 -> 1};
         Res = If[step4 == {1}, True, False]
       ];


BoolCompVDL[w__, x__, y__] :=
  Block[
        {step1, step2, step3, Res},
         step1 = Flatten@MapThread[CompO, {w, x, y}];
         step2 = FirstPosition[step1, 1 | 2, {0}];
         step3 = If[step2[[1]] != 0, step1[[step2]], {0}];
         Res = If[step3 == {1}, True, False]
        ];

SortVDS[x_, y_] := Sort[x, BoolCompVDS[y, #1, #2] &];
SortVDM[x_, y_] := Sort[x, BoolCompVDM[y, #1, #2] &];
SortVDL[x_, y_] := Sort[x, BoolCompVDL[y, #1, #2] &];

To compare the results of different sort :

data = RandomInteger[{-9, 9}, {10, 2}];

SortVDS[data, {"max", "max"}]
SortVDM[data, {"max", "max"}]
SortVDL[data, {"max", "max"}]

We obtain :

Random list >> {{2, -5}, {-6, 5}, {6, 9}, {-6, -4}, {4, -6}}

Sort n°1 >> {{6, 9}, {4, -6}, {-6, 5}, {-6, -4}, {2, -5}}
Sort n°2 >> {{6, 9}, {-6, -4}, {-6, 5}, {2, -5}, {4, -6}}
Sort n°3 >> {{6, 9}, {4, -6}, {2, -5}, {-6, 5}, {-6, -4}}

As mentioned by Mr.Wizards, only the principle 3 allows a total ordering.
This does not mean that the other sort are uninteresting.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.