3
$\begingroup$

Familiar example of sorting objects

I have a list of $n$ "vectors" $\{x^{(1)},...,x^{(n)}\}$ of form $ x^{(i)}=\sum_{j=1}^m c_j^{(i)}x_j,i=1\dots n$, where $c_j^{(i)}$ are nonnegative coefficients of the vector $x^{(i)}$, and components $x_j$ are shared among them, and take some nonnegative values.

For example, we could have: $$ x^{(1)}=10x_1+2x_2\\ x^{(2)}=10x_1+3x_2+x_3\\ x^{(3)}=5x_1+2x_2 $$

I say that $x^{(a)}\ge x^{(b)}$ iff $x^{(a)} - x^{(b)}\ge 0$.

Since components $x_j$ are nonnegative, we have that $x^{(a)}\ge x^{(b)}$ if $c_j^{(a)}\ge c_j^{(b)}$ for every $j=1,\dots,m$. In this example, we can have a $\ge$ relation between all the "vectors", even thought $x_j$ are unknown.

Now we have defined the objects, and the comparator function, and our set of objects is comparable. Now, the above example can be easily sorted: $x^{(2)}\ge x^{(1)} \ge x^{(3)}$.

So desired result would be: $\{x^{(2)},x^{(1)},x^{(3)}\}$.

I noticed SortBy and Sort work for examples like this one.


Generalized sort with incomplete information

But a valid input can be the following example as well:

$$ x^{(1)}=10x_1+2x_2+x_3\\ x^{(2)}=10x_1+3x_2\\ x^{(3)}=5x_1+2x_2 $$

Here $x^{(2)}\ge x^{(3)}$ and $x^{(1)}\ge x^{(3)}$, and $x^{(3)}$ is clearly the smallest, but we can't compare $x^{(2)},x^{(1)}$ definitely. Which is larger, depends on components $x_2,x_3$. To resolve this, we take:

$$ x^{(2)}-x^{(1)}=x_2-x_3. $$

Now, we can see that $x^{(2)}\ge x^{(1)}$ iff $x_2\ge x_3 \text{ (c1)}$. Depending on this $\text{(c1)}$ condition, we can either have: $\{x^{(2)},x^{(1)},x^{(3)}\}$ or $\{x^{(1)},x^{(2)},x^{(3)}\}$ as the desired output.

But $x_j$ are "components" (unknown variables), thus in this second example, the desired output should contain all possible sortings and conditions under which they are valid. That is, more precisely, in this example, the desired output is:

$\{ \{\{x^{(2)},x^{(1)},x^{(3)}\},\{x_2\ge x_3\}\},\{\{x^{(1)},x^{(2)},x^{(3)}\},\{x_2\lt x_3\}\} \}$

A list of two sortings each with one condition under which they are valid.

The SortBy and Sort output one of the sortings (just the sorted list of "vectors") for these cases - but I need all of them along with the conditions.

The first example, under this generalized scenario, would then be:

$\{\{\{x^{(2)},x^{(1)},x^{(3)}\},\{\}\}\}$

A list with one possible sorting with no conditions (under all values for $x_j$'s).

Where "sorting" is a list pair of sorted elements and conditions under which the sorting is valid, as you can see in both examples.


How can I do this in mathematica?

Create a function that given input v={v[1], v[2], ..., v[n]} outputs the sortings: {s[1],s[2],...}, where sortings have form s[i]={{'sorted elements of v'},{'conditions'}}?

I was mentioning SortBy, and one naive solution that is probably possible, is to SortBy the list of vectors into $m!$ ways, by going over all permutations of attributes $x_j$ as criterions - Then eliminate the duplicate sortings, and finally extract the conditions from the remaining sortings. But this is extremely slow for large $m$ and does a lot of unecessary work (if the case is similar to example 1, then all of the $m!$ outputed sorted lists will be the same, and we will eliminate all but one...).

How can I implement my own sort that can do this reliably and always "sort" those vectors given $x_j$ are unknown? It will need to find such conditions or perhaps multiple cases of multiple conditions?


(To format the above two examples as code?)

Clear[x, v, w];
v = {10 x[1] + 2 x[2], 10 x[1] + 3 x[2] + x[3], 5 x[1] + 2 x[2]};
w = {10 x[1] + 2 x[2] + x[3], 10 x[1] + 3 x[2], 5 x[1] + 2 x[2]};

Then if the solution to our problem is function f[v_] := ..., then again:

First example F[v] should return:

 {{{10 x[1] + 3 x[2] + x[3],10 x[1] + 2 x[2],5 x[1] + 2 x[2]},{}}}

And f[w] should have two sortings:

f[w][[1]]={{10 x[1] + 2 x[2] + x[3], 10 x[1] + 3 x[2], 5 x[1] + 2 x[2]},{x[2]>=x[3]}}

f[w][[2]]={{10 x[1] + 3 x[2], 10 x[1] + 2 x[2] + x[3], 5 x[1] + 2 x[2]},{x[2]<x[3]}} 


Motivation:

I have a problem that I split into subproblems, and reduced each subproblem to such a list of "vectors". The subproblems can then be solved by solving a system of equalities that are constructed from the the sortings, that need to be solved assuming the condition under which the sorting is valid, and to have a complete set of solutions, all sortings are necessary to be considered.

This is a very very lengthy process if done by hand (a very large number of systems of equations arise from sortings - and the "vectors" form which I need to derive sortings can get messy), so I'm trying create an algorithm to do it in Mathematica, and this question above is the step where I'm currently stuck at.

$\endgroup$
  • $\begingroup$ Very well written and interesting question! $\endgroup$ – Marius Ladegård Meyer Jul 22 at 8:25
3
$\begingroup$

We identify each polynomial with its coefficient list. We use Internal`ListMin on the coefficient array of input list with FixedPointList to identify layers in the partial ordering we seek. Then for each layer with multiple elements we use Reduce to find the condition for each possible permutation of the elements.

ClearAll[coeffArray, paretoLayers, addCondition]

coeffArray = Normal @ Last @ CoefficientArrays[#] &

paretoLayers = Complement @@@ Partition[#, 2, 1] &[Most@
   FixedPointList[DeleteCases[#, Alternatives @@ Internal`ListMin[#]] &, #]] &;

addCondition[v_] := If[Length[#] == 1, {#, {}}, 
    Piecewise[{#, Reduce[LessEqual @@ (#.v), v, Reals]} & /@ Permutations[#]]] &;

 addCondition2[v_] := If[Length[#] == 1, {{#, {}}},
    {#, Reduce[LessEqual @@ (#.v), v, Reals]} & /@ Permutations[#]] &;

conditionalSorts[v_] := {Join @@ #[[1]], And @@ #[[2]]} & /@ 
  (Transpose /@ Tuples[addCondition2[Variables[v]] /@ 
       paretoLayers@coeffArray[v]] /. {} -> True)

Examples:

v = {10 x[1] + 2 x[2], 10 x[1] + 3 x[2] + x[3], 5 x[1] + 2 x[2]};
paretoLayers @ coeffArray[v]

{{{5, 2, 0}}, {{10, 2, 0}}, {{10, 3, 1}}}

addCondition[Variables[v]] /@ paretoLayers@coeffArray[v]

{{{{5, 2, 0}}, {}}, {{{10, 2, 0}}, {}}, {{{10, 3, 1}}, {}}}

conditionalSorts[v]

{{{{5, 2, 0}, {10, 2, 0}, {10, 3, 1}}, True}}

w = {10 x[1] + 2 x[2] + x[3], 10 x[1] + 3 x[2], 5 x[1] + 2 x[2]};
paretoLayers @ coeffArray[w]

{{{5, 2, 0}}, {{10, 2, 1}, {10, 3, 0}}}

addCondition[Variables[w]] /@ paretoLayers @ coeffArray[w]

enter image description here

To have a just a list of {orderedlist, condition} pairs use addCondition2:

addCondition2[Variables[w]] /@ paretoLayers@coeffArray[w]

{{{{{5, 2, 0}}, {}}}, {{{{10, 2, 1}, {10, 3, 0}}, x[2] <= x[3]}, {{{10, 3, 0}, {10, 2, 1}}, x[2] >= x[3]}}}

Display each layer as a column:

Column /@ %

enter image description here

Column @ conditionalSorts[w]

enter image description here

SeedRandom[1]
z = RandomInteger[5, {5, 3}].Array[x, 3]

{4 x[1] + 2 x[2] + 4 x[3], x[2], 2 x[2], 3 x[2] + 5 x[3], 2 x[1] + 3 x[3]}

addCondition[Variables[z]] /@ paretoLayers @ coeffArray[z]

enter image description here

addCondition2[Variables[z]] /@ paretoLayers@coeffArray[z]

{{{{{0, 1, 0}, {2, 0, 3}}, x[2] >= 1/3 (-2 x[1] + x[3])}, {{{2, 0, 3}, {0, 1, 0}}, x[2] <= 1/3 (-2 x[1] + x[3])}}, {{{{0, 2, 0}}, {}}}, {{{{0, 3, 5}, {4, 2, 4}}, x[2] <= 4 x[1] - x[3]}, {{{4, 2, 4}, {0, 3, 5}}, x[2] >= 4 x[1] - x[3]}}}

Column /@ %

enter image description here

Column @ conditionalSorts[z]

enter image description here

Update: Using Reduce directly if the input list is not too long:

ClearAll[AllOrderings]

allOrderings[a_] := {#, Reduce[LessEqual @@ #, Variables[a], Reals] }& /@  
  Permutations[a];

Examples:

allOrderings[v] // FullSimplify // Column

enter image description here

allOrderings[w] // FullSimplify // Column

enter image description here

$\endgroup$
  • $\begingroup$ Perfect, appreciate your response! Would you mind giving me advice on how to iterate this output (under your Examples) in mathematica-ish way? My goal here is to have {v,c} in each iteration, where v is the original list of "vectors" (or just a list of their coefficient tuples to be consistent with your example outputs), but sorted, under condition(s) c. I noticed conventional programming does not look or work best in mathematica and that's the reason for asking this. $\endgroup$ – Vepir Jul 22 at 16:09
  • $\begingroup$ @Vepir, thank you for the accept. Great question btw. I added addCondition2 which gives such a list. $\endgroup$ – kglr Jul 22 at 16:53
  • $\begingroup$ Thank you for following the follow up question - but what I meant to ask by my comment is for example: taking your first addCondition2 example output: out = {{{{{5, 2, 0}}, {}}}, {{{{10, 2, 1}, {10, 3, 0}}, x[2] <= x[3]}, {{{10, 3, 0}, {10, 2, 1}}, x[2] >= x[3]}}};, I wanted to extract and iterate (handle) all {v,c} pairs from it - here I wanted to do "for e in out" such that e is { { {5, 2, 0},{10, 2, 1}, {10, 3, 0} },{x[2] <= x[3]} } in first iteration and { { {5, 2, 0},{10, 3, 0}, {10, 2, 1} },{x[2] >= x[3]} } in second iteration. - to group all "vectors", conditions $\endgroup$ – Vepir Jul 22 at 17:20
  • $\begingroup$ I think your update "Using Reduce directly if the input list is not too long" is more of what I wanted to use, but perhaps I forgot to mention that there, it seems that more than needed amount of cases and condtitions is produced (Perhaps because its not taking into consideration that conditions are nonnegative as stated in the problem)? $\endgroup$ – Vepir Jul 22 at 17:42
  • $\begingroup$ @Vepir, I added conditionalSorts that reorganizes the output in the desired form. Re many conditions in the output of Reduce you are right; need to add the condition that all variables positive. Try if changing Reals to PositiveReals makes the desired difference. $\endgroup$ – kglr Jul 22 at 18:02

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.