nPr 순열 구현
-
6 순열과 조합 : 조합의 구현Discrete mathmatics and Problem Solving/6, 8 경우의 수와 그 응용(dp) 2017. 10. 16. 23:43
이전포스트순열과조합: 순열의구현 순열과 조합, 조합의 구현 이전 포스트에서는 순열을 구현해 보았는데요, 순열의 특징은 사전순으로 정렬하는데 있습니다. 그렇다면 조합의 경우는 어떨까요? 우선 조합은 다음과 같은 특징을 같습니다. 비트스트링을 생각해보죠, 해당 원소가 포함되는 곳엔 1, 아닌 곳은 0이 됩니다. 아래그림을 확인해보죠. r-조합은 기본적으로 n개 중 r개를 선택한 원소들의 고유한 집합입니다. 따라서 위와 같은 비트 스트링으로 포함, 비포함으로 표현할 수 있습니다. 자, 우선 모든 조합을 고려해보죠.그러니까 비트스링의 모든 경우의수요. 그렇다면 경우의수는 2^n 가지 입니다. 자, 우선 간단한 예제를 풀어볼까요?예제 41010111 의 다음 비트스링은 뭔가?정답1010111의 다음 비트스트링은 ..