f# - F# 中获取集合的幂集的函数

Question

我正在尝试用 F# 编写一个函数来获取集合的幂集。到目前为止我已经写了:

let rec powerset = function
    |[] -> [[]]
    | [x] -> [[x]; []]
    |x::xs -> [x] :: (List.map (fun n -> [x; n]) xs) @ powerset xs;;

但这不会返回具有 3 个或更多元素的情况，仅返回对、单个元素和空集。

Answer 1

您的方向是正确的，这是一个有效的解决方案:

let rec powerset = 
   function
   | [] -> [[]]
   | (x::xs) -> 
      let xss = powerset xs 
      List.map (fun xs' -> x::xs') xss @ xss

看你只需要使用这个技巧:

for each element x you there half of the elements of the powerset will include x and half will not

因此，您递归地生成剩余元素xss的幂集，并将两部分连接起来(List.map (fun xs' -> x::xs') xss将在每个前面添加 x)

但请注意，这不是尾递归，并且会破坏更大列表的堆栈 - 您可以采用这个想法并尝试使用 seq 实现它，或者如果您愿意，可以制作一个尾递归版本

---

使用seq

这是一个使用 seq 和自然数的二进制表示(这些数字的子集)和集合的子集之间的双射的版本(将元素映射到数字并设置 1，如果对应的元素在子集中，否则为 0):

let powerset (xs : 'a seq) : 'a seq seq =
    let digits (n : bigint) : bool seq =
        Seq.unfold (fun n -> 
            if n <= 0I 
            then None 
            else Some (n &&& 1I = 1I, n >>> 1))
            n
    let subsetBy (i : bigint) : 'a seq =
        Seq.zip xs (digits i)
        |> Seq.choose (fun (x,b) -> if b then Some x else None)
    seq { 0I .. 2I**(Seq.length xs)-1I }
    |> Seq.map subsetBy

这适用于诸如 powerset [1..100] 之类的东西，但可能需要很长时间才能将它们全部枚举出来;)(但它不应该占用太多内存......)