算法 - 查找滿足輸入元件

的任何組合假設我們有一個輸入，其是元素的列表的所有集合：算法 - 查找滿足輸入元件

{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

算法 - 查找滿足輸入元件

回答

相關問題