Wie kann ich mithilfe eines iterativen Ansatzes in Java effizient alle Permutationen eines Arrays generieren?

Permutationsalgorithmus

Um alle Permutationen eines Arrays zu generieren, ziehen Sie einen iterativen Ansatz in Betracht, der mit dem aktuellen Array in aufsteigender Reihenfolge beginnt. Das Ziel besteht darin, es schrittweise in eine absteigende Reihenfolge umzuwandeln, indem Elemente ausgetauscht werden, die das absteigende Muster durchbrechen.

Pseudocode-Algorithmus

`
for (int tail = ind. Länge - 1; Schwanz > {

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;
}

}
`

Implementierung

Hier ist eine Beispielimplementierung in Java, die sowohl eindeutige als auch wiederholte Funktionen verarbeitet Elemente:

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
    }
}

Beispiel

Für ein Array [3, 4, 6, 2, 1] lauten die Permutationen wie folgt:

[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]

Das obige ist der detaillierte Inhalt vonWie kann ich mithilfe eines iterativen Ansatzes in Java effizient alle Permutationen eines Arrays generieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!