Java高效Permutation Iterator实现需求：优化低速迭代器

Hey there, let's fix that slow permutation iterator! The most common culprits behind poor performance here are usually unnecessary object churn, recursive generation that creates all permutations upfront, or naive array copying. Below are targeted optimizations with concrete code examples to get your iterator running much faster.

Key Optimizations & Implementation #

1. Use Lazy, Iterative Permutation Generation (No Precomputation) #

Instead of generating all permutations at once and storing them (which eats up memory and slows initialization), we'll generate each permutation on-demand when next() is called. Two efficient iterative algorithms work perfectly here:

Option A: Heap's Algorithm (Fastest, Non-Dictionary Order)

Heap's Algorithm generates permutations by swapping elements in-place, with amortized O(1) time per permutation. It uses minimal extra state and avoids recursion overhead.

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Permulator implements Iterator<int[]> {
    private final int n;
    private final int[] currentPerm;
    private final int[] swapTracker;
    private boolean hasNextPerm;

    public Permulator(int n) {
        if (n <= 0) throw new IllegalArgumentException("n must be a positive integer");
        this.n = n;
        this.currentPerm = new int[n];
        for (int i = 0; i < n; i++) currentPerm[i] = i;
        this.swapTracker = new int[n];
        this.hasNextPerm = true;
    }

    @Override
    public boolean hasNext() {
        return hasNextPerm;
    }

    @Override
    public int[] next() {
        if (!hasNextPerm) throw new NoSuchElementException();

        // Return a copy of the current valid permutation
        int[] result = currentPerm.clone();

        // Generate next permutation via Heap's Algorithm
        int i = 0;
        while (i < n) {
            if (swapTracker[i] < i) {
                // Swap based on even/odd index
                if (i % 2 == 0) swap(currentPerm, 0, i);
                else swap(currentPerm, swapTracker[i], i);
                swapTracker[i]++;
                return result;
            } else {
                swapTracker[i] = 0;
                i++;
            }
        }

        // No more permutations left
        hasNextPerm = false;
        return result;
    }

    private void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

Option B: Next Permutation (Dictionary Order, Matches Your Example)

If you need permutations in lexicographical order (like your example: [0,1,2] → [0,2,1] → ...), use the "next permutation" algorithm. It's also iterative and in-place:

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Permulator implements Iterator<int[]> {
    private final int n;
    private final int[] currentPerm;
    private boolean hasNextPerm;

    public Permulator(int n) {
        if (n <= 0) throw new IllegalArgumentException("n must be a positive integer");
        this.n = n;
        this.currentPerm = new int[n];
        for (int i = 0; i < n; i++) currentPerm[i] = i;
        this.hasNextPerm = true;
    }

    @Override
    public boolean hasNext() {
        return hasNextPerm;
    }

    @Override
    public int[] next() {
        if (!hasNextPerm) throw new NoSuchElementException();

        int[] result = currentPerm.clone();

        // Step 1: Find the largest k where currentPerm[k] < currentPerm[k+1]
        int k = n - 2;
        while (k >= 0 && currentPerm[k] >= currentPerm[k+1]) k--;

        if (k == -1) {
            // No more permutations
            hasNextPerm = false;
            return result;
        }

        // Step 2: Find largest l > k where currentPerm[k] < currentPerm[l]
        int l = n - 1;
        while (currentPerm[l] <= currentPerm[k]) l--;

        // Step 3: Swap k and l
        swap(currentPerm, k, l);

        // Step 4: Reverse from k+1 to end
        reverse(currentPerm, k+1, n-1);

        return result;
    }

    private void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    private void reverse(int[] arr, int start, int end) {
        while (start < end) {
            swap(arr, start, end);
            start++;
            end--;
        }
    }
}

2. Minimize Object Overhead #

• Reuse internal arrays: Both implementations maintain a single currentPerm array that's modified in-place. We only clone it when returning the result to avoid exposing mutable state to the caller.
• Use primitive arrays: int[] is far faster than Integer[] or List<Integer> because it avoids autoboxing/unboxing and has lower memory overhead. If you need a List<Integer>, you can convert the array once per next() call, but keep the internal state as int[].

3. Avoid Unnecessary Operations #

• Skip recursive calls: Recursive permutation generation often leads to stack overhead and precomputing all permutations at once, which is terrible for memory and initialization time.
• Avoid redundant copies: Only copy the array when you need to return it to the caller—never copy during permutation generation itself.

Performance Impact #

Both implementations will drastically outperform naive approaches:

• Initialization is O(n) time (just setting up the starting array and tracker state).
• Each next() call runs in amortized O(1) time (Heap's) or O(n) worst-case time (Next Permutation, but average case is still fast for most use cases).
• Memory usage is O(n) (only storing the current permutation and small tracker state), instead of O(n*n!) for precomputed permutations.

内容的提问来源于stack exchange，提问作者Alto Lagato