본문 바로가기
컴퓨터/수학이랑

주어진 집합의 모든 부분집합을 구하기

by adnoctum 2010. 8. 2.

   문제는, 말 그대로 간단하다. 주어진 배열의 모든 부분집합을 구해내는 것. 짱구 한 10분 굴려 나온 코드의 아이디어를 스케치 해보자.

   우리가 일반적으로 주어진 배열에 대하여 k-개의 원소로 된 부분집합을 다 구하고자 할 때는 다음과 같은 절차를 따르게 된다.

위에서 붉은 색이 선택한 요소라 하자. 위 그림은 2개의 원소로 된 부분집합을 모두 구하는 절차를 표현한 것이다. 우선 가장 왼쪽의 요소 2개를 선택할 것이다. 그 후, 가장 오른쪽 요소를 한 칸 오른쪽으로 옮기겠지. 이런 식으로 계속 오른쪽으로 한 칸씩 옮기면서 2개로 된 부분집합을 만들어 나가는 것이다. 그러다 더이상 움직일 수 없다면 이제 바로 앞의 요소를 한 칸 오른쪽으로 옮기는 것이다. 물론 이 단계에서 가장 오른쪽에 있던 요소는 다시 앞으로 이동을 하되, 현재 오른쪽으로 옮긴 요소보다는 바로 앞 칸에 있어야 하겠지(위 그림에서 (1) 이라고 표시된 부분).

   위 절차를 일반성을 잃지 않고 (ㅋㅋ without loss of generality[각주:1]), 자연수 k 개로 확장하면[각주:2] 우리가 원하는 알고리즘이 된다. 코드로 표현하면 다음과 같다.




위 코드를 C++로 옮기면 다음과 같을 것이다.




뭐, 효율성이나 코드의 aesthetics 따윈 보이지 않는, 참으로 날것의 코드 :) 어쨌거나 위에 나타난 기본적인 방법을 이용하면 좀 더 일반성 있는 코드 - 가령 iterator나 template을 이용하거나 - 나 좀 더 효율적인 코드(특히 파이썬 코드에서)를 작성하는 것에는 큰 어려움이 없을 것이다. 언제나 중요한 것은 idea 니까, 코딩 따위야 그냥 뭐 하면 되는 거지...





  1. 수학의 증명에 보면 자주 나오는 말, 일반성을 잃지 않으면서 모든 수에 대해 확장해 보면, 이란 말. ㅋㅋㅋ 여기 나와 있는 생각도 사실 원소가 2개인 부분집합에서 아이디어를 따온 후, 곧바로 k 라는 일반적인 자연수로 확장을 시켰을 뿐 별다른 것이 없다. [본문으로]
  2. 이런 부분을 여기서 설명해야 하나, 하는 궁금증이 있다. 1,2,3개 정도에서 되면 일반적인 n 으로 확장하는 것은 자주 접하던 일이라... 만약 이 부분이 명확하지 않다는 것을 알려 준다면 보충하겠습니다. [본문으로]