算法 - 找到满足输入元素任意组合的所有集合

Question

假设我们有一个输入，它是一个元素列表:

{a, b, c, d, e, f}

还有不同的集合，可能包含这些元素的任意组合，也可能包含不在输入列表中的其他元素:

A:{e,f} B:{d,f,a} C:{g,a,b} D:{a,h,k}

算法应该只返回集合 A 和 B。

乍一看，我想到了对输入列表进行排序并遍历所有集合，检查集合中的每个元素是否存在于输入列表中。在我的例子中，虽然输入列表会很小，但集合的数量会很大，所以我不想遍历所有集合，除了一次。输入经常会改变，但集合不会。

Answer 1

您可以将输入集的(有限!)字母表转换为位集，然后使用二元运算来测试另一个集是否是引用集的(完整)子集。

这里是一个示例实现:

type CharSet = string
type EncodedCharSet = uint32

let encode (set : CharSet) : EncodedCharSet =
    set.ToCharArray()
    |> Array.fold (fun a c -> a ||| (1u <<< (int c - int 'a')) ) 0u

let inSet (reference : EncodedCharSet) (test : EncodedCharSet) : bool =
    0u = (reference &&& test) ^^^ test

let test a b =
    let (ae,be) = (encode a, encode b)
    inSet ae be

[
    "ef"
    "dfa"
    "gab"
    "ahk"
]
|> List.map (test "abcdef")