Java recursive combine function to iterative equivalent

Question

I have recursive combining function:

static void combinations2(String[] arr, int len, int startPosition, String[] result) {

    if (len == 0) {
        for (String n : result) {
            System.out.print(n + "  \n");

        }

        return;
    }

    for (int i = startPosition; i <= arr.length - len; i++) {
        result[result.length - len] = arr[i];
        combinations2(arr, len - 1, i + 1, result);
    }
}

Input:

 arr = {"Item 1", "Item 2", "Item 3", "Item 4", "Item 5"} - input array e.g.
 len = 3 - length of each combination
 startPosition = 0
 result - result of each combination

Output:

Item 1  
Item 2  
Item 3  

Item 1  
Item 2  
Item 4  

Item 1  
Item 2  
Item 5  

Item 1  
Item 3  
Item 4  

Item 1  
Item 3  
Item 5  

Item 1  
Item 4  
Item 5  

Item 2  
Item 3  
Item 4  

Item 2  
Item 3  
Item 5  

Item 2  
Item 4  
Item 5  

Item 3  
Item 4  
Item 5 

What i should do to change it to iterative alternative? I read about stacks and i wrote couple of lines.. but what about return function? How to hande it?

I did somthing like this:

static void combinations2(String[] arr, int len, int startPosition, String[] result) {
        Stack<Integer> stos = new Stack<>();
        stos.push(startPosition);
        stos.push(len);

        int i = 0;
        while (!stos.isEmpty()) {
            len = stos.pop();
            startPosition = stos.pop();

            if (len == 0) {
                for (String n : result) {
                    System.out.print(n + "  \n");
                }            

                System.out.println("    ");
                stos.push(startPosition);
                stos.push(len+1);
            } else {

                for (i = startPosition; i <= arr.length - len; i++) {
                    result[result.length - len] = arr[i];

                    //combinations2(arr, len - 1, i + 1, result);
                    stos.push(i + 1);
                    stos.push(len - 1);
                    break;

                }
            }  
        }
    }

And i've got output:

Item 1  
Item 2  
Item 3  

Item 1  
Item 2  
Item 4  

Item 1  
Item 2  
Item 5 

Someone could show me the way, to generate next steps?

Answer 1

The following class is an Iterable which returns combinations. See the main method for the use. Run the main method to test.

Combinations are created lazily, as such reading first 100 combinations of 10 elements from pool of 10000000 will not be slow.

This class also short circuits any exploration of impossible scenarios i.e. for combitions of 3 out of 5 elements, it is pointless to place 4th element in first position, as that will lead to 5th element in second position, and no element left for the last position.

Generally iterative versions of recursive algorithms use a stack to simulate variable passing to the same function.

public class Combinations<T> implements Iterable<List<T>> {

    private final List<T> items;
    private final int size;

    public static <T> Combinations<T> of(List<T> items, int size) {
        return new Combinations<T>(items, size);
    }

    private Combinations(List<T> items, int size) {
        if (items.size() < size) throw new IllegalArgumentException();
        this.items =  items;
        this.size = size;
    }

    public Iterator<List<T>> iterator() {
        return new Iterator<List<T>>() {        
            private final int[] positions = new int[size];              
            private boolean more = true;
            {
                for(int i = 0;i < positions.length;i++) {
                    positions[i] = i;
                }
            }

            public boolean hasNext() {
                return more;
            }

            public List<T> next() {
                if (!more) throw new NoSuchElementException();
                List<T> ret = new ArrayList<T>();
                for (int i = 0;i < positions.length;i++) {
                    ret.add(items.get(positions[i]));
                }
                int advanceIdx = positions.length - 1;
                while(advanceIdx > -1) {
                    if (positions[advanceIdx] == items.size() - size + advanceIdx) {
                        advanceIdx--;
                    } else {
                        positions[advanceIdx]++;
                        for (int i = 1;i + advanceIdx < positions.length;i++) {
                            positions[advanceIdx+i] = positions[advanceIdx] + i; 
                        }
                        return ret;
                    }
                }
                more = false;
                return ret;
            }

            public void remove() {
                throw new UnsupportedOperationException();
            }

        };
    }

    public static void main(String[] args) {
        for(List<String> s : Combinations.of(Arrays.asList("A", "B", "C", "D", "E"), 3)) {
            System.out.println(s);
        }
    }
}