# C++ Reference: class DynamicPartition

This documentation is automatically generated.

Partition class that supports incremental splitting, with backtracking. See http://en.wikipedia.org/wiki/Partition_refinement . More precisely, the supported edit operations are:- Refine the partition so that a subset S (typically, |S| <<< N) of elements are all considered non-equivalent to any element in ¬S. Typically, this should be done in O(|S|).

- Undo the above operations (backtracking).

TODO(user): rename this to BacktrackableSplittingPartition.

Method | |
---|---|

`DebugString` | Return type: Arguments: |

`DynamicPartition` | Return type: Arguments: Creates a DynamicPartition on n elements, numbered 0..n-1. Start with the trivial partition (only one subset containing all elements). |

`DynamicPartition` | Return type: Arguments: Ditto, but specify the initial part of each elements. Part indices must form a dense integer set starting at 0; eg. [2, 1, 0, 1, 1, 3, 0] is valid. |

`ElementsInHierarchicalOrder` | Return type: ADVANCED USAGE: All elements (0..n-1) of the partition, sorted in a way that's compatible with the hierarchical partitioning: - All the elements of any given part are contiguous. - Elements of a part P are always after elements of part Parent(P). - The order remains identical (and the above property holds) after any UndoRefine*() operation. Note that the order does get changed by Refine() operations. This is a reference, so it'll only remain valid and constant until the class is destroyed or until Refine() get called. |

`ElementsInPart` | Return type: Arguments: |

`ElementsInSamePartAs` | Return type: Arguments: A handy shortcut to ElementsInPart(PartOf(e)). The returned IterablePart will never be empty, since it contains at least i. |

`FprintOfPart` | Return type: Arguments: Returns a fingerprint of the given part. While collisions are possible, their probability is quite low. Two parts that have the same size and the same fingerprint are most likely identical. Also, two parts that have the exact same set of elements will *always* have the same fingerprint. |

`NumElements` | Return type: Accessors. |

`NumParts` | Return type: |

`ParentOfPart` | Return type: Arguments: |

`PartOf` | Return type: Arguments: |

`Refine` | Return type: Arguments: Refines the partition such that elements that are in distinguished_subset never share the same part as elements that aren't in that subset. This might be a no-op: in that case, NumParts() won't change, but the order of elements inside each part may change. ORDERING OF PARTS: For each i such that Part #i has a non-trivial intersection with "distinguished_subset" (neither empty, nor the full Part); Part #i is stripped out of all elements that are in "distinguished_subset", and those elements are sent to a newly created part, whose parent_part = i. The parts newly created by a single Refine() operations are sorted by parent_part. Example: a Refine() on a partition with 6 parts causes parts #1, #3 and #4 to be split: the partition will now contain 3 new parts: part #6 (with parent_part = 1), part #7 (with parent_part = 3) and part #8 (with parent_part = 4). TODO(user): the graph symmetry finder could probably benefit a lot from keeping track of one additional bit of information for each part that remains unchanged by a Refine() operation: was that part entirely *in* the distinguished subset or entirely *out*? |

`SizeOfPart` | Return type: Arguments: |

`UndoRefineUntilNumPartsEqual` | Return type: Arguments: Undo one or several Refine() operations, until the number of parts becomes equal to "original_num_parts". Prerequisite: NumParts() >= original_num_parts. |