
배열의 순열 생성
배열의 순열은 해당 요소의 고유한 배열로 구성됩니다. N 요소 배열의 경우 N! (N 계승) 별개의 순열. 이 질문의 목적은 이러한 순열을 생성하는 알고리즘의 개요를 설명하는 것입니다.
알고리즘:
배열 순열을 생성하려면 다음 단계를 고려하세요.
- 초기화: 첫 번째 요소를 피벗으로 가져와서 시작합니다. 현재 순열 목록의 첫 번째 위치.
-
재귀 순열: 배열의 나머지 요소를 반복합니다. 각 요소를 피벗으로 교체하고, 다음 위치에서 업데이트된 피벗으로 순열 함수를 재귀적으로 호출한 후 다시 교체하여 원래 순서를 복원합니다.
- 예를 들어 {3,4,6, 2,1}을 피벗 3으로 사용하면 {4,6,2,1}을 반복합니다. 4를 3으로 바꾸고, {4, 3, 2, 1}을 피벗 4로 재귀적으로 치환한 다음 다시 바꿉니다.
-
종료: 루프가 마지막 요소이면 현재 순열 목록이 완성됩니다. 출력하세요.
구현:
다음은 위 알고리즘의 Python 구현입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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]
|
로그인 후 복사
예 사용법:
1 2 3 | arr = [3, 4, 6, 2, 1]
permutations = generate_permutations(arr)
print (permutations) # [[3, 4, 6, 2, 1], [3, 4, 2, 6, 1], ... ]
|
로그인 후 복사
참고: 이 방법은 현재 순열의 시작 및 끝 요소만 유지하고 다음 위치에서만 전체 목록을 구성하여 메모리 사용량에 최적화될 수 있습니다. 전체 순열 목록을 메모리에 보관할 필요가 없습니다.
위 내용은 배열의 모든 순열을 어떻게 생성할 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!