이 멱집합 생성 함수는 어떻게 동작하는거죠?

Elm 강의를 보고 있는데 멱집합을 생성하는 함수가 과제로 나왔다. 한참을 고민하다가 결국 검색을 해보게 되었다. 반성하는 차원에서 How is this powerset generating function working?를 짧게 번역했다. 수학공부 부지런히 해야겠다.


이 멱집합 생성 함수는 어떻게 동작하는거죠?

리스트를 넣어 멱집합을 생성하는 함수를 만들려고 하는데 다음과 같은 코드를 인터넷에서 찾게 되었다. 설명은 없었지만 테스트 해보니 정상적으로 동작했다. 이 함수가 어떻게 동작하는지 이해할 수가 없었다. 설명을 해주면 감사하겠다.

generateSubset [] = [[]]
generateSubset (x:xs) = let p = generateSubset xs in p ++ map (x:) p

Daniel Wagner의 답변

멱집합의 특성으로 쉽게 증명할 수 있다. P(A ∪ B) = {a ∪ b | a ∈ P(A) 또는 b ∈ P(B)}. 특히 집합 S와 그 집합에 포함된 원소인 s로 분해하고 S’의 모든 원소는 s가 아닐 때,

P(S) = P({s} ∪ S')
     = {a ∪ b | a ∈ P({s}), b ∈ P(S')}

여기서 P({s})는 직접 계산하기 좋을 정도로 충분히 작다. P({s}) = {{}, {s}}. 이 사실로 다음과 같이 유도한다.

P(S) = {a ∪ b | a ∈ {{}, {s}}, b ∈ P(S')}
     = {b | b ∈ P(S')} ∪ {{s} ∪ b | b ∈ P(S')}
     = P(S') ∪ {{s} ∪ b | b ∈ P(S')}
     = let p = P(S') in p ∪ {{s} ∪ b | b ∈ p}

이 방법은 멱집합이 빈 원소를 갖는 집합이기 때문에 사용 가능한 계산 방법이다. 먼저 원소를 고른 후, 나머지로 멱집합을 연산한다. 그 후 각각의 부분집합에 추가하거나 더하지 않는다. 질문한 함수는 이 부분을 코드로 전환한 것으로 리스트를 집합으로 사용했다.

-- P         ({s} ∪ S') = let p = P(S')             in p  ∪ {{s} ∪ b | b ∈ p}
generateSubset (x:xs)   = let p = generateSubset xs in p ++     map (x:) p

재귀를 위해 기본값을 넣어주는 일만 남았다. 멱집합의 정의에 따라 다음과 같이 추가한다.

-- P          ({}) = {{}}
generateSubset []  = [[]]
김용균

안녕하세요, 김용균입니다. 문제를 해결하기 위해 작고 단단한 코드를 작성하는 일을 합니다. 웹의 자유로운 접근성을 좋아합니다. 프로그래밍 언어, 소프트웨어 아키텍처, 커뮤니티에 관심이 많습니다.

이 글 공유하기

이 글이 유익했다면 주변에도 알려주세요!

페이스북으로 공유하기트위터로 공유하기링크드인으로 공유하기Email 보내기

주제별 목록

같은 주제의 다른 글을 읽어보고 싶다면 아래 링크를 확인하세요.

August 25, 2015

FP in Elm 노트 – 코스 개요

seoh 님의 Elm Resources 글에서 [Functional Programming: Purely Functional Data Structures in Elm ] 3 강의를 알게 되었다. 개요를 읽고 흥미가 생겨 강의 노트를 읽기 시작했고…

August 15, 2015

호주에서의 세번째 이사

1년 반 만에 세번째 이사를 하게 되었다. 그간 Justin 님 댁에서 감사하게도 정말 편하게 하숙 생활을 하며 걱정없이 지낼 수 있었다. 몸이 편하면 게을러지는 타입인 나란 사람은 좀 더 부지런히 지내기 위해 주변 환경을 바꿔야겠다는 생각이 들어…