How Can I Generate All Permutations of an Array Using Recursive and Non-Recursive Algorithms?

Permutation of Array: An In-Depth Explanation

To generate permutations of an array, it's crucial to understand how the elements are arranged. A permutation involves rearranging the array elements to create new sequences. The number of possible permutations for an array with n elements is given by n!.

Recursive Algorithm

One way to generate permutations is using a recursive approach, where you iteratively swap elements and apply permutations on the remaining array elements.

public static void permute(java.util.List<Integer> arr, int k) {
    for (int i = k; i < arr.size(); i++) {
        java.util.Collections.swap(arr, i, k);
        permute(arr, k + 1);
        java.util.Collections.swap(arr, k, i);
    }
    if (k == arr.size() - 1) {
        System.out.println(java.util.Arrays.toString(arr.toArray()));
    }
}

This algorithm starts by exchanging the first element with each of the remaining elements. Then, it recursively applies the same operation on the remaining elements. After each recursive call, the elements are swapped back to their original positions.

Non-Recursive Algorithm

For an iterative approach, consider the following steps:

1. Start with the array sorted in ascending order.
2. Find the first index where the sequence fails to be descending (i.e., where a[i] < a[i-1]).
3. Find the last index where the value is greater than or equal to a[i-1].
4. Swap a[i-1] with the element at the last index.
5. Reverse the order of elements in the tail of the array (after index i-1).

Example: Permuting an Array [3, 4, 6, 2, 1]

Recursive Algorithm:

1. Swap 3 with 4: [4, 3, 6, 2, 1]
2. Recursively permute [4, 3, 6, 2, 1]
3. Swap 3 with 6: [4, 6, 3, 2, 1]
4. Recursively permute [4, 6, 3, 2, 1]
5. Continue until all permutations are generated

Non-Recursive Algorithm:

1. Start with [1, 2, 3, 4, 6] (sorted ascending)
2. The sequence is descending, so proceed to Step 3
3. Find the first index where a[i] < a[i-1]: i = 4, since 3 < 4
4. Find the last index where a[j] >= a[i-1]: j = 5, since 6 >= 3
5. Swap a[i-1] with a[j]: [1, 2, 6, 3, 4, 5]
6. Reverse the tail of the array: [1, 2, 3, 4, 5, 6]
7. Repeat Steps 3-6 until the array is in descending order (indicating all permutations have been generated)

The outcome for both algorithms is the same: all possible permutations are generated and printed.

The above is the detailed content of How Can I Generate All Permutations of an Array Using Recursive and Non-Recursive Algorithms?. For more information, please follow other related articles on the PHP Chinese website!