How can I efficiently generate all permutations of an array using an iterative approach in Java?

Permutation Algorithm

To generate all permutations of an array, consider an iterative approach that starts with the current array in ascending order. The goal is to gradually transform it into descending order by swapping elements that break the descending pattern.

Pseudocode Algorithm

`
for (int tail = ind.length - 1; tail > 0; tail--) {

if (ind[tail - 1] < ind[tail]) { // still increasing

    // find last element that does not exceed ind[tail - 1]
    int s = ind.length - 1;
    while (ind[tail - 1] >= ind[s])
        s--;

    swap(ind, tail - 1, s);

    // reverse order of elements in the tail
    for (int i = tail, j = ind.length - 1; i < j; i++, j--)
        swap(ind, i, j);
    break;
}

}
`

Implementation

Here's an example implementation in Java that handles both distinct and repeated elements:

import java.util.Arrays;
import java.util.Iterator;
import java.lang.reflect.Array;

class Permutations<E> implements Iterator<E[]> {

    private E[] arr;
    private int[] ind;
    private boolean has_next;

    public E[] output; // next() returns this array

    Permutations(E[] arr) {
        this.arr = arr.clone();
        ind = new int[arr.length];

        // convert an array of any elements into an array of integers
        Map<E, Integer> hm = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            Integer n = hm.get(arr[i]);
            if (n == null) {
                hm.put(arr[i], i);
                n = i;
            }
            ind[i] = n.intValue();
        }
        Arrays.sort(ind); // start with ascending sequence of integers

        output = (E[]) Array.newInstance(arr.getClass().getComponentType(), arr.length);
        has_next = true;
    }

    public boolean hasNext() {
        return has_next;
    }

    public E[] next() {
        if (!has_next) {
            throw new NoSuchElementException();
        }

        for (int i = 0; i < ind.length; i++) {
            output[i] = arr[ind[i]];
        }

        // get next permutation
        has_next = false;
        for (int tail = ind.length - 1; tail > 0; tail--) {
            if (ind[tail - 1] < ind[tail]) { // still increasing

                // find last element that does not exceed ind[tail - 1]
                int s = ind.length - 1;
                while (ind[tail - 1] >= ind[s]) {
                    s--;
                }

                swap(ind, tail - 1, s);

                // reverse order of elements in the tail
                for (int i = tail, j = ind.length - 1; i < j; i++, j--) {
                    swap(ind, i, j);
                }

                has_next = true;
                break;
            }
        }

        return output;
    }

    private void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public void remove() {
        // not supported
    }
}

Example

For an array [3, 4, 6, 2, 1], the permutations are as follows:

[3, 2, 1, 4, 6]
[3, 2, 1, 6, 4]
[3, 2, 4, 1, 6]
[3, 2, 4, 6, 1]
[3, 2, 6, 1, 4]
[3, 2, 6, 4, 1]
[3, 4, 1, 2, 6]
[3, 4, 1, 6, 2]
[3, 4, 2, 1, 6]
[3, 4, 2, 6, 1]
[3, 4, 6, 1, 2]
[3, 4, 6, 2, 1]
[3, 6, 1, 2, 4]
[3, 6, 1, 4, 2]
[3, 6, 2, 1, 4]
[3, 6, 2, 4, 1]
[3, 6, 4, 1, 2]
[3, 6, 4, 2, 1]
[4, 2, 1, 3, 6]
[4, 2, 1, 6, 3]
[4, 2, 3, 1, 6]
[4, 2, 3, 6, 1]
[4, 2, 6, 1, 3]
[4, 2, 6, 3, 1]
[4, 3, 1, 2, 6]
[4, 3, 1, 6, 2]
[4, 3, 2, 1, 6]
[4, 3, 2, 6, 1]
[4, 3, 6, 1, 2]
[4, 3, 6, 2, 1]
[4, 6, 1, 2, 3]
[4, 6, 1, 3, 2]
[4, 6, 2, 1, 3]
[4, 6, 2, 3, 1]
[4, 6, 3, 1, 2]
[4, 6, 3, 2, 1]
[6, 2, 1, 3, 4]
[6, 2, 1, 4, 3]
[6, 2, 3, 1, 4]
[6, 2, 3, 4, 1]
[6, 2, 4, 1, 3]
[6, 2, 4, 3, 1]
[6, 3, 1, 2, 4]
[6, 3, 1, 4, 2]
[6, 3, 2, 1, 4]
[6, 3, 2, 4, 1]
[6, 3, 4, 1, 2]
[6, 3, 4, 2, 1]
[6, 4, 1, 2, 3]
[6, 4, 1, 3, 2]
[6, 4, 2, 1, 3]
[6, 4, 2, 3, 1]
[6, 4, 3, 1, 2]
[6, 4, 3, 2, 1]

The above is the detailed content of How can I efficiently generate all permutations of an array using an iterative approach in Java?. For more information, please follow other related articles on the PHP Chinese website!