Array list iteration

Question

I have a setting 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 when writing code. I am trying to iterate the whole installation to create 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:

• I remember that recursion can always be replaced by loops in some lecture, but I cannot do this for this case. What will the loop version of this view look like?

• Is there a better way to solve this problem?

Answer 1

Here's a non-recursive method for outputting all combinations of array elements. This is definitely more complicated than a recursive solution. It works by storing the entry in an additional array, from which a digit was recently displayed 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 ); } } 

results

 [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, this can be done without recursion if you maintain an array, list, or something else that tells you where you are in each of the arrays.

Say we save a list of these items:

 /** * 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 look at each array, say, the array {4, 5} . We will start with four, as we go through our cycle, we will update this to five. But then the element above changes, and we need to move on to four again. This class helps us with this.

So, we compile 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; } 

It's quite simple - we just look at our list and collect lengths to help us find out when each index needs to be reset.

At each iteration, we have to go through the list and print the numbers in the current index of each array. Therefore, if we have index 2 for the first array, 1 for the second and 0 for the last, we 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 updating the indexes. This is very similar to adding 1 to the number. Imagine you have the number 1958 and you add 1 to it. He becomes 1959 . Now you add 1. again. So 9 becomes 0 , and you need to move 1 to 5. Now you have 1960 . Save it and you will get until 1999 . At this point, you add 1, zero 9, drag it to the left, then zero it and drag it to the left, then reset it and drag it to the left, and you end up in 2000 .

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

 /** * 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 a “carry” from the left-most index — an index that belongs to the head of our source list, this means that we have finished the program since we passed all the elements in the first array. When this happens, the above method returns true.

Now we only need to call our methods:

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

Answer 4

This solution WITHOUT using stacks / queues / linked list . Purely made with simple hinges. The only data structure I use is a single 1D array.

  int[] state = new int[list.size()]; int incIdx = list.size()-1; //increment index while(true){ for(int x=0; x<list.size(); x++) System.out.print(list.get(x)[state[x]); System.out.println(); state[list.size()-1]++; //last one always increase while(state[incIdx] == list.get(incIdx).length){ //replaces back tracking state[incIdx] = 0; incIdx--; if(incIdx < 0) break; //solution found, exit loop state[incIdx]++; } if(incIdx < 0) break; //solution found, exit loop incIdx = list.size()-1; if(state[list.size()-1] == list.get(list.size()-1).length) state[list.size()-1] = 0; } } 

The idea is to use a 1D array to store state. The state represented by the 1D array to determine which index of the array to print.

OUTPUT:

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

Answer 5

Is there a better way to solve this problem?

A more abstract approach:

• Add a marker at the beginning and end of the list.
• Build a grid in which each element (token or array in the list) is a level.
• Print each path through this grate.

This works because your problem can be modeled as listing all possible actions through a distributed system in which the total number of processes is equal to the length of the longest array found in the list.

Answer 6

If you mean iterating over a list of arrays, something like this will print every value inside each array:

 for(int=0; i<list.size(); i++){ for(int j=0; j<list.get(i).length; j++){ System.out.println(j); } }