JarCastingPartition
In mathematical terms, according to the book Naive Set Theory (Halmos), a partition of a set U is a set of nonempty subsets of U such that every element u in U is in exactly one of these subsets.
This package provides the Partition interface which complies to this mathematical concept, as well as two implementations with different characteristics. The UnionFindPartition implementation is a Union-Find-Delete data structure with operations bounded by the inverse Ackermann function. The ImmutablePartition class is an immutable implementation with constant time access to all the supported methods.
Using
You can add a dependency from your project as follows:
Using Maven
<dependency>
<groupId>gr.james</groupId>
<artifactId>partition</artifactId>
<version>0.8</version>
</dependency>
Using Gradle
implementation 'gr.james:partition:0.8' // Runtime
api 'gr.james:partition:0.8' // Public API
Examples
Typical usage for a set of integers.
Partition<Integer> p = new UnionFindPartition<>();
IntStream.range(0, 10).forEach(p::add);
p.union(0, 1);
p.union(1, 2);
System.out.println(p);
p.union(3, 4);
p.union(4, 5);
p.union(5, 6);
p.union(6, 7);
System.out.println(p);
p.union(8, 9);
System.out.println(p);
p.merge(10, 2);
System.out.println(p);
p.addSubset(new HashSet<>(Arrays.asList(11, 12)));
System.out.println(p);
Import from string.
Partition<Integer> p = new UnionFindPartition<>("[[1,2][3]]", Integer::parseInt);
System.out.println(p);
Immutable partition (UnsupportedOperationException).
Partition<Integer> p = new ImmutablePartition<>("[[1,2][3]]", Integer::parseInt);
System.out.println(p);
p.union(1, 3);
Enumerate all possible partitions of 4 elements with exactly 2 or 3 subsets in lexicographic order.
final Partition<Integer> p = new UnionFindPartition<>();
IntStream.range(0, 4).forEach(p::add);
Iterator<Partition<Integer>> it = Partitions.lexicographicEnumeration(
p.elements(), 2, 3, UnionFindPartition::new);
while (it.hasNext()) {
System.out.println(it.next());
}
Same snippet with reverse lexicographic order.
final Partition<Integer> p = new UnionFindPartition<>();
IntStream.range(0, 4).forEach(p::add);
Iterator<Partition<Integer>> it = Partitions.reverseLexicographicEnumeration(
p.elements(), 2, 3, UnionFindPartition::new);
while (it.hasNext()) {
System.out.println(it.next());
}
Enumerate all possible partitions of 4 elements with exactly 1 or 3 subsets in lexicographic order.
final Partition<Integer> p = new UnionFindPartition<>();
IntStream.range(0, 4).forEach(p::add);
Iterator<Partition<Integer>> it = Partitions.lexicographicEnumeration(
p.elements(), new int[]{1, 3}, UnionFindPartition::new);
while (it.hasNext()) {
System.out.println(it.next());
}