How to Generate All Permutations of an Array, Including Those with Repeated Elements?

Generating All Permutations of an Array

Given an array of distinct elements, the aim is to list all possible permutations of the array elements.

Algorithm

The following algorithm generates all permutations in O(N!) time complexity:

1. Initialize: Set i = 0.
2. Iterate over array: While i is less than the array length:
3. Swap: Swap the element at index i with each of the remaining elements in the array.
4. Recurse: Recursively call the algorithm with i 1 as the new i value.
5. Swap back: After the recursive call, swap the element back to its original position.
6. Increment i: Increment i by 1.

Python Implementation

def permute(arr, i=0):
    if i == len(arr) - 1:
        print(arr)
        return

    for j in range(i, len(arr)):
        arr[i], arr[j] = arr[j], arr[i]
        permute(arr, i + 1)
        arr[i], arr[j] = arr[j], arr[i]

Jarvis March Algorithm

For arrays with repeated elements, the Jarvis March algorithm is a more efficient approach:

1. Sort: Sort the array in ascending order.
2. While: While not done:
3. Find pivot: Find the largest index where the element is less than its successor.
4. Find adjacent: Find the last element in the sorted portion that is greater than the element at the pivot index.
5. Swap: Swap the elements at the pivot and adjacent indices.
6. Reverse: Reverse the elements from the pivot index to the end of the sorted portion.
7. Check done: Check if the array is sorted in descending order. If so, exit the loop.

Python Implementation

def permute_repeated(arr):
    ind = [0] * len(arr)
    for i in range(len(arr)):
        ind[i] = i

    while True:
        yield [arr[i] for i in ind]

        for i in range(len(arr) - 2, -1, -1):
            if ind[i] < ind[i + 1]:
                break

        if i == -1:
            return

        for j in range(len(arr) - 1, -1, -1):
            if arr[j] > arr[i]:
                ind[i], ind[j] = ind[j], ind[i]
                break

        ind[i + 1:] = sorted(ind[i + 1:])

The above is the detailed content of How to Generate All Permutations of an Array, Including Those with Repeated Elements?. For more information, please follow other related articles on the PHP Chinese website!