組合/笛卡爾積的計算（沒有重複且沒有訂單限制）

Question

我有一個組合問題，可以使用多個組的笛卡爾 產品低效地解決。具體而言，我有多個項目和 滿足每個項目的多個元素。問題包括查找滿足所有項目的元素 的所有可能組合。例如：

items -> elements 
------------------------ 
1 -> {a,b}  // a and b cover the item 1 
2 -> {a,b}  // a and b cover the item 2 
3 -> {a,b,c} // a, b and c cover the item 3 
4 -> {a,b,e,f} // a, b, e, f cover the item 4 

Alternative representation: 
element -> items covered 
------------------------ 
a -> {1,2,3,4} 
b -> {1,2,3,4} 
c -> {3} 
e -> {4} 
f -> {4} 

目標是找到涵蓋項目1,2,3,4的所有組合。 有效的解決方案是：

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

注意，順序並不重要，所以{a,b} = {b,a} ({a,b} x {c,d} = {c,d} x {a,b})。 另請注意，{a,a,a,a}, {a,a,a,b}...是冗餘組合。

正如你可以看到，這個問題是類似於set cover problem，其中對於這個示例性元件的宇宙 是項U={1,2,3,4}和該組的子集的從U是S={ab={1,2,3,4},c={3},ef{4}}，其中設置{1,2,3,4}是所涵蓋的設定項目的元件a和b，{3}是一組由覆蓋c元素，且{4}是一組由元件e和f覆蓋元件。然而，這裏的目標是找不到涵蓋來自U的所有元素的來自S的集合的最小組合，但找到涵蓋所有項目{1,2,3,4}的元素{a,b,c,e,f}的所有組合。

通過在1,2,3和4之間執行 組之間的笛卡爾乘積，然後過濾冗餘組合，可以完成一個實現。不過，這種方法效率非常低。假設我有這樣的情況：

1 -> {a,b,c,d,e,f,g,h} 
2 -> {a,b,c,d,e,f,g,h} 
3 -> {a,b,c,d,e,f,g,h} 
4 -> {a,b,c,d,e,f,g,h} 
5 -> {a,b,c,d,e,f,g,h} 
6 -> {a,b,c,d,e,f,g,h,i} 

將導致8^5*9=294912組合六套之間笛卡爾積，當實際上有很多的組合較少，這是 ：{a,b,c,d,e,f,g} U {a,b,c,d,e,f,g} x {i}。

解決此問題的另一種方法是枚舉所有元素，跳過等效於其他先前生成的組合，並跳過重複的元素也跳過 。這很容易計算，並且可以作爲一次返回組合的迭代器來實現，但我不知道是否有更好的方法來解決這個問題，或者如果之前研究過這個問題。

你會如何解決這個問題？

Answer 1

首先，認識到如果一組元素不滿足所有項目，它的任何子集都不會滿足。其次，要意識到如果一個集合滿足所有項目，那麼所有的超集也是如此。現在

，所有你需要做的是：

令S是集合所有元素。 設R是空集。

定義一個函數查找（S，R），其作用：

If r includes s, return r. 
If s does not satisfy all items, return r. 

Otherwise add s to r. 
For every item I in s, 
    let s' be s-I 
    let s be f(s', r) 

return s. 

只需調用發現（S，R），你有你的答案。

該方法執行一些重複測試，但只要它被識別出來就總是會殺死一個分支。這導致大量元素的修剪。

對於r是否包含特定元素集合以及檢查s是否滿足所有項目的查找都可以非常快速地以犧牲額外內存爲代價。如果

Answer 2

你這樣做：

1 -> {a,b} 
2 -> {b,c} 
3 -> {a,b,c} 
4 -> {a,e,f} 

=> 

a -> [1,3,4] 
b -> [1,2,3] 
c -> [2,3] 
e -> [4] 
f -> [4] 

然後枚舉左側提供（至少）[1,2,3,4]

For each item in the set of all-satisfying sets, enumerate combinations 
with other items. 

All-Satisfying-Sets: {{a,b},{b,e},{b,f}} 
Combinations within All-Satisfiying-Sets: {{a,b,e},{a,b,f},{b,e,f},{a,b,e,f}} 
Others: {c} 
Combinations with Others: {{a,b,c},{b,e,c},{b,f,c} 
          ,{a,b,e,c},{a,b,f,c},{b,e,f,c},{a,b,e,f,c}} 

組合或者你可以在Haskell中執行此操作：

import Data.List (union, subsequences, sort) 

example1 = [(["a"],[1,2,3,4]) 
      ,(["b"],[1,2,3,4]) 
      ,(["c"],[3]) 
      ,(["e"],[4]) 
      ,(["f"],[4])] 

example2 = [(["a"],[1,2,3,4,5,6]) 
      ,(["b"],[1,2,3,4,5,6]) 
      ,(["c"],[1,2,3,4,5,6]) 
      ,(["e"],[1,2,3,4,5,6]) 
      ,(["f"],[1,2,3,4,5,6]) 
      ,(["g"],[1,2,3,4,5,6]) 
      ,(["h"],[1,2,3,4,5,6]) 
      ,(["i"],[6])] 

combs items list = 
    let unify (a,b) (a',b') = (sort (a ++ a'), sort (union b b')) 
    in map fst 
    . filter ((==items) . snd) 
    . map (foldr unify ([],[])) 
    . subsequences 
    $ list 


OUTPUT: 

*Main> combs [1..4] example1 
[["a"],["b"],["a","b"],["a","c"],["b","c"],["a","b","c"],["a","e"],["b","e"], 
["a","b","e"],["a","c","e"],["b","c","e"],["a","b","c","e"],["a","f"],["b","f"], 
["a","b","f"],["a","c","f"],["b","c","f"],["a","b","c","f"],["a","e","f"], 
["b","e","f"],["a","b","e","f"],["a","c","e","f"],["b","c","e","f"], 
["a","b","c","e","f"]]