An iterator returning all possible permutations of a list in Java

Your solution looks good. It's a really challenging task. This is because you have to "flatten" an algorithm with recursive nature. Furthermore you have to break it apart into single steps and to be able to resume at the last step made.

So there are little things that I would change:

1. I like separated classes instead of inner classes they are more handy in testing
2. I would have separated the algorithm in "generateNextPermutation()" in an additional class.
3. I would follow the recursive nature of the problem and build a recursive structure. This is a slightly different approach.
4. I do not exactly know how the algorithm should behave if you provide an empty list. I assume that you will have one permutation as result. So I adapted your algorithm to work with an empty array of indices.

You see that our solutions do not differ in structure. Only the algorithm to generate a new permutation is extracted in a class and reformulated.

I unpacked this riddle (I somehow liked this riddle) and I want to provide a solution that can use either your algorithm or mine. But finally they converged against the same interface. I expected that as I know there is only one structure that fits the problem best. We may not have found it but both solutions have a "meeting" where the structure is mostly the same AND the things that may be different can work under the same abstraction. Sure, most structure was provided by the interfaces "Iterable" and "Iterator" but I found it interesting how the algorithms are interchangeable.

So first of all the interface for our algorithms:

public interface PermutationResolver<T> {

    List<T> resolvePermutation(List<T> base);

    boolean nextStep();

}

Your algorithm:

public class IndicesWalker<T> implements PermutationResolver<T> {

    private int[] indices;

    public IndicesWalker(int elements) {
        indices = new int[elements];
        for (int i = 0; i < indices.length; ++i) {
            indices[i] = i;
        }
    }

    @Override
    public boolean nextStep() {

        if (indices.length == 0) return false;

        int i = indices.length - 2;

        while (i >= 0 && indices[i] > indices[i + 1]) {
            --i;
        }

        if (i == -1) {
            // No more new permutations.
            return false;
        }

        int j = i + 1;
        int min = indices[j];
        int minIndex = j;

        while (j < indices.length) {
            if (indices[i] < indices[j] && indices[j] < min) {
                min = indices[j];
                minIndex = j;
            }

            ++j;
        }

        swap(indices, i, minIndex);

        ++i;
        j = indices.length - 1;

        while (i < j) {
            swap(indices, i++, j--);
        }
        return true;
    }

    @Override
    public List<T> resolvePermutation(List<T> base) {

        List<T> newPermutation = new ArrayList<>(indices.length);

        for (int i : indices) {
            newPermutation.add(base.get(i));
        }

        return newPermutation;
    }

    private void swap(int[] array, int a, int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

}

Mine:

public class RecursiveCounter<T> implements PermutationResolver<T> {

    private int i;
    private int max;
    private RecursiveCounter<T> nextState;

    public RecursiveCounter(int max) {
        this.max = max;
        this.i = 0;
        if (this.max > 1) {
            nextState = new RecursiveCounter<T>(max - 1);
        }
    }

    @Override
    public boolean nextStep() {

        boolean wasIncremented = true;

        if (nextState != null) {
            if (!nextState.nextStep()) {
                if (this.i == this.max - 1) {
                    this.i = 0;
                    wasIncremented = false;
                } else {
                    i++;
                }
            }
        } else {
            wasIncremented = false;
        }

        return wasIncremented;
    }


    private int getI(int level) {
        if (level == 0) {
            return this.i;
        } else {
            return nextState.getI(level - 1);
        }
    }

    @Override
    public List<T> resolvePermutation(List<T> base) {
        List<T> result = new ArrayList<>();
        List<T> work = new ArrayList<>(base);
        for(int i = 0; i < base.size(); i++) {
            result.add(work.remove(getI(i)));
        }
        return result;
    }


}

The iterator:

public class PermutationIterator<T> implements Iterator<List<T>>  {

    private List<T> base;

    private PermutationResolver<T> permutationResolver;
    private List<T> next;

    public PermutationIterator(List<T> base, PermutationResolver<T> resolver) {
        this.base = base;
        this.next = new ArrayList<>(base);
        this.permutationResolver = resolver;
    }

    private List<T> generateNextPermutation(boolean isLast) {

        List<T> result = null;

        if (!isLast) {
            result = getPermutationResolver().resolvePermutation(base);
        }

        return result;
    }

    @Override
    public boolean hasNext() {
        return next != null;
    }

    @Override
    public List<T> next() {

        if (!hasNext()) {
            throw new NoSuchElementException();
        }

        List<T> current = next;

        this.next = generateNextPermutation(!getPermutationResolver().nextStep());

        return current;
    }


    private PermutationResolver<T> getPermutationResolver() {
        return permutationResolver;
    }

}

The iterable:

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

    private List<T> base;
    private PermutationResolver<T> resolver;

    public PermutationIterable(List<T> base, PermutationResolver<T> resolver) {
        super();
        this.base = base;
        this.resolver = resolver;
    }

    @Override
    public Iterator<List<T>> iterator() {
        return new PermutationIterator<T>(base, resolver);
    }

}

Code in action with both algorithms:

public class Main {

    public static void main(String[] args) {

        List<String> base = Arrays.asList();

        PermutationIterable<String> permutationIterable1 = new PermutationIterable<String>(base, new IndicesWalker<String>(base.size()));

        for (List<String> permutation : permutationIterable1) {
            System.out.println(permutation);
        }

        PermutationIterable<String> permutationIterable2 = new PermutationIterable<String>(base, new RecursiveCounter<String>(base.size()));

        for (List<String> permutation : permutationIterable2) {
            System.out.println(permutation);
        }

    }

}