Ordered Partition Stacks

This post introduces an ordered partition stack. This is used to efficiently represent an ordered partition and the changes which occur to it over time. Before reading this you should read about ordered partitions.

Interface

The exact interface we choose for an ordered partition can vary, but the basic functionality always supported is:

PS_Points(p) # The points p is defined over
PS_Cells(p) # The number of cells in the partition p
PS_Cell(ps, i) # The contents of cell i of partition p, as an unordered list

PS_Cell(ps,i) is not required to return values in any particular ordering – we will see later why this list is unordered.

There are some other functions which are often provided by ordered partitions:

PS_CellOfPoint(p, x) # The cell which contains x
PS_FixedPoints(p) # A list of the points which are in a cell of size one
PS_CellLen(p, i) # The length of cell p

A Partition Stack adds the ability to modify an ordered partition. This modification is extremely restricted, all we are allowed to do is:

  • Take a subset S of the values in PS_Cell(ps,i)
  • Move the values in S to a new cell at the end of the partition (which will be cell PS_Cells(p)+1)

There are a few different ways to provide this function – a very low-level interface, and a high-level interface which provides (most) of the functionality that is required in practice. We will only provide the high-level interface here:

PS_SplitCellByFunction(ps, i, f)

This function requires a bit of explanation. f should be a function which accepts integers. The following operation is then performed:

  • Apply f to each element of PS_Cell(ps,i)
  • Partition PS_Cell(ps,i) into equivalence classes which return the

The Partition Stack also adds a time-travel function. This an set the partition stack back to an earlier state:

  • PS_Revert(ps, i) - Set the partition stack back to having i cells. i must be less than or equal to PS_Cells(ps).

Note that partition stacks can only be reverted – there is no method to go forwards again.

, which are used in both graph isomorphism and partition backtracking. We will give a definition and provide a simple (and inefficient!) implementation of ordered partitions in GAP.

This post is (probably) only of interest if you want to learn about graph isomorphism or partition backtracking!

Cell representation

An ordered partition of a set $\Omega$ is a partition of $\Omega$ where the cells of the partition are ordered. Let's give an example!

Given the set ${1\ldots 6}$, one ordered partition is $[{2,3,6}, {1}, {4,5}]$. Here the first cell of the partition is the set ${2,3,6}$, the second is ${1}$ and the last is ${4,5}$. No value occurs in more than one cell, and the unions of the cells is ${1\ldots 6}$.

How can we represent this in GAP? The easiest option is as a list of sets. We will call this the explicit representation:

part := [ Set([2,3,6]), Set([1]), Set([4,5]) ];

We can sanity check we have all our values by using Union to merge our list of sets:

Union(part);
# [1 .. 6 ]

Indicator Representation

There is one bad feature of this representation – it is very expensive to find which cell a particular value is contained in. Therefore let's consider a second representation, known as the simple indicator representation. This maps each value to the number of the cell it is contained in. For example, part from the previous example is represented by the list l := [2,1,1,3,3,1]. The simple indicator and explicit representations are linked by the condition $l[i] = j \leftrightarrow j \in part[i]$ .

Complex Indicator Representation

The complex indicator representation is like the simple indicator representation, except we allow the array to contain any values, not just the integers in a range [1..k]. For example, lx := [2, -6, -6, "Q", "Q", -6]. Two values $i$ and $j$ are in the same cell of the partition if and only if $lx[i] = lx[j]$.

But wait, we want ordered partitions! What ordering is there on 2, -6 and "Q"? When we use the complex indicator representation we will not care what the ordering is, as long as it is well-defined and consistent. GAP provides a complete ordering on (almost) all objects – all integers are less than "Q". By design, a simple indicator representation is also a complex indicator representation.

Here are a couple of GAP functions, which provide mappings between the explicit and complex indicator representations. Firstly, we will map explicit to complex indicator (actually, we always make a indicator:

CellsToList := function(cells)
    local cellpos, i, j;
    cellpos := [];
  # Iterate over all the cells
    for i in [1..Length(cells)] do
    # Iterate over the members of each cell
        for j in cells[i] do
            cellpos[j] := i;
        od;
    od;
    return cellpos;
end;

CellsToList([ [2,3,6], [1], [4,5] ]);
# [ 2, 1, 1, 3, 3, 1 ]

And now, let's go back the other way! The first this we do is gather all the values in the array into a GAP Set. We can then use Position to find the index of a value in that set.

ListToCells := function(cellpos)
    local cells, labels, i;
    # Find all unique cell labels
    labels := Set(cellpos);
    # make an empty list of cells
    cells := List([1..Length(labels)], x -> []);
    # Fill the cells
    for i in [1..Length(cellpos)] do
        AddSet(cells[Position(labels, cellpos[i])], i);
    od;
    return cells;
end;

ListToCells( [ 2, 1, 1, 3, 3, 1 ] );
# [ [ 2, 3, 6 ], [ 1 ], [ 4, 5 ] ]

ListToCells( [2, -6, -6, "Q", "Q", -6] );
# [ [ 2, 3, 6 ], [ 1 ], [ 4, 5 ] ]

Refining Partitions

An obvious question is, why have this horrible indicator representation at all? The reason is it makes it easy for us to express one of the most important operations we will perform on partitions, refinement.

Given two (possibly ordered) partitions $P$ and $Q$, which both partition the same set ${1\ldots n}$, $Q$ is a refinement of $P$ if every cell of $Q$ is contained in a cell of $P$. Alternatively, $Q$ can be created by splitting cells of $P$.

Important Aside: There is another definition of refinement which is stricter and imposes an order on the cells of $Q$ – this requires, if $P$ has $j$ cells, that $\forall i in {1..j}. Q[i] \subseteq P[i]$.

Let's consider a couple of ways of taking a partition, and generating a refinement of it. These will both be used over and over again in both partition backtrack, and graph automorphism detection.

Fixing a single point

Consider a partition in Cell format, let's consider our long-running example part := [ [2,3,6], [1], [4,5] ];. We want to take this and generate a new partition, where a single value has been extracted an placed in a cell by itself. For example, if we fixed 3, we might get [ [2,6], [1], [4,5], [3] ]. Alternatively, we might get [ [1], [3], [2,6], [4,5] ], because refining a partition does not make use of the order of the cells.

The easiest way to fix a single point is to switch to indicator representation, and change the value. Here is a function which accepts a cell input:

FixPoint := function(cells, point)
  local indic;
    indic := CellsToList(cells);
    indic[point] := infinity;
    return ListToCells(indic);
end;

FixPoint( [ [2,3,6], [1], [4,5] ], 3);
# [ [ 3 ], [ 2, 6 ], [ 1 ], [ 4, 5 ] ]

The meet of two partitions

Given two ordered partitions P and Q, we can define their meet as a new partition R, where two points are in the same cell of R if and only if they are in the same cells of both P and Q. Implementing this is easy (we will assume P and Q partition the same set). We will meet partitions frequently, while implementing partition backtracking.

PartitionsMeet := function(P, Q)
  local indicP, indicQ, indicJoin;
    indicP := CellsToList(P);
    indicQ := CellsToList(Q);
    indicJoin := List([1..Length(indicP)], i -> [indicP[i], indicQ[i]]);
    return ListToCells(indicJoin);
end;

PartitionsMeet([ [1,2,3], [4,5] ], [ [1,2], [3,4,5] ]);
# [ [ 1, 2 ], [ 3 ], [ 4, 5 ] ]

Applying permutations to partitions

Given an ordered partition Q and a permutation p, we define the action of p on Q as mapping each point in each cell of Q by p. GAP already has a function to do this, OnTuplesSets:

OnTuplesSets([ [2,3,6], [1], [4,5] ], (1,2,3,4,5,6));
# [ [ 1, 3, 4 ], [ 2 ], [ 5, 6 ] ]

In out searches, we will often want to look at all the permutations which map an ordered partition to itself, or one ordered partition to another. We will now give some quick results in this area, without proof.

  • Given an ordered partition $P$, the set of permutations $p$ such that $P^p = P$ is generated by the symmetric group of each cell of $P$.

GAP already uses this result internally.

Stabilizer(SymmetricGroup(5), [ [1,3], [2,4,5] ], OnTuplesSets);
# Group([ (2,4), (2,4,5), (1,3) ])

Definition: Two ordered partitions P and Q are agreeable if the number of cells in P is equal to the number of cells in Q, and for all i, the size of P[i] is equal to the size of Q[i]. This is, I think, easier to read as a function!

Agreeable := function(P,Q)
    if Size(P) <> Size(Q) then
        return false;
    fi;

    return ForAll([1..Size(P)], i -> Size(P[i]) = Size(Q[i]));
end;

Agreeable([ [1,2,3], [4,5] ], [[1,2], [3,4,5] ]);
# false
Agreeable([ [1,2,3], [4,5] ], [[1,2,3], [3,4,5] ]);
# false
Agreeable([ [1,2,3], [4,5],[5] ], [[1,2,3], [4,5] ]);
# false
Agreeable([ [1,2,3], [4,5] ], [[1,2,3], [4,5],[5] ]);
# false
Agreeable([ [1,2,3], [4,5] ], [[1,2,3], [4,5] ]);
# true

So, why is agreeable useful? For the following mini-lemma!

  • Given two ordered partitions P and Q, there exists a permutation p which maps P to Q if and only if P and Q are agreeable.

One direction of this lemma is trivial – if P and Q aren't agreeable, then there can't be any mapping from P to Q, as any image of P will be agreeable with P. If P and Q are agreeable, then we can easily construct a mapping from P to Q by imposing any ordering on the cells of P and Q, and mapping them pointwise. As every integer occurs exactly once in P and Q, this will define a permutation.

We can use this to construct all the mappings of P to Q. We can also construct them more easily using the fact that they form a coset of the mappings of P to itself.

Now we have a giant pile of partition-related results, we can start using them to do interesting things!