[알고리즘] 순열(Permutaion) 및 조합(Combination)

순열은 n개의 성분 중 r개를 선택해 순서대로 나열하는 것을 의미하며, 그 경우의 수를 $_nP_r$이라고 한다.

가령 [1, 2, 3]에서 2개를 골라서 만들 수 있는 모든 순열은 [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]이고, 그 경우의 수는 $_3P_2$ = 6이다.

구현

---

조합은 n개의 성분 중 r개를 선택해 순서 상관 없이 나열하는 것을 의미하며, 그 경우의 수를 $_nC_r$이라고 한다.

가령 [1, 2, 3]에서 2개를 골라서 만들 수 있는 모든 조합은 [(1, 2), (1, 3), (2, 3)]이고, 그 경우의 수는 $_3C_2$ = 3이다.

순열에서 구성은 같고 순서만 다른 경우들에 대해 중복 처리를 해주면 조합을 구할 수 있다.
가령 (1, 2, 3), (2, 3, 1), (3, 1, 2)는 조합에서 하나로 통일된다.
이것이 $_nP_r$을 순열의 길이 r의 팩토리얼로 나눈 것이 $_nC_r$이 되는 까닭이다.

구현