算法 - 查找满足输入元件

的任何组合假设我们有一个输入，其是元素的列表的所有集合：算法 - 查找满足输入元件

{A，B，C，d，E，F}

有也可以包含这些元素的任意组合，也可以包含不在输入列表中的其他元素：

A：{e，f} B：{d，f，a} C：{g ，a，b} D：{a，h，k}

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

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

2017-08-08 zwya

如果输入元件具有的可能性有限的量（例如“A” - “Z”），通常的方式是在一个单一的表示一组作为一个数位表示集合中的单个值... 1表示“存在元素”，0表示不存在。然后，您可以使用基本的二进制操作（和，或xor，...）快速检查一个集是否是结果集。 – BitTickler

事实上，可能性的数量是有限的。我认为我的最后一句写得非常糟糕，我的意思是这个算法预计每分钟运行几次，或者是一个新的输入列表，或者是一个基于前一个列表的修改过的列表。我会尽力在明天编写你的解决方案，看看它适合我的情况。 – zwya

您可以将输入集的（限制！）字母表转换为位集，然后使用二进制操作来测试另一个集是否是参考集的（完整）子集。

这里一个示例实现：

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")

来源

2017-08-08 00:48:16 BitTickler

算法 - 查找满足输入元件

回答

相关问题