Comment puis-je générer toutes les permutations possibles d'un tableau d'entiers uniques en utilisant une approche récursive ?

Générer des permutations d'un tableau

Comprendre le problème

On nous donne un tableau d'entiers uniques et on nous demande de générer toutes les permutations possibles. Deux permutations sont considérées comme différentes si elles diffèrent dans l'ordre des éléments. Pour un tableau de longueur n, il y a n! permutations possibles.

Approche : Permutation récursive

La solution comporte deux étapes principales :

1. Récursion : Prenez chaque élément du tableau dans tourner et permuter les éléments restants.
2. Échange : Échangez l'élément actuel avec des éléments de la partie restante pour créer de nouvelles permutations.

En utilisant cette approche, nous peut générer toutes les permutations.

Implémentation du code

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

Exemple Utilisation

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

Sortie :

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!