如何使用C程序从集列表中删除超集
我在一个文本文件中有一个如下所示的集合列表。这些是我的代码的输出，它生成一个图的路径。节点0与1、5相连，节点1与0、5、2相连，节点5与0、1、6相连，所有节点都相连。
图表如下所示：
0
1 5
2 6
3 7
4 8
9
( source 0 , destination 9)创建的路径：
0 1 2 3 4 9
0 1 2 3 7 8 9
0 1 2 6 7 3 4 9
0 1 2 6 7 8 9
0 5 6 2 3 4 9
0 5 6 2 3 7 8 9
0 5 6 7 3 4 9
0 5 6 7 8 9 我想删除属于另一个集合的超集(包含另一个集合的所有元素，但带有附加元素的集合)的所有行。
对于上面的示例，删除超集应该会导致以下结果：
0 1 2 3 4 9
0 1 2 6 7 8 9
0 1 2 3 7 8 9
0 5 6 7 8 9
0 5 6 2 3 4 9
0 5 6 7 3 4 9 删除的超集：
0 1 2 6 7 3 4 9
0 5 6 2 3 7 8 9 我如何在C程序中做到这一点。对于大量的图形路径，我必须做到这一点。
回答 1
Stack Overflow用户
发布于 2020-03-14 16:07:01
考虑两个路径，path1和path2，使得path2 > path1，即path2包含所有节点或path1 +一些额外的节点。这意味着在某些情况下，path2必须从path1中分离出来，而在某些node2之后，则必须重新连接。但是，因为path1没有任何不在path2中的节点，所以在path1中不应该有node1和node2之间的节点。换句话说，node2必须恰好位于node1之下。因此，path2背离并重新连接到path1的唯一可能是做一个小循环:向右移动一个节点，向下移动一个节点，然后向左移动一个节点，或者对称的路径:一个向左，一个向下，一个向右。因此，path2必须包含节点的完整“正方形”：
node node
node node反之也是正确的-如果某个路径包含完整的节点正方形，则可以通过直接向下移动而不是左右移动来简化它。所以，你只需要删除所有的路径，其中包含任何相邻节点的方块。在您的示例中，您需要删除包含以下任何内容的路径
1 5 2 6
2 6 3 7
3 7 4 8 此外，您必须排除在开头和结尾包含可避免的循环的路径：
0 1 5
4 8 9但是，此解决方案要求您从上到下生成所有可能的路径。现在您还没有生成所有可能的路径，例如path
0 1 5 6 7 8 9都不见了。
当然，在没有超集的情况下生成路径要容易得多。当你生成这样的路径时，你不能允许在另一个下面切换分支。分支交换机之间必须至少有一次垂直移动。
https://stackoverflow.com/questions/60679181
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号