F＃Powerset関数

Question

以下の関数は、セット（リスト）のパワーセットを返します。

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を含まないサブセットの2つのグループで構成されていると考えることができます。

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 } 

今、私たちはちょうど2つを組み合わせる必要がある、と私たちは自分自身P(A)取得：

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

これはあなたのコード例の最後の行が何をするかである：それは、その後powerset xsを呼び出してP(A-x)を計算し、それらのサブセットのそれぞれについて、xを貼り付け、サブセット自体も含む。