F # Powerset 함수

Question

아래 함수는 집합 (list)의 powerset을 반환합니다.

let rec powerset = function 
    | [] -> [[]] 
    | x::xs -> List.collect (fun sub -> [sub; x::sub]) (powerset xs) 

정확하게 작동하는지 이해할 수 없습니다. 재귀를 이해합니다. 나는 또한 List.collect가 어떻게 작동 하는지를 이해한다. 나는 powerset의 인스턴스가 [[]]를 반환 할 때까지 계속 재귀가 일어난다는 것을 안다. 그러나, 그 지점 이후에 반환 된 값을 추적하려고 시도하고 완전한 전력 집합을 얻지 못합니다.

Answer 1

전원 집합을 계산하기위한 알고리즘은 다음과 같이 진행됩니다

이의이 (일명 "입력") A 원래 세트를 부르 자. 그리고 해당 세트에서 항목을 골라 내고 x이라고합니다. 이제 A의 powerset ( P(A)라고 함)은 A의 모든 하위 집합 집합입니다. A의 모든 하위 집합은 x을 포함하는 하위 집합과 x을 포함하지 않는 하위 집합으로 구성됩니다.

all subsets of A that don't include x = P(A-x) 

어떻게이 x을 포함 할 우리의 모든 부분 집합을받을 수 있나요 A것을 : 그것은 x을 포함하지 않는 부분 집합 (제외 x와 A) A - x의 모든 가능한 부분 집합이라는 것을 쉽게 알 수? x을 포함하지 않고 모든 사람에게 x을 집어 넣으십시오!

all subsets of A that include x = { for each S in P(A-x) : S+x } 

이제 우리는 두 가지를 결합해야합니다, 우리는 우리 자신에게 P(A)를 얻을 : 다음 powerset xs를 호출하여이 P(A-x) 계산하고 :

P(A) = P(A-x) + { for each S in P(A-x) : S+x } 

이 코드 예제의 마지막 줄이하는 일입니다 각 하위 집합에 대해 x을 붙이며 하위 집합 자체도 포함합니다.