How Can I Generate All Permutations of an Array?

Generating Permutations of an Array

An array's permutation comprises a unique arrangement of its elements. For an N-element array, there exist N! (N factorial) distinct permutations. This question aims to outline an algorithm for generating these permutations.

Algorithm:

Consider the following steps for generating array permutations:

1. Initialize: Begin by taking the first element as the pivot and placing it in the first position of the current permutation list.

2. Recursive Permutation: Loop through the remaining elements of the array. Swap each element with the pivot, call the permutation function recursively with the updated pivot at the next position, and swap again to restore the original order.

   • For example, given {3,4,6,2,1} with pivot 3, you iterate over {4,6,2,1}. You swap 4 with 3, recursively permute {4, 3, 2, 1} with pivot 4, and swap back.
3. Termination: When the loop reaches the last element, the current permutation list is complete. Output it.

Implementation:

Here's a Python implementation of the above algorithm:

def generate_permutations(arr):
  perms = []
  _generate_permutations_helper(arr, 0, perms)
  return perms


def _generate_permutations_helper(arr, start, perms):
  if start == len(arr) - 1:
    perms.append(arr.copy())
  else:
    for i in range(start, len(arr)):
      arr[start], arr[i] = arr[i], arr[start]
      _generate_permutations_helper(arr, start + 1, perms)
      arr[start], arr[i] = arr[i], arr[start]

Example Usage:

arr = [3, 4, 6, 2, 1]
permutations = generate_permutations(arr)
print(permutations)  # [[3, 4, 6, 2, 1], [3, 4, 2, 6, 1], ... ]

Note: This method can be optimized for memory usage by maintaining only the starting and ending elements of the current permutations and constructing the full list only at the end, eliminating the need to keep the entire list of permutations in memory.

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