순열(permutation) 알고리즘
순열(permutation)이란 숫자나 문자들의 집합(set)에 순서를 부여하여 나열하는 것이라고 생각하면 된다. 예를들어 원소가 'A', 'B', 'C'를 가진 집합 S 가 있다면 ( { 'A', 'B', 'C' } ∈ S) 이 A ,B, C 각각의 원소를 일렬로 나열했을때 나올수 있는 경우의 수는 (A, B, C), (A, C, B), (B, A, C), (B, C, A), (C, A, B), (C, B, A) 총 6가지가 나올수 있다. 순열에 대해서 자세히 알고 싶으면 순열(permutation) 를 먼저 읽어봐라. 그럼 순열을 프로그래밍적으로 어떻게 접근해야 할까? 만약 {a,b,c,d}의 모든 순열을 구한다고 하면 ☞ 첫 원소가 a이면서 {b,c,d}의 모든 순열 ☞ 첫 원소가 b이면서 {a,c..
멱집합(Power Set)
A의 모든 부분집합을 원소로 하는 집합을 A의 멱집합(power set)이라 하고 P(A) 또는 2A로 나타낸다. 예를들어 S = { 1 , 2, 3, 4 } 일때 부분집합(power set) = {{}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4}, {2,4}, {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}} 이다. 따라서 임의의 유한집합에 대해서 그 크기가 |A| = n 이라고 할때, 부분집합의 개수는 2n 개가 된다. 그럼 컴퓨터에서 임의의 집합의 모든 부분집합을 출력하는 알고리즘은 어떻게 될까? 사실 생각해보면 { a, b, c, d, e, f } 의 모든 부분집합을 나열하려면 a 를 제외한 { b, c, d,..
