[Algorithm] 순열 (Permutation)

순열

어떤 리스트에서 뽑는 순서에 따라 결과가 다른 경우를 말한다.

예를들어 {1,2,3}에서 3개를 뽑는 경우

{1,2,3}, {1,3,2}
{2,1,3}, {2,3,1}
{3,1,2}, {3,2,1}

총 6가지의 경우의 수가 존재한다.

 

순열 형태

vector<int> list = {1,2,3}; 
do {
  for (int i : list)
    cout << i << " ";
} while(NextPermutaion(list.begin(), list.end());

• NextPermutaion(from, to)
  •  입력값
    • from : 리스트의 첫번째 요소
    • to     : 리스트의 마지막 요소 (null)
  • 주의
    
    • 리스트는 사전에 오름차순으로 정렬되어 있어야 한다.

 

순열의 개수

순열의 개수는 공식을 통해 구할 수 있다.

• n = 총 개수
• r = 선택할 개수
• nPr = n개 중에 r개를 선택하여 나오는 순열의 개수 

 

참고

순열과 조합