集合的组合/笛卡尔积的计算（无重复且无顺序限制）

问题描述 投票：0回答：3

我有一个组合问题，可以使用笛卡尔低效地解决 多套产品。具体来说，我有多个项目和多个元素 满足每一项。问题包括找到所有可能的元素组合 满足所有项目。例如：

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
覆盖的元素集合。然而，这里的目标不是找到 覆盖 
S
中所有元素的集合的最小组合，但找到覆盖所有项目 
U
的元素 
{a,b,c,e,f}
的所有组合。
可以通过在之间执行笛卡尔积来完成简单的实现
设置1、2、3和4，然后过滤掉多余的组合。然而，
这种方法效率很低。假设我有这样的情况：



{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
。
解决这个问题的另一种方法是枚举所有元素，跳过
与之前生成的其他组合等效的组合，以及
跳过重复的元素。这很容易计算并且可以实现
作为一次返回一个组合的迭代器，但我不知道是否有
解决这个问题的更好方法，或者之前是否研究过这个问题。



你会如何解决这个问题？

    

	




algorithm

combinations

enumeration

cartesian-product


3个回答




    
    
    

        

            

                

                    
2
投票

                    
                

            

        

        



其次，认识到如果一个集合满足所有项目，那么它的所有超集也满足。



现在，您所要做的就是：



设S是所有元素的集合。
设 R 为空集。



定义一个函数 find( s, r ) ，它的作用是：



{a,b,c,d,e,f,g} U {a,b,c,d,e,f,g} x {i}



只需调用 find(S,R) 即可得到答案。



此方法执行一些重复的测试，但每当分支被识别时总是会杀死它。这会导致对大量元素进行大量修剪。



查找 r 是否包含特定的元素集以及检查 s 是否满足所有项目都可以非常快地进行，但需要额外的内存。

    





    

    
    
    

    

        

            

                

                    
1
投票

                    
                

            

        

        



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.




然后枚举左侧提供（至少）[1,2,3,4]的组合



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]




或者你可以在 Haskell 中执行此操作：



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}}


    



    

    
    
    

    

        

            

                

                    
0
投票

                    
                

            

        

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

去掉重复，得到
['ab','ab','ab','abc']
。最坏的情况是，没有共享项，您将生成集合的所有笛卡尔积。如果您只想要指定的集合的唯一子集（最小生成集，而不是最小生成集），那么这将很容易生成；在最坏的情况下，这会生成集合的笛卡尔积，但是当集合之间存在大量共享元素时，可以使用
['ab','abc']
例程（此处
描述）更有效地完成。例如，

cnf_dnf

即使您想要所有
唯一
顺序无关紧要的全长集，也有一种有效的方法可以做到这一点，并使用
>>> sets = [
 {1, 2, 4, 6, 7, 10},
 {2, 3, 4, 6, 7, 10},
 {2, 7, 8, 9, 10},
 {1, 2, 3, 4, 5, 7, 10},
 {1, 2, 3, 5, 8, 9},
 {1, 2, 3, 5, 7, 10},
 {1, 2, 4, 6, 7},
 {2, 3, 4, 5, 6, 8, 9, 10},
 {1, 2, 4, 7, 8, 9},
 {1, 2, 3, 4, 5, 7, 8, 10}]
>>> from time import time
>>> from itertools import product

# there are many possible products

>>> t=time();sum(1 for i in product(*sets)),time()-t
(87091200, 4.305924654006958)

# there are very few minimal spanning sets

>>> t=time();sum(1 for i in cnf_dnf(sets)),time()-t
(28, 0.00010538101196289062)
例程按字典顺序生成它们
。这将以有效的方式生成以下子集：
combogen


但是您需要最小集
和
冗余条目，这些条目不会重复您已有的内容。这是一个更困难的问题，我不确定吉拉德的“建议”是否真的会让它变得容易得多。生成最小跨度集很容易，但随后要弄清楚如何在不重复的情况下组合它们，并强制从每个集合中只取出一项的条件。
在我看来，你能做的最好的事情就是过滤 >>> sum(1 for i in combogen(sets, len(range(sets))))
81399
 生成的唯一元组的结果；对于上面定义的集合，这只需一秒多一点的时间。对于给定的集合，它会完成繁重的工作，将 8700 万种可能性的简单乘积减少到 81000 种可能性；对结果的设定值进行排序并保留唯一的值，剩下的值将少于 1000:


combogen
如果您有一组“小”组，您可以从以下内容开始，这对于 7 组（每组 7 个唯一值）或 20 组（每组 2 个唯一值）来说还不错：


>>> sum(1 for i in {tuple(sorted(set(i))) for i in combo(sets)})
934


    

	

    

    


  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2025. All rights reserved.