## Generating set partitions – replacing virtual functions with protected inheritance

2015/07/14 6 Comments

The purpose of this long post is twofold: first, I really am in need of an efficiently implemented set partition enumerating library, and second, I would like to use this work as a pretext to share and discuss the designs that I considered. The latter is the main part here, as the algorithms themselves are taken from other people’s work, and the c++ discussion does not require a thorough understanding of them.

A set partition is a way to split elements of a finite set into disjoint subsets, called blocks. A way to model it is to take the set of natural numbers {0,1,2,…,n} as the initial set, and give each member a block number. Thus, for n=4 the partition (0,1,0,1) defines two blocks, block 0 containing elements 0 and 2, and block 1 containing elements 1 and 3. Of course, had we taken partition (1,0,1,0), we would have got the same split, so to avoid repetition there has to be a normalization rule: we start with block 0, and if a new block is needed, it gets the next number unused so far. A nice overview of the algorithms that accomplish this task has been gathered by Michael Orlov (section Technical reports at https://www.cs.bgu.ac.il/~orlovm/papers/ ), there’s even an accompanying implementation, but I think that with modern c++ one can now do better. And I need it for a student of mine who is doing research on some industrial process optimisation as well as for purely mathematical research, set partitions have a lot to do with probability, see for instance the explanatory paper by Roland Speicher: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.9723

# 1. Elementary solution for all partitions

Partitions of fixed size can be looked upon as an ordered collection of immutable elements, and the most natural way to implement this kind of objects in c++ is to have a collection object equipped with iterators, technically speaking `const_iterators`

. Actually, most work is done in iterators in this case, the collection object is just needed for the convenience of having `begin`

and `end`

methods, which allows for instance the range `for`

loop syntax. Michael Orlov’s paper details four algorithms: initialization of first and last partition and generation of next and previous partition, in terms of two sequences, a current partition `k`

and a running maximum of used block numbers `m`

. I will not analyse the algorithms themselves, it is not necessary for the c++ discussion that follows, and Michael has already done a prefect job, please consult his text. So, my first take at implementing the unrestricted set partitions is as follows:

Read more of this post

## Recent Comments