[알고리즘] 순열, 조합 응용(비트마스킹)

순열

nPr

• 서로 다른 n 개중에 r를 뽑아 한줄로 나열하는 것 // 순서가 의미가 있음
  nPr = n(n-1)(n-2)...(n-r+1)

비트연산자

• & : 비트 단위로 AND 연산을 한다.
  같으면 1, 다르면 0
• | : 비트단위로 OR 연산을 한다.
  두비트 중 하나라도 같으면 1, 전부 다르면 0
• ^ : 비트 단위로 XOR 연산을 한다.
  같으면 0, 다르면 1
• ~ : 단항연산자로서 피연산자의 모든 비트를 반전시킨다.
• << : 피연산자의 비트 열을 왼쪽으로 이동시킨다.
  왼쪽으로 밀어내고 남은 오른쪽 자리는 0으로 채움
• >> : 피연산자의 비트 열을 오른쪽으로 이동시킨다.

순열 응용 : 비트마스킹 순열 pseudo code

//nPn : N개의 원소로 만들 수 있는 모든 순열 생성
inpur[] : 숫자 배열
numbers[] : 순열 저장 배열

perm(cnt, flag) // cnt: 현재까지 뽑은 순열의 수, flag : 선택된 원소에 대한 비트 정보
	if(cnt == N) 순열 생성
    else
    	for i from to N-1
        	if((flag & 1<<i) != 0 then continue
            numbers[cnt] <- input[i]
            perm(cnt+1, (flag | 1<<i)
        end for
end perm()

순열 응용 : Next Permutation

현 순열에서 사전 순으로 다음 순열을 생성하는 것

• 구현 알고리즘
  배열을 오름차순으로 정렬한 후 시작한다.
  아래 과정을 반복하여 사전 순으로 다음으로 큰 순열 생성(가장 큰 내림차순 순열을 만들 때까지 반복한다.)
  1. 뒤쪽부터 탐색하며 교환위치(i-1)찾기 // i는 꼭대기
  2. 뒤쪽부터 탐색하며 교환위치(i-1)와 교환할 큰 값 위치(j) 찾기
  3. 두 위치 값(i-1,j) 교환
  4. 꼭대기 위치(i)부터 맨 뒤까지 오름차순 정렬

• 주의 사항 : NP 사용 전에 오름차순으로 정렬하여 가장 작은 순열을 한번 처리 해야 함.

조합

nCr

• 서로 다른 n 개중에 r를 뽑는것 // 순서가 의미가 없음
  nCr = n!/(n-r)!*r!

조합을 Next Permutation을 활용하여 생성하는 법

원소크기와 같은 크기의 int 배열 P를 생성하여 rㄱ 크기만큼 뒤에서 0이 아닌 값(예를 들어 1)으로 초기화 한다.
NextPermutation 알고리즘을 활용한다.
NextPermutation 알고리즘 한번 수행 시마다 조합이 만들어짐
-> NextPermutation 과정 수행 시마다 0이 아닌 값의 위치가 변경됨
P배열에서 0이 아닌 값을 가지고 있는 위치에 해당하는 원소가 조합의 원소임.