How to Implement a Non-Recursive Permutation Algorithm in Java?

Question

What is a non-recursive way to generate permutations in Java?

public static List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Stack<List<Integer>> stack = new Stack<>();
    stack.push(new ArrayList<>());
    boolean[] used = new boolean[nums.length];

    while (!stack.isEmpty()) {
        List<Integer> current = stack.pop();

        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            continue;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.add(nums[i]);
            stack.push(new ArrayList<>(current));
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }
    return result;
}

Answer

Generating permutations without recursion can be achieved using an iterative approach. This method leverages a stack data structure to maintain the current state of permutations as we explore possible combinations in a controlled manner.

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Permutations {
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Stack<List<Integer>> stack = new Stack<>();
        stack.push(new ArrayList<>());
        boolean[] used = new boolean[nums.length];

        while (!stack.isEmpty()) {
            List<Integer> current = stack.pop();

            if (current.size() == nums.length) {
                result.add(new ArrayList<>(current));
                continue;
            }

            for (int i = 0; i < nums.length; i++) {
                if (used[i]) continue;
                used[i] = true;
                current.add(nums[i]);
                stack.push(new ArrayList<>(current));
                current.remove(current.size() - 1);
                used[i] = false;
            }
        }
        return result;
    }
}

Causes

Need for efficient memory management without the overhead of recursion.
Preference for iterative methods in certain programming scenarios.

Solutions

Utilize a stack to emulate the call stack used in recursive methods.
Maintain a boolean array to track which elements are currently used in the permutation.

Common Mistakes

Mistake: Not properly managing the 'used' state, causing duplicates in results.

Solution: Ensure to reset used[i] to false after backtracking.

Mistake: Attempting to use stack.push(current) without creating a new list causes reference issues.

Solution: Always instantiate a new ArrayList for stack entries.

Helpers

Java non-recursive permutation
iterative permutation algorithm Java
Java permutations without recursion
generate permutations Java