[seqfan] ranking of partitions
wouter meeussen
wouter.meeussen at pandora.be
Sat Oct 2 16:58:12 CEST 2010
hi All,
can anyone point me to an explanation why there seems to be no algorithm to
identify the ranking of a partition like
7432221111 (it's the 1000 th partition among the 1575 partitions of 24,
using reverse lexicographic order).
For partitions of larger integers, say 128, it is impractical to first
generate them all.
Similar ranking exists for binary trees, Ksubsets, permutations, Gray codes,
and even set partitions.
Why not for partitions?
In http://en.wikipedia.org/wiki/Partially_ordered_set there is some
clarification about 'partial' versus 'total' ordering.
For partitions, it seems that a total order should be feasible by
introducing some arbitrary precedence rule (like reverse-lexicographic vs.
Abramowitz & Stegun ordering) [cfr.
http://en.wikipedia.org/wiki/Dominance_order]
The point is that several orderings are in use, but no one explicitely
states that a ranking algorithm cannot exist.
Wouter.
More information about the SeqFan
mailing list