By a "set partition", specifically a set partition of {1,2,...,n}, I mean a collection of nonempty sets of integers between 1 and n such that each integer is in exactly one of the sets, and does not occur more than once in that set. Think of it as a way of dividing all the numbers between 1 and n into an arbitrary number of boxes, where both the boxes and their contents are unordered.
I have two different functions I need to compute for these kinds of object, which I will give as pseudocode below. I can make do without interleaving these functions, so it would be fine to have two different data structures for them, but if one structure is good for both, that would be nice. The time complexity of converting to or from the data structure is basically irrelevant compared to the time these functions take.
The first function is as follows:
setPartition FunctionA(setPartition partition):
choose a random integer i between 1 and n
choose a part P of partition uniformly at random
if i is in P:
return(partition)
else:
for j in P:
do a computation depending only on i and j, not on P or partition
if [condition depending on those computations]:
remove i from the part it is currently in
add i to P
return(partition)
else:
return(partition)
Notice here that in the step where we remove i from its current part, we need to remove that set from the collection if it becomes empty. We also cannot choose i by first choosing a random part and then a random element, since that does not give the right distribution, so looking up which part i is in is probably necessary. (We could choose a random part if we did it with each part having probability proportional to its size, but that'd require us to know the size of each part.)
The second is:
setPartition FunctionB(setPartition partition):
with probability p:
choose two distinct parts P and Q of partition uniformly at random
for i in P and j in Q:
do a computation depending only on i and j, not on P, Q, or partition
if [condition depending on those computations]:
merge parts P and Q into a single part
return(partition)
else:
return(partition)
otherwise:
choose a part P of partition uniformly at random
choose a subset Q of P uniformly at random (i.e. each element is in Q w.p. 50%)
for i in Q and j in (P minus Q):
do a computation depending only on i and j, not on P, Q, or partition
if [condition depending on those computations]:
remove the elements of Q from P
create a new part whose elements are Q
return(partition)
else:
return(partition)
Again, bear in mind that the merging of parts can't leave an empty part lying around -- the set partition must always consist of nonempty sets.
These functions are both run in a big loop modifying a single set-partition, say, a million times, or two million times, so obviously doing this by modifying in place seems like a good idea. I'm doing this for n around 2000 or so, so using more memory for faster computations is a good tradeoff, I think.
I've already implemented this once in R, representing the partitions as lists of lists in the obvious way, but that just isn't fast enough for the amount of computations I need, so I decided to reimplement it in C++. So I want to make sure I'm using the right data structure to begin with, so I don't have to reimplement it all a third time.