(See the next iteration here.)
Intro
This time, I have an Iterator<List<Integer>> implementation that generates list index tuples in lexicographic order. The sample main() output for new IndexTupleIterator(3, 6) is:
1: [0, 1, 2]
2: [0, 1, 3]
3: [0, 1, 4]
4: [0, 1, 5]
5: [0, 2, 3]
6: [0, 2, 4]
7: [0, 2, 5]
8: [0, 3, 4]
9: [0, 3, 5]
10: [0, 4, 5]
11: [1, 2, 3]
12: [1, 2, 4]
13: [1, 2, 5]
14: [1, 3, 4]
15: [1, 3, 5]
16: [1, 4, 5]
17: [2, 3, 4]
18: [2, 3, 5]
19: [2, 4, 5]
20: [3, 4, 5]
In general, for a list of \$n > 0\$ elements and index tuple length \$k \in \{1, \ldots, n \}\$, the total number of index tuples will be presicely
$$\binom{n}{k}.$$
Code
com.github.coderodde.util.IndexTupleIterator.java:
package com.github.coderodde.util;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.function.Consumer;
/**
* This class implements an iterator that generates index tuples in
* lexicographic order.
*
* @version 1.0.0
* @since 1.0.0
*/
public final class IndexTupleIterator implements Iterator<List<Integer>>{
/**
* The length of the index tuples.
*/
private final int indexTupleLength;
/**
* The length of the list for which the indices are being generated.
*/
private final int lengthOfTargetList;
/**
* The actual internal state containing the current index tuple.
*/
private final List<Integer> indices;
/**
* The number of iterated tuples.
*/
private long numberOfIteratedIndexTuples = 0L;
/**
* The total number of iterations.
*/
private long totalNumberOfIterations;
public IndexTupleIterator(final int indexTupleLength,
final int lengthOfTargetList) {
checkArguments(indexTupleLength,
lengthOfTargetList);
this.indexTupleLength = indexTupleLength;
this.lengthOfTargetList = lengthOfTargetList;
this.indices = new ArrayList<>(indexTupleLength);
initState();
}
@Override
public boolean hasNext() {
return numberOfIteratedIndexTuples < totalNumberOfIterations;
}
@Override
public List<Integer> next() {
if (!hasNext()) {
throw new NoSuchElementException("Nothing to iterate.");
}
numberOfIteratedIndexTuples++;
if (indices.get(indices.size() - 1) < lengthOfTargetList - 1) {
indices.set(indices.size() - 1,
indices.get(indices.size() - 1) + 1);
return Collections.<Integer>unmodifiableList(indices);
}
for (int i = indices.size() - 2; i >= 0; --i) {
final Integer a = indices.get(i);
final Integer b = indices.get(i + 1);
if (a < b - 1) {
indices.set(i, indices.get(i) + 1);
for (int j = i + 1; j < indices.size(); j++) {
indices.set(j, indices.get(j - 1) + 1);
}
return Collections.<Integer>unmodifiableList(indices);
}
}
throw new IllegalStateException("Should not get here.");
}
@Override
public void remove() {
throw new UnsupportedOperationException(
"remove() is not supported in IndexTupleIterator.");
}
@Override
public void forEachRemaining(Consumer<? super List<Integer>> action) {
throw new UnsupportedOperationException(
"forEachRemainig() is not supported in IndexTupleIterator.");
}
public static void main(String[] args) {
int lineNumber = 1;
for (final List<Integer> list : new IndexTupleIterable(3, 6)) {
System.out.printf("%d: %s\n", lineNumber++, list);
}
}
private void initState() {
// Create the initial index tuple <0, 1, ..., indexTupleLength - 1>:
for (int i = 0; i < indexTupleLength; ++i) {
this.indices.add(i);
}
// Compute the total number of iterations:
final long factorialN = factorial(lengthOfTargetList);
final long factorialK = factorial(indexTupleLength);
final long factorialNminusK =
factorial(lengthOfTargetList - indexTupleLength);
this.totalNumberOfIterations = factorialN
/ factorialK
/ factorialNminusK;
// We need this in order to generate the first index tuple:
this.indices.set(indexTupleLength - 1,
this.indices.get(indexTupleLength - 1) - 1);
}
/**
* Checks that the input arguments are sensible.
*
* @param indexTupleLength the length of the index tuple.
* @param lengthOfTargetList the length of the list being indexed.
*/
private static void checkArguments(final int indexTupleLength,
final int lengthOfTargetList) {
if (indexTupleLength < 1) {
final String exceptionMessage =
String.format("indexTupleLength(%d) < 1",
indexTupleLength);
throw new IllegalArgumentException(exceptionMessage);
}
if (lengthOfTargetList < 1) {
final String exceptionMessage =
String.format("lengthOfTargetList(%d) < 1",
lengthOfTargetList);
throw new IllegalArgumentException(exceptionMessage);
}
if (indexTupleLength > lengthOfTargetList) {
final String exceptionMessage =
String.format(
"indexTupleLength(%d) > lengthOfTargetList(%d)",
indexTupleLength,
lengthOfTargetList);
throw new IllegalArgumentException(exceptionMessage);
}
}
private static long factorial(final long n) {
long factorial = 1;
for (long l = 1; l <= n; ++l) {
factorial *= l;
}
return factorial;
}
}
com.github.coderodde.util.IndexTupleIterable.java:
package com.github.coderodde.util;
import java.util.Iterator;
import java.util.List;
import java.util.Spliterator;
/**
* This class provides an iterable for iterating over list index tuples.
*
* @version 1.0.0
* @since 1.0.0
*/
public final class IndexTupleIterable implements Iterable<List<Integer>> {
/**
* The length of the index tuples.
*/
private final int indexTupleLength;
/**
* The length of the list for which the indices are being generated.
*/
private final int lengthOfTargetList;
public IndexTupleIterable(final int indexTupleLength,
final int lengthOfTargetList) {
this.indexTupleLength = indexTupleLength;
this.lengthOfTargetList = lengthOfTargetList;
}
@Override
public Iterator<List<Integer>> iterator() {
return new IndexTupleIterator(indexTupleLength,
lengthOfTargetList);
}
@Override
public Spliterator<List<Integer>> spliterator() {
throw new UnsupportedOperationException(
"spliterator() is not supported in IndexTupleIterable.");
}
}
Critique request
As always, I am eager to hear any constructive criticism on my attempt.
