|
Ordered partition stacks have been implemented with their own
type and Magma intrinsics. They implement the data structure
described very briefly in section 2 of Jeff Leon's 1997 paper [Leo97].
They can be used as an aid to implementing various backtrack searches
in the Magma language.
The domain set of the partitions is always {1..n}, where n is called
the degree of the stack. The basic "push" operation for these stacks
involves refining an ordered partition, and the precise definition of
refinement used in the Magma implementation is Definition 2 of [Leo97].
This differs from the definition in Chapter 9 of [Ser03], for
instance.
The word "ordered" refers to the cells of the partition being in
a fixed order. The order of points in a cell is not significant, and may
vary as the data structure is manipulated.
Create a data structure representing a complete ordered partition stack
of degree n. Initially the stack has one partition on it, which is
the partition having a single block.
Create a data structure representing a zero-based ordered partition stack
of degree n with height limited to h. Initially the stack has one
partition on it, which is the partition having a single block, and has height
0.
The degree of the ordered partition stack P.
The height of the ordered partition stack P. For a complete stack, this
equals the number of cells of the finest partition on the stack.
NumberOfCells(P) : StkPtnOrd -> RngIntElt
The number of cells in the partition on stack P at height h.
If h is omitted it is taken to be the height of P, so giving the number
of cells in the finest partition on the stack P.
CellNumber(P, x) : StkPtnOrd, RngIntElt -> RngIntElt
The number of the cell of the partition at height h in P that contains
the element x. If h is omitted it is taken to be the height of P.
CellSize(P, i) : StkPtnOrd, RngIntElt -> RngIntElt
The size of cell i of the partition at height h in P.
If h is omitted it is taken to be the height of P.
Cell(P, i) : StkPtnOrd, RngIntElt -> SeqEnum
The contents of cell i of the partition at height h in P as a sequence
of integers. If h is omitted it is taken to be the height of P. Note that
the order of the points in the returned sequence may vary, as the order of
points in a cell of an ordered partition is not fixed.
A random element of cell i of the finest partition on P.
Rep(P, i) : StkPtnOrd, RngIntElt -> RngIntElt
An element of cell i of the finest partition on P.
The number of the cell that was split to first create cell number i.
Here are listed the basic operations provided for pushing a finer
partition onto an ordered partition stack, called splitting, and
for popping ordered partitions off the stack.
If the top partition on the stack has k cells, and one of these cells is
split to form a finer partition, then the new cell will have number k + 1, and
the residue of the split cell will have the same number as the cell that was
split. This agrees with the definition of refinement given in [Leo97],
Definition 2, but disagrees with [Ser03], Chapter 9.2, and
[McK81].
SplitCell(P, i, Q) : StkPtnOrd, RngIntElt, SeqEnum[RngIntElt] -> BoolElt
Attempt to refine the top partition on stack P by splitting cell i.
The new cell created will be {x} if x is in cell i, or will be
the intersection of Q with cell i (in the second form), if this is
not empty and not all of cell i. The new partition, if any, is pushed
onto the stack. The return value is true when P is changed, false
otherwise. This implements the operation in Definition 6 of [Leo97].
Refine the top partition on stack P by splitting all possible cells
using the values in V. This implements the operation given in
Definition 15 of [Leo97]. Cells are split in increasing order of cell
number, and the resulting new cells are in the curious order given in the cited
definition.
The first return value is true when P is changed, false otherwise. The
second is a hash value based on which cells are split, the values from V
used in the split, and the sizes of the resulting cells. It is suitable for
use as an indicator function, as defined in 2-16 of [McK81].
SplitCellsByValues(P, i, V) : StkPtnOrd, RngIntElt, SeqEnum[RngIntElt] -> BoolElt, RngIntElt
Refine the top partition on stack P by splitting all cells given in C,
or cell i, using the values in V. Splitting and return values are
as for SplitAllByValues, with an important difference: cells will be
split in the order given in C, and, if some cell in C does not split,
the operation will be terminated there, and false returned.
Pop(P, h) : StkPtnOrd, RngIntElt ->
Reduce the height of the partition stack P to height h, or by one
if h is not given. The method used is the "retract" algorithm of
[Leo97], Fig. 7.
This implements the "advance" algorithm of [Leo97], Fig. 7: X is a zero-based stack of degree d say, L is a sequence of length n taking values
in {1..d}, representing an unordered partition of {1..n} into d
blocks, P is a complete stack of degree n, and h is a positive integer
which is at most the height of P. This is a fundamental operation in
Leon's unordered partition stabilizer algorithm.
We set up an ordered partition stack of degree 12, and try out
a few basic operations on it. The printing of a stack shows the top
partition of the stack.
> P := OrderedPartitionStack(12);
> P;
Partn stack, degree 12, height 1
[ 1 2 3 4 5 6 7 8 9 10 11 12]
> SplitCell(P, 1, 4);
true
> P;
Partn stack, degree 12, height 2
[ 1 2 3 12 5 6 7 8 9 10 11 | 4]
Note that the order of the points in cell 1 is not significant. Now we will
split on the values in a vector V.
> V := [i mod 5 + 1: i in [0..11]];
> V;
[ 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2 ]
> SplitAllByValues(P, V);
true 119375796
> P;
Partn stack, degree 12, height 6
[ 1 6 11 | 4 | 10 5 | 9 | 8 3 | 12 2 7]
Only cell 1 has been split.
The points corresponding to the minimum value in V remain in cell 1.
The new cells are cells 2 to 6. They correspond to the higher values in V,
in descending order. Now pop the stack back to height 4 and try the effect
of a different split by values.
> Pop(P, 4);
> P;
Partn stack, degree 12, height 4
[ 1 6 11 12 2 7 8 3 | 4 | 10 5 | 9]
> V := [i mod 4 + 1: i in [0..11]];
> V;
[ 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4 ]
> SplitAllByValues(P, V);
true 985543242
> P;
Partn stack, degree 12, height 8
[ 1 | 4 | 5 | 9 | 8 12 | 11 7 3 | 6 2 | 10]
> Pop(P, 3);
> P;
Partn stack, degree 12, height 3
[ 1 6 2 11 7 3 8 12 9 | 4 | 5 10]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|