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
SortByandSortwork 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
SortByandSortoutput 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 forms[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.
