Permutation of Array

Generating permutations of an array is a common computational task. Given an array of distinct elements, how can we compute all possible arrangements of these elements?

Recursive Algorithm

One classic algorithm for permutation generation employs recursion. The core idea is to consider each element in the array as a potential first element, then recursively permute the remaining elements to find all possible combinations starting with that first element:

// Recursive method for permutation generation
public static void permute(int[] arr, int k) {
    for (int i = k; i < arr.length; i++) {
        // Swap elements at positions k and i
        Collections.swap(arr, k, i);
        // Recursively permute the remaining elements
        permute(arr, k + 1);
        // Restore original order of elements
        Collections.swap(arr, k, i);
    }
    if (k == arr.length - 1) {
        // Once all elements are permuted, print the current permutation
        System.out.println(Arrays.toString(arr));
    }
}

In this algorithm, the parameter k keeps track of the current position in the array. Initially, k is set to 0, indicating the first element. For each position k, it iterates through the remaining elements, swapping them with the element at position k, and recursively permuting the rest of the array starting with position k 1. This effectively considers all possible arrangements starting with each element.

Non-Recursive Algorithm for Distinct Elements

An alternative, non-recursive algorithm works well for cases where all elements in the array are distinct. It builds permutations by iteratively swapping elements to achieve a specific pattern:

for (int tail = arr.length - 1; tail > 0; tail--) {
    // Find the first decreasing element from the end
    if (arr[tail - 1] < arr[tail]) {
        // Find the last element greater than the decreasing element
        int s = arr.length - 1;
        while (arr[tail - 1] >= arr[s]) {
            s--;
        }
        // Swap the decreasing element with the greater element
        swap(arr, tail - 1, s);
        // Reverse the order of elements after the swap
        reverse(arr, tail);
        break;
    }
}

This algorithm starts with an ascending sequence of elements in the array. It scans the array from right to left, looking for the first decreasing element. Once it finds the decreasing element, it swaps it with the smallest element in the tail of the array that is greater than it. Finally, it reverses the order of the elements in the tail to obtain the next permutation.

Non-Recursive Algorithm for Same Elements

In cases where elements in the array are not distinct, using HashMap to map elements to their indices can handle potential repetitions:

// Create a HashMap to map elements to their indices
Map<E, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
    map.put(arr[i], i);
}
// Sort the array in ascending order
Arrays.sort(arr);
// Initialize the index array
int[] ind = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
    ind[i] = map.get(arr[i]);
}

With proper mapping and indexing, the same non-recursive algorithm can generate all permutations, handling repeated elements appropriately.

The above is the detailed content of How Can We Generate All Possible Permutations of an Array, Handling Both Distinct and Non-Distinct Elements?. For more information, please follow other related articles on the PHP Chinese website!