Generating permutations

Permutations.java

// I have been programming Java since 1996 at both the application and systems level.
// This seemingly elementary problem that I would fail on any junior-level interview
// gave me absolute fits.  I wanted to capture it here for the benefit of other
// dullards like me.   You are not alone.
//
// Suppose you have some number of arrays (let's say 2).  Like so:
//
//   final Object[] o0 = new Object[] { String.class, Number.class };
//   final Object[] o1 = new Object[] { Object.class };
//
// For reasons that will hopefully become clear, we'll call these "column values
// arrays."  They are arrays that hold potential values that could go in a 
// column of a row whose length is equal to the number of these arrays.
//
// Let's say given that you now need a series of permutations that are:
//
//   { String.class, Object.class }
//   { Number.class, Object.class }
//
// Each of these is a permutation (a combination with order).  If you know the number
// of "columns" in each permutation "row" in advance, you can, of course, just do this
// with an appropriate number of nested loops.  Doing this for an arbitrary number of
// columns is what stumped me for a long time.  I knew I needed recursion but had a 
// lot of trouble coming up with the recipe.
// 
// This method recursively generates the permutations you need.  You pass it a
// resultAdder, which, when given a "row", ultimately ends up adding it (whatever that
// might mean; usually you'd probably pass someCollection::add here).  You pass it a
// columnValuesGetter which will give you o0 when supplied with 0 and o1 when supplied
// with 1 (in the example above).  You pass it a non-null "row", which will be used and
// mutated as this method progresses (you should toss it away afterwards).  The row's
// length should be equal to the number of columnValues arrays that could be returned by
// columnValuesGetter (so 2 in the example above).  You pass a rowCloner, which is
// responsible for taking the row and cloning it or otherwise copying it (r -> r.clone(),
// for example).  Finally you pass 0 to start; this is the index of the column the method
// will begin work on.
//
// So you could do this:
// 
//   final List<Type[]> columnValuesList = List.of(o0, o1); // size() is number of columns in a row
//   final List<Type[]> result = new ArrayList<>();
//   permutations(result::add, columnValuesList::get, new Type[columnValuesList.size()], r -> r.clone(), 0);
//   // result will now have the permutations in it
public static final <T> void permutations(final Consumer<? super T[]> resultAdder,
                                          final IntFunction<? extends T[]> columnValuesGetter,
                                          final T[] row, // mutated and reused
                                          final UnaryOperator<T[]> rowCloner,
                                          final int columnIndex) {
  if (columnIndex < row.length) {
    for (final T columnValue : columnValuesGetter.apply(columnIndex)) {
      row[columnIndex] = columnValue;
      permutations(resultAdder, columnValuesGetter, row, rowCloner, columnIndex + 1); // NOTE: recursive
    }
  } else {
    final T[] clonedRow = rowCloner.apply(row);
    assert clonedRow != row;
    assert clonedRow.length == row.length;
    resultAdder.accept(clonedRow);
  }
}