如何生成数组的所有排列？

生成数组的排列

数组的排列包含其元素的独特排列。对于 N 元素数组，存在 N! （N 阶乘）不同的排列。本问题旨在概述生成这些排列的算法。

算法：

考虑以下生成数组排列的步骤：

1. 初始化： 首先将第一个元素作为枢轴并将其放置在当前排列列表的第一个位置。

2. 递归排列：循环遍历数组的剩余元素。将每个元素与主元交换，在下一个位置使用更新后的主元递归调用排列函数，然后再次交换以恢复原始顺序。

   • 例如，给定 {3,4,6, 2,1} 与主元 3 一起，迭代 {4,6,2,1}。将 4 与 3 交换，用主元 4 递归排列 {4, 3, 2, 1}，然后交换回来。
3. 终止： 当循环到达最后一个元素，当前排列列表完成。输出它。

实现：

这是上述算法的 Python 实现：

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]

示例用法：

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

注意： 此方法可以通过仅维护当前排列的开始和结束元素并仅在最后，无需将整个排列列表保留在内存中。

以上是如何生成数组的所有排列？的详细内容。更多信息请关注PHP中文网其他相关文章！