주어진 정수의 모든 순열을 인쇄하는 재귀 적 방법의 의사 코드

Question

나는이 의사 코드를 정말로 이해하지 못합니다.이 함수는 모든 숫자가 다르다고 가정하면 $ n $ 의 모든 순열을 인쇄합니다.

스와핑의 목적을 얻지 못하는 것처럼이 코드를 더 쉽게 설명하는 방법이 있습니다.

PERMUTATE(A, start, end)
   if start == end return A
   else
      PERMUTATE(A,start+1,end)
      for i = start+1 to end
         SWAP(A[i],A[start])
         PERMUTATE(A,start+1,end)
         SWAP(A[start],A[i])

.

Answer 1

귀하의 절차는 입력의 모든 순열을 생성하여 끝 부분에 원래 상태로 되돌립니다.

입력이 길이 1이면 할 일이 없습니다.

그렇지 않으면 입력이 $ a_1, \ ldots, a_n $ 이라고 가정합니다. $ a_1, \ ldots, a_n $ 의 모든 순열을 $ [a_1, \ ldots, a_n] $ < / span>.

여기는 절차가 수행하는 것입니다.

• 출력 $ A_1, [A_2, A_3, \ LDOTS, A_ {N-1}, A_N] $ .
• 출력 $ a_2, [a_1, a_3, \ ldots, a_ {n-1}, a_n] $ .
• 출력 $ A_3, [A_2, A_1, \ LDOTS, A_ {N-1}, A_N] $ .
• ...
• 출력 $ a_n, [a_2, a_3, \ ldots, a_ {n-1}, a_1] $ .

첫 번째 단계에서 절차는 첫 번째 요소를 제외한 모든 것들로 구성된 목록의 꼬리의 모든 순열을 초과합니다.

두 번째 단계에서 $ A_1 $ 및 $ a_2 $ 을 전환합니다. 모든 순열을 초과합니다. 꼬리의 $ a_1 $ 및 $ a_2 $

를 전환합니다.

세 번째 단계에서 $ A_1 $ 및 $ a_3 $ 을 전환하고 모든 순열을 초과합니다. 꼬리의 $ A_1 $ 및 $ a_3 $

$ n $ th 단계에서 $ a_1 $ 을 전환 할 때까지 $ a_n $ 은 꼬리의 모든 순열을 초과 한 다음 $ a_1 $ 및 $ a_n $ 뒷면.