Talk:Orderings

Code of the orderings

Do we agree that the following code always produces the respective orderings?
(Compare Commons:File:Orderings;_6_choose_3.svg)
If so, we should include the formulas in the article, including versions for Mathematica etc.

Name	Shorthand	Pseudocode	MATLAB code
Lexicographic order	lex	lex(M)	sortrows(M)
Reverse lexicographic order	rev lex	vert( lex(M) )	rot90( sortrows(M) , 3 )'
Reflected lexicographic order	ref lex	horz( lex(M) )	rot90( sortrows(M) )'
Reverse reflected lexicographic order	rev ref lex	rot( lex(M) )	rot90( sortrows(M) , 2 )
Colexicographic order	colex	rot( -lex(-horz(M)) )	rot90( -sortrows(-rot90(M)') , 2 )
Reverse colexicographic order	rev colex	horz( -lex(-horz(M)) )	rot90( -sortrows(-rot90(M)') )'
Reflected colexicographic order	ref colex	vert( -lex(-horz(M)) )	rot90( -sortrows(-rot90(M)') , 3 )'
Reverse reflected colexicographic order	rev ref colex	-lex(-horz(M))	-sortrows(-rot90(M)')

Is there possibly an easier code for colex ordering? Tilman Piesk 23:47, 1 February 2012 (UTC)

Abstract mathematical definition for the total order needed

I think we need a definition like Wikipedia's [[1]], either in the beginning of this article, or maybe as its own separate page. Note that these "sorting methods" form just a tiny subset of all possible total orders that can be devised for any particular combinatorial structure. Antti Karttunen 13:32, 9 August 2012 (UTC)

Ranking and Unranking Partitions.

example: take a random partition of 1000 :

pr={140, 131, 69, 57, 45, 33, 32, 31, 31, 30, 25, 20, 20, 15, 12, 11, 11, 11, 
10, 10, 10, 9, 8, 8, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 4, 4, 4, 4, 
4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

in Mathematica order <http://oeis.org/wiki/Reverse_reflected_lexicographic_order>

rankpartition[pr] equals 1720060175047629205108063970726 and unrankpartition[ 1000, 1720060175047629205108063970726] produces pr as above.

Not too complex to program; but how about ranking and unranking in other ordering systems?

---

with : integerpartitions[n,k] : count of partitions of n with largest part <= k ; --

• rankpartition[(p_)?PartitionQ] := PartitionsP[Tr[p]] - Sum[(integerpartitions[Tr[#1], First[#1] - 1] &)[Drop[p, k]], {k, 0, Length[p] - 1}];
• unrankpartition[n_Integer,k_Integer] := Block[{ove,res,qq,zz,mem}, ove =PartitionsP[n]-k; res={}; While[n-Tr[res]>0, qq=0;zz=0;While[(mem= integerpartitions[n-Tr[res],qq+1])<= ove,zz=mem;qq++]; AppendTo[res,qq+1];ove=ove-zz]; res]/; k<=PartitionsP[n];

---

--Wouter Meeussen 14:32, 31 October 2012 (UTC)