배열의 모든 순열을 어떻게 생성할 수 있습니까?

배열의 순열 생성

배열의 순열은 해당 요소의 고유한 배열로 구성됩니다. N 요소 배열의 경우 N! (N 계승) 별개의 순열. 이 질문의 목적은 이러한 순열을 생성하는 알고리즘의 개요를 설명하는 것입니다.

알고리즘:

배열 순열을 생성하려면 다음 단계를 고려하세요.

1. 초기화: 첫 번째 요소를 피벗으로 가져와서 시작합니다. 현재 순열 목록의 첫 번째 위치.

2. 재귀 순열: 배열의 나머지 요소를 반복합니다. 각 요소를 피벗으로 교체하고, 다음 위치에서 업데이트된 피벗으로 순열 함수를 재귀적으로 호출한 후 다시 교체하여 원래 순서를 복원합니다.

   • 예를 들어 {3,4,6, 2,1}을 피벗 3으로 사용하면 {4,6,2,1}을 반복합니다. 4를 3으로 바꾸고, {4, 3, 2, 1}을 피벗 4로 재귀적으로 치환한 다음 다시 바꿉니다.
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 중국어 웹사이트의 기타 관련 기사를 참조하세요!