算法问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Computation - 科学计算

算法问题

算法问题# Computation - 科学计算

s*s2007-09-17 07:09

1 楼

最近遇到个问题，忘了有没有相关算法了。
有一些set, from A1 to An, each set contains a number of elements
Ai and Aj has intersection. 比如 Ai=(1,2,3,4) Aj=(3,4,7,8,9,10).
How to find the minimum number of sets from A1 to An so that
Union of these sets = Union of A1 ... An
Thanks.

sc2007-09-17 07:09

2 楼

我不知道是不是有现成的算法，
不过想了一个，不知道好使不好使，
有数组B(1..M)，
初始话：
建个可以反查的质数表P(i)
loop i
loop A_i(j)
k=A_i(j)
如果B(k)没值，B(k)=P(i)
否则B(k)=B(k)*P(i)
end loop
end loop
然后扫描数组B，是质数，说明stand alone，这个质数对应的set要得，
然后用这个质数除B里的每一个可以整除的元素。
一直搞一直搞，搞到它剩下一堆1和一堆合数，
然后找最小公约数什么的。
整个过程有点烦，不知道有没有简单的。

【在 s********s 的大作中提到】

: 最近遇到个问题，忘了有没有相关算法了。
: 有一些set, from A1 to An, each set contains a number of elements
: Ai and Aj has intersection. 比如 Ai=(1,2,3,4) Aj=(3,4,7,8,9,10).
: How to find the minimum number of sets from A1 to An so that
: Union of these sets = Union of A1 ... An
: Thanks.