如果您有一组范围,例如以下简单示例......
[
[12, 25], #1
[14, 27], #2
[15, 22], #3
[17, 21], #4
[20, 65], #5
[62, 70], #6
[64, 80] #7
]
...你如何计算最大交叉子集(不确定如何短语,但我的意思是"相交且具有最高基数的范围的子集")并确定交集的程度(该子集中范围的基数) )？
逻辑上我可以解决它,并且可能能够将其转换为天真的算法.沿着列表,我们看到1-5相交,5-7相交,#5与两组相交.
我想要的结果只是子集,因为它给了我关于基数的信息,只要它们都相交,我就可以轻松地计算集合的交集.在上面的例子中,它将是[[14, 27],[15, 22],[12, 25],[17, 21],[20, 65]].
在我的脑海中,我可能会尝试将每个范围转换为图形节点,连接相交的图形节点,并找到最大的完全连接图形.
我也在思考迭代地从头开始,继续建立一个相交范围的列表,每个交叉范围都有一个运行的交叉点来检查 - 直到你碰到一个不相交的元素,然后开始一个新的列表.继续针对现有交叉点检查每个项目.但是我不确定这是完整的.
我可以尝试实施某些东西(lang是ruby FWIW),但我很想听听其他人如何解决这个问题,以及最有效和最优雅的方式.
更新:
我认为这是最大集团问题的一个特例,它是NP难的,因此实际上很难.对于近似/实际使用的建议将非常感谢!
另请参阅:http://en.wikipedia.org/wiki/Maximum_clique/查找图表中的所有完整子图
更新2
在这里找到了这个问题的NP-硬度和NP-完整性的一个很好的证明:http://www.cs.bris.ac.uk/~popa/ipl.pdf
看起来这是行的结束.对不起人!我将使用足够好的贪婪近似.谢谢.
如答案所述,我不认为该论文描述了这个问题......我们可能会根据范围提供更多信息.
我正在使用Rails并在SublimeText中使用Ruby 1.9,但它使用Ruby 1.9的新哈希语法进行了一些古怪的突出显示.
例如,使用以下哈希,这对于rails非常常见:
<%= link_to some_page_here_path, class: "btn btn-primary" %>
当class关键字实际上不是真正的关键字而是仅仅是一个简单的哈希键时,该关键字会突出显示.我更喜欢它是否被设计为符号(它在Ruby 1.9中)而不是保留字.这也适用于其他保留字,'for','while','do'等.
有没有办法在现有的Ruby.tmLanguage或已经完成的tmLanguage文件中使这个工作？感谢任何帮助.谢谢!