Wie generiert man alle eindeutigen Permutationen eines Arrays, einschließlich der Behandlung wiederholter Elemente?

Permutation eines Arrays

Permutationen eines Arrays sind alle möglichen Möglichkeiten, die Elemente des Arrays in einer anderen Reihenfolge anzuordnen. Beispielsweise weist das Array [1, 2, 3] die folgenden Permutationen auf:

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

Es gibt mehrere Algorithmen, um Permutationen eines Arrays zu generieren. Einer der gebräuchlichsten Algorithmen ist ein rekursiver Algorithmus, der alle Permutationen eines kleineren Arrays generiert, indem er das neue Element am Ende jeder Permutation des kleineren Arrays hinzufügt.

Hier ist eine Implementierung des rekursiven Algorithmus in Java :

import java.util.List;

public class Permute {

    public static void main(String[] args) {
        int[] a = new int[]{3, 4, 6, 2, 1};
        permute(a, 0);
    }

    static void permute(int[] a, int k) {
        for (int i = k; i < a.length; i++) {
            java.util.Collections.swap(a, i, k);
            permute(a, k + 1);
            java.util.Collections.swap(a, i, k);
        }
        if (k == a.length - 1) {
            System.out.println(java.util.Arrays.toString(a));
        }
    }
}

Der obige Code gibt alle Permutationen des Arrays a bis the aus Konsole.

Verarbeitung wiederholter Elemente

Der obige rekursive Algorithmus verarbeitet wiederholte Elemente nicht korrekt. Wenn das Array a beispielsweise wiederholte Elemente enthält, generiert der Algorithmus doppelte Permutationen.

Um wiederholte Elemente zu verarbeiten, können wir einen anderen Algorithmus namens Heap-Algorithmus verwenden. Der Heap-Algorithmus generiert alle Permutationen eines Arrays, indem zwei Elemente des Arrays iterativ ausgetauscht werden.

Hier ist eine Implementierung des Heap-Algorithmus in Java:

import java.util.List;

public class Permute {

    public static void main(String[] args) {
        int[] a = new int[]{3, 3, 4, 4, 6, 2, 1};
        permute(a, 0);
    }

    static void permute(int[] a, int k) {
        if (k == a.length - 1) {
            System.out.println(java.util.Arrays.toString(a));
        } else {
            for (int i = k; i < a.length; i++) {
                if (i == k || a[i] != a[k]) {
                    java.util.Collections.swap(a, i, k);
                    permute(a, k + 1);
                    java.util.Collections.swap(a, i, k);
                }
            }
        }
    }
}

Der obige Code druckt alle eindeutigen Permutationen des Arrays a an die Konsole.

Das obige ist der detaillierte Inhalt vonWie generiert man alle eindeutigen Permutationen eines Arrays, einschließlich der Behandlung wiederholter Elemente?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!