순열과 조합, 부분집합 간단 정리(+비트마스킹, NextPermutation)

순열과 조합, 부분집합은 모두 완전탐색 방법이다.

각 방법들은 반복문, 재귀함수로 구현이 가능하다.

-순열(permutation)

:서로 다른 n 개 중에서 r 개를 뽑아서 한 줄로 나열한다. (”순서” 의미가 있다.)

: nPr로 표현한다.

: nPr = n * (n-1) * (n-2) … (n-r+1)

: nPn = n!(팩토리얼)

 

-조합(combination)

: 서로 다른 n개의 원소 중 r개 원소를 가지며 순서가 없음.

:nCr로 표현한다.

: n! / (n-r)! r!

 

-부분집합

: 다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 것이다.

집합은 순서의 의미가 없다. (=조합) ex) {A,B} == {B,A}

 

-순열을 생성하는 방법

1.반복문을 통한 순열 생성

뽑는 수가 고정적일 때만 사용한다. 변동이 있으면 계속 반복문을 추가해야하기 때문이다.

 

2.재귀를 통한 순열 생성

일반적인 순열 구현 방법으로 재귀 호출을 통해 생성한다.

 

3.비트마스킹을 통한 순열 생성

시간초과가 나지 않을 정도의 10!(팩토리얼) 이하의 경우의 수 중 java기준 int형 32비트로 나타낼 수 있을 경우 비트마스킹을 이용하여 빠른 연산이 가능하다.

 

4.NextPermutation 

비트마스킹보다 빠른 방법이다. 하지만, 제한적으로 nPn일 경우에만 사용이 가능하다. (nanotime 함수를 호출하여 비교했을 경우 10P10 기준으로 비트마스킹보다 약 5배 빠른 연산 시간을 보여준다.)

• NextPermutation의 알고리즘
• : 현 순열에서 사전 순으로 다음 순열 생성
• 아래 과정을 반복하여 사전 순으로 다음 큰 순열 생성

배열을 오름차순으로 정렬한 후 시작한다.

1. 뒤쪽부터 탐색하며 교환위치(i-1) 찾기(i : 꼭대기)
2. 뒤쪽부터 탐색하며 교환위치와 교환할 큰 값 위치(j) 찾기
3. 두 위치 값(i - 1, j) 교환
4. 꼭대기위치(i)부터 맨 뒤까지 오름차순 정렬

 

-조합에서의 NextPermutation 활용

1)원소 크기와 같은 크기의 int 배열 P를 생성하여 r개 크기만큼 뒤에서 0이 아닌 값으로 초기화한다.

2)nextPermutation 알고리즘을 활용한다.

3) 2번 수행시마다 조합이 생성된다.