A partition of a set S is a separation of the set into an arbitrary number of non-empty, pairwise disjoint subsets whose union is exactly S. What manner of a data structure should be used to represent a partition of a set if the following methods need to be optimized:moving an element from one part to another, possibly an entirely new one, anditerating over the parts of the partition.A naive way of prioritizing 1 would be a hash/tree/whatever mapping from set elements to part labels, but iterating over the parts would require O(N) for first constructing the actual parts from the labels. 2 is naively prioritized as a hash/tree/whatever set of hash/tree/whatever sets, but then moving elements around, especially to new subsets, incurs that memory management overhead.Is there a way to get the best of both worlds? The implementation I need is Python but I imagine this is a cross-language question.
Data structure for partition of a set
data structures;partitions;sets