Wie kann ich mithilfe eines rekursiven Ansatzes alle möglichen Permutationen eines Arrays eindeutiger Ganzzahlen generieren?

Permutationen eines Arrays generieren

Das Problem verstehen

Wir erhalten ein Array eindeutiger Ganzzahlen und werden gebeten, alle möglichen Permutationen zu generieren. Zwei Permutationen gelten als unterschiedlich, wenn sie sich in der Reihenfolge der Elemente unterscheiden. Für ein Array der Länge n gibt es n! mögliche Permutationen.

Ansatz: Rekursive Permutation

Die Lösung umfasst zwei Hauptschritte:

1. Rekursion: Nehmen Sie nacheinander jedes Element des Arrays und die verbleibenden Elemente permutieren.
2. Austauschen: Tauschen Sie das aktuelle Element mit Elementen aus dem verbleibenden Teil aus, um neue Permutationen zu erstellen.

Mit diesem Ansatz können wir Generieren Sie alle Permutationen.

Code-Implementierung

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

public class Permutation {

    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        permute(nums, 0, result);
        return result;
    }

    private static void permute(int[] nums, int startIndex, List<List<Integer>> result) {
        if (startIndex == nums.length - 1) {
            // Base case: If we reach the end of the array, add the current permutation to the result.
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) {
                permutation.add(num);
            }
            result.add(permutation);
        } else {
            // Recursive case: Permute the remaining elements for each element at the current index.
            for (int i = startIndex; i < nums.length; i++) {
                swap(nums, startIndex, i);
                permute(nums, startIndex + 1, result);
                swap(nums, startIndex, i);
            }
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Beispiel Verwendung

int[] nums = {3, 4, 6, 2, 1};
List<List<Integer>> permutations = Permutation.permute(nums);
for (List<Integer> permutation : permutations) {
    System.out.println(permutation);
}

Ausgabe:

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

Das obige ist der detaillierte Inhalt vonWie kann ich mithilfe eines rekursiven Ansatzes alle möglichen Permutationen eines Arrays eindeutiger Ganzzahlen generieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!