순열 (Permutation)

순열 (Permutation)

순열(Permutation) ?

👉 서로 다른 n개의 원소 중 r개를 순서대로 골라내어 한줄로 나열하는 것

 

순열의 수식

순열의 수식

Factorial

nPr = n개의 원소 중에 r개를 선택하여 일렬로 나열했다는 의미

nPn = 팩토리얼(Factorial)이라 불리며, n부터 1까지의 모든 수를 곱한 값

위의 식을 보면 반복되는 공식이 존재하므로, 순열은 재귀함수를 적용하여 나타낼 수 있음

 

재귀함수를 모른다면 밑의 링크를 참고해보자.

재귀함수 👉  https://ichijeochi.tistory.com/11

재귀 (Recursive)

 

N값에 따른 순열 (feat. Factorial)

N	순열 값	Million / sec	Billion / sec
9	362880
10	3628800
11	39916800	seconds
12	479001600	minutes
13	6227020800	hours	seconds

        : 보통 알고리즘 문제의 답안은 초 단위로 시간제한이 있으므로 N이 11인 팩토리얼까지를 주로 계산하게 될 것

위의 N의 팩토리얼 값을 구할때에는 팩토리얼 계산기를 이용하면 편리

https://ourcalc.com/factorial-calculator/

팩토리얼 계산기

 

순열을 생성하는 방법 (feat. Pseudo-Code)

✔ 재귀호출을 통한 순열 생성

 ex) {1, 2, 3}을 포함하는 모든 순열을 생성하는 함수

num[] : 순열 저장 배열 (멤버변수)
select[] : 인덱스에 해당하는 숫자가 사용중인지 저장하는 배열 (num 배열과 같은 크기)
permutation (cnt)  // 현재까지 뽑은 순열 수의 개수   

if(cnt==3)   // 순열 생성 완료
else
     for i from 1 to 3  // 가능한 모든 수에 대해 시도
    	 if select[i] == true  then continue;  // 이미 사용한 수라면 continue;
         num[cnt] ← true  // 수 사용
         select[i] ← true  // 사용 표시
         permutation(cnt+1)  // 다음 인덱스로 넘어가기 (cnt = 지금까지 선택한 수의 개수)
         select[i] ← false  // 사용하지 않은 수로 다시 되돌려놓기
     end for

     선택된 숫자가 들어갈 인덱스는 계속 바뀌며, 해당 인덱스를 결정하는 요인은 "앞에서 수를 선택했는가?"

     ❓ 앞에서 선택된 수인지 어떻게 알 수 있을까?

          1️⃣ 멤버변수를 이용하여 기존에 뽑았던 수들을 공유

          2️⃣ 매개변수로 기존에 뽑았던 수들을 전달하여 공유

          👉 개인적으로 1️⃣의 방법이 코드가 더 간결해져서 주로 멤버변수를 이용