Data structure for partition of a set
I'm not familiar with the topic, so all I can do is give a few pointers.
Manipulating partitions of finite sets is known by several names:


union-find when you start with singletons and progressively merge sets;
partition refinement when you start with a single set and progressively split it;
union-split-find when sets can be both merged and split as in your case.


Katherine J. Lai's discusses the union-split-find problem and proposes an algorithm using B-trees that double as finger trees to represent each set. Each element is represented by a distinct integer; using consecutive values for elements that are likely to remain together is more efficient. To merge two sets, split them into non-overlapping intervals that are entirely contained in one of the sets, and join the pieces together. See her thesis for details.