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.
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.
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.
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.
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.
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].
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].
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.
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.
> 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]