[请教] 集合分组问题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

[请教] 集合分组问题

[请教] 集合分组问题# JobHunting - 待字闺中

x*g2014-02-05 08:02

1 楼

Programming版在打擂台，根本没人看，在此请教。
有一个集合 {a1, a2, a3 ... an}
其上定义有 >, =, ==, 这些关系均可传递
不符合以上条件的定义为 <>

例如在有限个复数集合上 1 < 2, 1+i < 2+i
但是我们只知道 3 <> 2 + i, 无法比较大小

希望找到该集合的所有满足以下条件的子集：
（1）子集内的元素不存在 <> 关系
（2）任意一个子集不属于另一个子集

实在想不出有效的算法，请各位大侠指教。
谢谢啦！

f*e2014-02-05 08:02

2 楼

strong connected component + DAG?

【在 x***g 的大作中提到】

: Programming版在打擂台，根本没人看，在此请教。
: 有一个集合 {a1, a2, a3 ... an}
: 其上定义有 >, =, ==, 这些关系均可传递
: 不符合以上条件的定义为 <>
:
: 例如在有限个复数集合上 1 < 2, 1+i < 2+i
: 但是我们只知道 3 <> 2 + i, 无法比较大小
:
: 希望找到该集合的所有满足以下条件的子集：
: （1）子集内的元素不存在 <> 关系

x*g2014-02-05 08:02

3 楼

展开说说？
谢谢。

【在 f*****e 的大作中提到】

: strong connected component + DAG?

x*g2014-02-05 08:02

4 楼

如果不满足第二条也可以，第二条可以用暴力解决。