Algorithm for number of transitions between pair of set (graph) partitions

Question

Say I have a set (or graph) which is partitioned into groups. I am interested to find the number of transitions between two partitions, where a transition involves taking an element out of one partition and moving it into another (or singleton partition by itself)

For example there is one transition between partitions

1 2 | 3 and 1 | 2 | 3

but between 1 2 3 4 and 1 2 | 3 | 4

The minimum number of transitions is 2 I believe.

So my question is are there algorithms that given a pair of partitions and a set, can return the number of transitions states between them?

There is a further complication that this set actually represents a graph and I would like every partition (and transition partition) to be connected (i.e. 1 2 | 3 would be invalid if there exists no in/direct connection between 1 and 2 unblocked by 3's single partition) but unless you are truly enlightened about this topic you can much probably ignore that.

Thanks

As a note I do have a method I thought of myself which is basically to find all neighbours of a partition A (i.e. all partitions which can be found within one transition) and do the same for partition B and if these is some overlap between these two sets of neighbours then they are one transition away. However this method gets very expensive very quickly.

Answer 1

I would expand on your method a little bit, and essentially build a graph and do a graph search. The vertices of the graph would be a valid partitioning of the set and the edges would be transitions. You can actually build and search at the same time and only build the portion of the graph necessary for the search.

To do this I would use an A* (or other best-first search) and at each step, generate all the neighbors of the current partition. The tricky part is determining the best heuristic for the A* search. You can probably estimate the number of transitions by assuming that all transitions would result in connected partitions (basically, ignore your constraint).

This is obviously expensive, but you save on time and space by using a best-first search and by generating the graph as you go.