On their own, your combinatorics Iterables look pretty generic.
- Given that they are
Iterables rather than Lists or Collections, one consideration would be instantiation with an Iterable.
Another thing to ponder would be the name itertools.
Even with "the basic three", this seems to call for common base classes - I gave it a try, without proper attention to other concerns. (One thing I'm never quite comfortable with is visibility: protected exposes quite a lot.) I didn't succeed in integrating Partitions without a second type parameter:
/** several classes for combinatorics */
abstract class Combinics {
/** Instantiated with a List of elements of type {@code E}, for
* one type of aggregation of elements represented as {@code
* List<I>} support iteration through all these aggregations.
* Elements at different positions are considered different. */
static abstract class Iterable<E, I>
implements java.lang.Iterable<List<I>> {
protected final /*E*/Object[] allElements;
/*final*/ int param;
public Iterable(List<E> allElements) {
final int count = allElements.size();
if (0 == count)
this.allElements = null;
else {
// E first = allElements.get(0);
this.allElements = allElements.toArray(
// off: allElements need not be of uniform type
// (E[]) Array.newInstance(first.getClass(), count)
);
}
}
}
/** Instantiated with a List of elements of type {@code E}, for
* one type of aggregation of elements represented as {@code
* List<I>} support iteration through all these aggregations.
* Elements at different positions are considered different. */
static abstract class Iterator<E, I>
implements java.util.Iterator<List<I>> {
final /*E*/Object[] allElements;
final int[] indices;
// ArrayList for extended interface - YAGNI?
ArrayList<I> next;
@SuppressWarnings("unchecked")
E get(int index) {
return (E) allElements[index];
}
Iterator(List<? extends E> allElements) {
this(allElements, allElements.size());
}
Iterator(List<? extends E> allElements, int count) {
indices = new int[count];
if (0 == count)
this.allElements = null;
else {
E first = allElements.get(0);
this.allElements = allElements.toArray(
// slightly off: allElement need not be of uniform type
(E[]) java.lang.reflect.Array.newInstance(
first.getClass(), count)
);
}
}
Iterator(Object[] allElements, int count) {
indices = new int[count];
this.allElements = allElements;
}
protected int size() { return indices.length; }
@Override
public boolean hasNext() {
return next != null;
}
/** for messages and more */// cache? nah...
protected String singular() {
String className = getClass().getName();
int
lastDot = className.lastIndexOf('.')+1,
lastIter = className.indexOf("Iter", lastDot);
if (0 <= ".$".indexOf(className.charAt(lastIter-1)))
lastIter -= 1;
return className.substring(lastDot,
lastIter).toLowerCase();
}
/** for messages and more */
protected String plural() { return singular() + 's'; }
@Override
public List<I> next() {
if (next == null) {
throw new NoSuchElementException(
"No " + plural() + " left.");
}
List<I> current = next;
generateNext();
return current;
}
/** Generates and keeps the next aggregation. */
abstract void generateNext();
/** non-public in java.util.Arrays */
protected static void swap(int[] array, int a, int b) {
int tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
}
/** Instantiated with a List of elements of type {@code E},
* for combinations of elements represented as {@code List<E>}
* support iteration through all these combinations.
* Elements at different positions are considered different. */
static abstract class IterElements<T> extends Iterator<T, T> {
IterElements(List<T> allElements) { super(allElements); }
IterElements(List<T> allElements, int count) {
super(allElements, count);
}
IterElements(Object[] allElements, int count) {
super(allElements, count);
}
protected void load() {
next = new ArrayList<>(size());
for (int i = 0; i < size() ; ++i) {
next.add(get(indices[i]));
}
}
}
static void
demo(int count, Function<List<?>, Iterable<?, ?>> generator) {
List<String> all = new ArrayList<>(count);
for (char c = 'A', end = (char) ('A' + count) ; c < end ; c++)
all.add(String.valueOf(c));
int row = 1;
for (List<String> elements : (Iterable<String, String>)
generator.apply(all)) {
System.out.printf("%2d: %s\n", row++, elements);
}
}
}
/** Instantiated with a List of elements of type {@code E},
* for combinations of elements represented as {@code List<E>}
* support iteration through all these combinations.
* Elements at different positions are considered different. */
public class Combination<E> extends Combinics.Iterable<E, E> {
public Combination(List<E> allElements, int nElements) {
super(allElements);
param = nElements;
}
public Combination(List<E> allElements) { this(allElements, -1); }
@Override
public java.util.Iterator<List<E>> iterator() {
return param < 0 ? new Iterator<E>(allElements)
: new Iterator<E>(allElements, param);
}
/** Instantiated with a List of elements of type {@code E},
* for combinations of elements represented as {@code List<E>}
* support iteration through all these combinations.
* Elements at different positions are considered different. */
static class Iterator<E> extends Combinics.IterElements<E> {
int currentSize;
Iterator(List<E> allElements) {
this(allElements, 1, allElements.size());
}
Iterator(List<E> allElements, int count) {
this(allElements, count, count);
}
Iterator(List<E> allElements, int start, int end) {
super(allElements, end);
init(start);
}
void init(int start) {
if (0 != indices.length) {
// Create the first combination.
currentSize = start;
next = new ArrayList<>(currentSize);
for (int i = 0; i < currentSize; ++i)
indices[i] = i;
load();
}
}
Iterator(Object... allElements) {
this(allElements, 1, allElements.length);
}
Iterator(Object[] allElements, int param) {
this(allElements, param, param);
}
Iterator(Object[] allElements, int start, int end) {
super(allElements, end);
init(start);
}
// @Override
// protected String singular() { return "combination"; }
@Override
protected int size() { return currentSize; }
@Override
void generateNext() {
next = new ArrayList<E>(next); // late?
if (indices[currentSize - 1] < allElements.length - 1) {
indices[currentSize - 1]++;
next.set(currentSize - 1, get(indices[currentSize-1]));
return;
}
for (int i = currentSize - 2; i >= 0; --i) {
if (indices[i] < indices[i + 1] - 1) {
indices[i]++;
for (int j = i + 1; j < currentSize; ++j) {
indices[j] = indices[j - 1] + 1;
}
load();
return;
}
}
if (indices.length < ++currentSize) {
next = null;
return;
}
for (int i = 0; i < currentSize; ++i) {
indices[i] = i;
}
load();
}
}
public static void main(String[] args) {
Combinics.demo(5, (all) -> new Combination<>(all));
Iterator<String> combinations =
new Combination.Iterator<String>(
Arrays.asList("A", "B", "C", "D", "E"), 3);
// provoke Exception
for (List<String> combi ;
null != (combi = combinations.next()) ; ) {
System.out.println(combi);
}
}
}
public class PartitionIterable<E>
extends Combinics.Iterable<E, List<E>> {
private final int blocks;
public PartitionIterable(List<E> allElements, int blocks) {
super(allElements);
checkNumberOfBlocks(blocks, allElements.size());
this.blocks = blocks;
}
@Override
public Iterator<List<List<E>>> iterator() {
return new PartitionIterator<>(allElements, blocks);
}
private void
checkNumberOfBlocks(int blocks, int numberOfElements) {
if (blocks < 1) {
throw new IllegalArgumentException(
"The number of blocks should be at least 1, received: "
+ blocks);
}
if (blocks > numberOfElements) {
throw new IllegalArgumentException(
"The number of blocks should be at most "
+ numberOfElements + ", received: " + blocks);
}
}
private static class PartitionIterator<E>
extends Combinics.Iterator<E, List<E>> {
private final int blocks;
private final int[] s;
private final int[] m;
private final int n;
PartitionIterator(List<E> allElements, int blocks) {
super(allElements);
this.blocks = blocks;
this.n = allElements.size();
s = indices;//new int[n];
m = new int[n];
if (n != 0) {
for (int i = n - blocks + 1; i < n; ++i) {
s[i] = m[i] = i - n + blocks;
}
loadPartition();
}
}
@Override
protected String singular() { return "partition"; }
private void loadPartition() {
next = new ArrayList<>(blocks);
for (int i = 0; i < blocks; ++i) {
next.add(new ArrayList<>());
}
for (int i = 0; i < n; ++i) {
next.get(s[i]).add(allElements.get(i));
}
}
@Override
void generateNext() {
for (int i = n - 1; i > 0; --i) {
if (s[i] < blocks - 1 && s[i] <= m[i - 1]) {
s[i]++;
m[i] = Math.max(m[i], s[i]);
int limit = n - blocks + m[i] + 1;
for (int j = i + 1; j < limit; ++j) {
s[j] = 0;
m[j] = m[i];
}
for (int j = limit; j < n; ++j) {
s[j] = m[j] = blocks - n + j;
}
loadPartition();
return;
}
}
next = null;
}
}
public static void main(String[] args) {
List<String> list = Arrays.asList("A", "B", "C", "D");
int row = 1;
for (int blocks = 1; blocks <= list.size(); ++blocks) {
for (List<List<String>> partition :
new PartitionIterable<>(list, blocks)) {
System.out.printf("%2d: %s\n", row++, partition);
}
}
}
}
class PermutationIterable<T>
extends Combinics.Iterable<T, T> {
public PermutationIterable(List<T> allElements) {
super(allElements);
}
@Override
public java.util.Iterator<List<T>> iterator() {
return new Iterator<>(allElements);
}
private static final class Iterator<T>
extends Combinics.IterElements<T> {
Iterator(List<T> allElements) {
super(allElements);
if (allElements.isEmpty())
next = null;
for (int i = 0; i < indices.length; ++i) {
indices[i] = i;
}
next = new ArrayList<>(allElements);
}
// @Override
// protected String singular() { return "permutation"; }
void generateNext() {
int i = indices.length - 2;
while (i >= 0 && indices[i] > indices[i + 1]) {
--i;
}
if (i == -1) {
// No more new permutations.
next = null;
return;
}
int j = i + 1;
int min = indices[j];
int minIndex = j;
while (j < indices.length) {
if (indices[i] < indices[j] && indices[j] < min) {
min = indices[j];
minIndex = j;
}
++j;
}
swap(indices, i, minIndex);
++i;
j = indices.length - 1;
while (i < j) {
swap(indices, i++, j--);
}
load();
}
}
public static void main(final String... args) {
Combinics.main(4,
(alphabet) -> new PermutationIterable<>(alphabet));
}
}
