Iterating over list of arrays

Question

I have a setup that looks like this:

List<int[]> list = new LinkedList<int[]>();
list.add(new int[] {1, 3, 4});
list.add(new int[] {4, 5});
list.add(new int[] {1, 4, 6});

I do not know the size of the arrays while writing the code. I am trying to iterate through the whole setup to generate all possible combinations:

141
144
146
151
154
156
341
...

I am currently using recursion to achieve this:

public static void recursive(List<int[]> list) {
    recursive(list, 0, "");
}

private static void recursive(List<int[]> list, int counter, String string)  {
    if (counter == list.size())
        System.out.println(string);
    else
        for (int i: list.get(counter))
            recursive(list, counter + 1, string + i);
}

I have 2 questions about this:

1. I remember hearing the recursion can always be replaced by loops in some lecture, but I can't do it for this case. How would a loop version of this look?

2. Is there a better way to solve this problem?

Answer 1

Here's a non-recursive method to output all combinations of array elements. It's definitely more complex than the recursive solution. It works by keeping a record in a supplementary array of which digit has recently been output in each array in the list.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Iter {

    public static void main(String[] args) {
        List<int[]> list = new LinkedList<int[]>();
        list.add(new int[] { 1, 3, 4 });
        list.add(new int[] { 4, 5 });
        list.add(new int[] { 1, 4, 6 });

        iter(list);
    }

    private static void iter(List<int[]> list) {
        int[] index = new int[list.size()];
        Arrays.fill(index, 0);
        boolean done = false;

        do {
            // Output digits for this row
            for (int i = 0; i < list.size(); i++) {
                System.out.print(list.get(i)[index[i]]);
            }
            System.out.println();

            // Rollover digits, starting from last
            for (int j = list.size() - 1; j >= 0; j--) {
                index[j] = (index[j] + 1) % list.get(j).length;
                if (index[j] > 0) break;
                if (j == 0) done = true;
            }
        } while (!done);
    }

}

Outputs:

141
144
146
151
154
156
341
344
346
351
354
356
441
444
446
451
454
456

Answer 2

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class Test {
    public static <T> void combinations( final List<T[]> listOfArrays ){
        // Can't iterate a vanilla array so this is just a container for the
        // input converted to something Iterable.
        final ArrayList<List<T>> listOfIterables = new ArrayList<>();

        // Stack containing iterators indicating the current position within
        // the combination.
        final Stack<Iterator<T>> iterators = new Stack<>();

        // The current combination to output.
        final LinkedList<T> values = new LinkedList<>();

        final int len = listOfArrays.size();

        // Initialise the previous lists.
        for ( final T[] ts : listOfArrays ) {
            final List<T> l = Arrays.asList( ts );
            final Iterator<T> i = l.iterator();
            listOfIterables.add( l );
            iterators.push( i );
            values.addLast( i.next() );
        }

        while( true ){
            System.out.println( values );
            // Pop iterators that have finished and their corresponsing values.
            int i = len;
            while ( !iterators.isEmpty() && !iterators.peek().hasNext() ){
                iterators.pop();
                values.removeLast();
                i--;
            }
            // If all iterators are finished then we're done.
            if ( iterators.isEmpty() )
                return;
            // Increment to the next value in the combination.
            values.removeLast();
            values.add( iterators.peek().next() );
            // If iteraters were finished then replace them in the stack with
            // refreshed iterators.
            for ( ; i < len; i++ ){
                final Iterator<T> iterator = listOfIterables.get( i ).iterator();
                iterators.push( iterator );
                values.addLast( iterator.next() );
            }
        }
    }

    public static void main( String[] args ){
        List<Integer[]> list = new LinkedList<>();
        list.add( new Integer[]{ 1, 3, 4 } );
        list.add( new Integer[]{ 4, 5 } );
        list.add( new Integer[]{ 1, 4, 6 } );

        combinations( list );
    }
}

Outputs

[1, 4, 1]
[1, 4, 4]
[1, 4, 6]
[1, 5, 1]
[1, 5, 4]
[1, 5, 6]
[3, 4, 1]
[3, 4, 4]
[3, 4, 6]
[3, 5, 1]
[3, 5, 4]
[3, 5, 6]
[4, 4, 1]
[4, 4, 4]
[4, 4, 6]
[4, 5, 1]
[4, 5, 4]
[4, 5, 6]

Answer 3

Well, it can be done without recursion, if you maintain an array, a list or anything else that tells you where you are in each of the arrays.

Let's say we keep a list of elements like this:

/**
 * Class to contain an index and a length. 
 */
private static class Pair {
    private int currIndex = 0;
    int length;

    /**
     * Constructor - we pass the length of the respective array.
     * This does not change during the lifetime of this program.
     * @param length The length of the respective array.
     */
    public Pair( int length ) {
        this.length = length;
    }

    /**
     * Increment the index by one. If we reach the length, start
     * from zero, and indicate that there is carry. That is, that
     * the next element will need to be updated.
     * @return True if next index down needs to be updated.
     */
    public boolean updateAndCheckCarry() {
        currIndex ++;
        if ( currIndex >= length ) {
            currIndex = 0;
            return true;
        }
        return false;
    }

    /**
     * Getter for the index itself
     * @return The current index.
     */
    public int getIndex() {
        return currIndex;
    }
}

The idea is that we go through each array, say, the {4, 5} array. We start with the four, as we will go through our loop, we'll update that to the five. But then the element above changes, and we need to go to the four again. This class helps us do that.

So we prepare our list of indices:

/**
 * Prepare an index list, which for each element of the original list,
 * will contain a current index and the limit. This allows us to keep
 * track of which element we are in in every array.
 * 
 * @param listToIndex
 * @return The index list
 */
public static LinkedList<Pair> prepareIndexList(List<int[]> listToIndex) {
    LinkedList<Pair> result = new LinkedList<>();

    for ( int[] element : listToIndex ) {
        Pair item = new Pair(element.length);
        result.add(item);
    }
    return result;
}

This is fairly simple - we just go through our list and collect the lengths to help us later be able to know when to zero out each index.

In each iteration, we are supposed to go through the list and print the numbers in the current index of each array. So if we have an index of 2 for the first array, 1 for the second and 0 for the last, we'll collect 4, 5 and 1 from your example.

/**
 * Get the current value to print from the list. That is, go through the
 * list and collect the appropriate element from each array, into a string.
 * 
 * @param valuesList The list of integer arrays to go through
 * @param indexList  The list of current indices
 * @return String representing the collected current value.
 */
public static String getNextValue(List<int[]> valuesList, List<Pair> indexList) {
    StringBuilder sb = new StringBuilder(valuesList.size());
    Iterator<Pair> indexIter = indexList.iterator();
    for ( int[] element : valuesList ) {
        int index = indexIter.next().getIndex();
        sb.append(element[index]);
    }
    return sb.toString();
}

Now, the real "meat" of this solution is the update of the indexes. It's pretty much like adding 1 to a number. Imagine you have the number 1958 and you add 1 to it. It becomes 1959. Now you add 1 again. So, the 9 becomes 0, and you need to carry the 1 to the 5. You now have 1960. Keep this up and you'll get up to 1999. At this point, you add 1, zero the 9, carry to the left, then zero it too, and carry to the left, then zero it to, and carry to the left, and you get to 2000.

In the same way - starting from the right and going through the left when we need to carry the 1 - we also update our list of indexes:

/**
 * Update the index list. Starting from the end and going backwards, we
 * increment each index. Each index is zeroed if it gets past the respective
 * array size, and also returns true to indicate that the next level needs
 * to be updated as well.
 * 
 * @param indexList The list of indices to be updated
 * @return true if the updates bubbled all the way to the first element,
 *         and it, too, was zeroed. This means we have completed printing
 *         the tree.
 */
public static boolean updateIndexList(LinkedList<Pair> indexList) {
    Iterator<Pair> iter = indexList.descendingIterator();
    boolean hasCarry = true;

    while ( iter.hasNext() && hasCarry ) {
        hasCarry =  iter.next().updateAndCheckCarry();
    }

    return hasCarry;
}

If we have "carry" from the leftmost index - the index that belongs to the head of our original list - it means that we have finished the program, as we have gone through all the elements in the first array. When this happens, the above method returns true.

Now all we need is to call our methods:

    LinkedList indexList = prepareIndexList(list);
    boolean completed = false;

    while ( ! completed ) {
        System.out.println(getNextValue( list, indexList  ));
        completed = updateIndexList(indexList);
    }