# Order list of monomials by degree (Pascal's Triangle)

Suppose I have the following list of monomials:

{1,x,x^2,y,y^2,x*y,x^2*y,x*y^2,x^2*y^2}


How could I manipulate it to get

{1,x,y,x*y,x^2,y^2,x^2*y,x*y^2,x^2*y^2}


such that they are in order by the total degree of the multivariate monomials?

It is important that although x*y, x^2, and y^2 all have the same degree, the x*y comes first.

Further Details

I was vague with my sorting conditions. Let me further define the problem.

The following could be considered Pascal's triangle of monomials:

                    |
1
x    |    y
x^2      x*y      y^2
x^3     x^2*y | x*y^2     y^3
...          x^2*y^2          ...
|


My goal is to ultimately extract a number of monomials from this triangle SYMMETRICALLY (from the centerline), starting at the top and moving outward from the centerline, moving to the next line in the triangle when needed. For example, if I want 4 monomials, I should get:

{1,x,y,x*y}


If i want 8 monomials, I should get:

{1,x,y,x*y,x^2,y^2,x^2*y,x*y^2}


A tricky case is if I want 9 monomials:

{1,x,y,x*y,x^2,y^2,x^2*y,x*y^2,x^2*y^2}


I can form a form of this triangle by creating the following matrix (easily generated):

  1     x     x^2     x^3  ...
y   x*y   x^2*y   x^3*y
y^2 x*y^2 x^2*y^2 x^3*y^2
y^3 x*y^3 x^2*y^3 x^3*y^3
.
.
.


So if I need a list of n monomials (assuming n is a valid number that lends to the symmetrical requirement), then I generate a size Ceiling[Sqrt[n]] matrix.

When I flatten the resulting matrix, I obtain a list similar to the one I originally posted, that I feel if could be sorted based on the symmetry rules, would allow me to obtain the desired number of monomials.

If anybody has a better approach to this, I would be most grateful.

-
Your sorting condition's a bit ambiguous. Which of $x^2 y$ and $xy^2$ should come first? –  Ｊ. Ｍ. Apr 5 '13 at 2:53
@J.M. I updated my question to include further details. Please review and see if you can help! –  Matthew Apr 5 '13 at 13:51
Will it help if you start with a triangle structure? For six (5+1) rows for example: Table[x^j y^(i - j), {i, 0, 5}, {j, i, 0, -1}] –  BoLe Apr 5 '13 at 14:12
It's still not well defined. You can use any n and get a symmetric polynomial: for instance 3 could be {1, x y, x^2 y^2}. Similarly, n=4 is not unique with only a condition on symmetry: besides the answer you give there is {1, x y, x^2 y, y^2 x}. –  bill s Apr 5 '13 at 14:41
@bill I edited the post and tried to clarify, let me know if I need more (I know I probably do) –  Matthew Apr 5 '13 at 14:47

sortF[lst_] := SortBy[lst, {Total@#, Variance[#]} &[Exponent[#, Variables[lst]]] &]

lst1 = {1, x, y, x^2, x y, y^2, x^2 y, x y^2, x^2 y^2};
lst2 = {1, z, x, y, x^2, z y, z^2, x y, y^2, x^2 y, x y^2, x^2 y^2};

sortF@lst1
(* {1, x, y, x y, x^2, y^2, x^2 y, x y^2, x^2 y^2} *)

sortF@lst2
(*  {1, x, y, z, x y, y z, x^2, y^2, z^2, x^2 y, x y^2, x^2 y^2} *)

-
Variance is a clever way to get x y in front of other degree 2 terms. –  Michael E2 Apr 5 '13 at 11:51
@Matthew Making this change to kguler's sorting parameters adapts the solution to your updated problem: sortF[lst_] := SortBy[lst, {Max@#, Total@#} &[Exponent[#, Variables[lst]]] &] –  Michael E2 Apr 5 '13 at 15:34

A crude function first which returns the total power of an expression depending on its head.

Empower[e_] := Switch[Head@e,
Integer, 0,
Symbol, 1,
Power, e[[2]],
Times, Total[Empower /@ List @@ e]]

Empower[Power[e_, n_]] := n


In case of Times it uses the special definition. You can sort a list with this function criteria.

SortBy[m, Empower]
(* {1, x, y, x^2, x y, y^2, x^2 y, x y^2, x^2 y^2} *)


I think this is called canonical order (x^2 before x y for instance).

Edit: You can supply SortBy with additional function(s) to break ties.

SortBy[m, {Empower@#, 1/(Length@Variables@# + 1)} &]
(* {1, x, y, x y, x^2, y^2, x^2 y, x y^2, x^2 y^2} *)


Edit 2: I think I have it now.

SortBy[m, {Empower@#, Map[Function[v,
Exponent[#, v] /. q_?(# == 0 &) -> \[Infinity]], Variables@m]} &]
(* {1, x, y, x y, x^2, y^2, x y^2, x^2 y, x^2 y^2} *)


In case of a tie it sorts according to a list of exponents of all variables. My Empower could of course be defined shorter (and more foolproof probably), for example:

{#, Total[Exponent[#, Variables[m]]]} & /@ m
(* {{1, 0}, {x, 1}, {x^2, 2}, {y, 1}, {y^2, 2},
(*  {x y, 2}, {x^2 y, 3}, {x y^2, 3}, {x^2 y^2, 4}} *)

-
Oops, I can see now that this is not in the desired order. –  BoLe Apr 5 '13 at 11:55
Edit sorts x y before x^2 yet I think you'd want x y^2 before x^2 y, in the increasing power of x, right? –  BoLe Apr 5 '13 at 12:39

I will try and answer your updated question with monomial triangle. You could construct it like this:

m = Table[x^j y^(i - j), {i, 0, 5}, {j, i, 0, -1}]

(* {{1}, {x, y}, {x^2, x y, y^2}, {x^3, x^2 y, x y^2, y^3},
(*  {x^4, x^3 y, x^2 y^2, x y^3, y^4}, {x^5, x^4 y, x^3 y^2, x^2 y^3, x y^4, y^5}} *)


With the extracting function:

Pull[t_, n_] :=
Module[{a = Accumulate[Length /@ t], i, e},
i = Last[Position[a, _?(# <= n &)]][[1]];
e = Take[t, i];
If[MemberQ[a, n], e,
Append[e,
With[{d = Length@t[[i + 1]]},
t[[i + 1, (d - n + a[[i]])/2 + 1 ;; (d + n - a[[i]])/2]]]
]
]
]

({#, Pull[m, #]} & /@ {3, 4, 6, 8}) // ColumnForm

(* {3,{{1},{x,y}}} *)
(* {4,{{1},{x,y},{x y}}} *)
(* {6,{{1},{x,y},{x^2,x y,y^2}}} *)
(* {8,{{1},{x,y},{x^2,x y,y^2},{x^2 y,x y^2}}} *)


It doesn't work with n=9 as it is now.

-