Eglusaxie 2022-02-09 22:41 采纳率: 100%
浏览 55
已结题

求“最大公共偏序子集”

有两个各自具有一种序结构的集合,如何寻找这两个集合的一种共同子集使得:
1、子集中元素的排列顺序能同时满足这两个集合上的序结构;
2、符合1的前提下,子集尽可能大

比如把两个字符串当做集合:
a="我不知道如何解决这个问题"
b="不知道我能否想出解决该问题的办法"
那么符合条件的所谓“最大公共偏序子集”就是:
"不知道解决问题"

稍微解释一下c怎么来的,所谓的序结构,比如a字符串的就是:“我”要排在“不”前面,“不”又要排在后面的其他字前面,字符串上这种覆盖每个字的一维的从左到右的可传导的顺序关系,就可以当做是a字符串所具有的一个序结构,同理b字符串也一样。
然后c在是a,b的公共子集的同时,c中的每一个元素,还要满足a,b上的顺序关系,比如开头的"我"和"不"字,虽然是a,b的共同元素,但是它们两个字在a中和在b中的先后顺序不一样,所以它们不能同时出现在c中。
就是这么回事吧,有点像是在找最长公共子串,也有点像求交集。
声明一下,标题中的“最大公共偏序子集”这个名字是我乱取的,只是为了简要概括题意而已,不过或许数学里真有这么个说法。
其实这里的集合,也不是严格数学定义的集合,可以当他是一个collection而不是set,也就是说,元素可重复。
请各位给点思路就好

  • 写回答

2条回答 默认 最新

  • Eglusaxie 2022-02-10 14:53
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 2月18日
  • 已采纳回答 2月10日
  • 修改了问题 2月10日
  • 修改了问题 2月10日
  • 展开全部

悬赏问题

  • ¥100 支付宝网页转账系统不识别账号
  • ¥15 基于单片机的靶位控制系统
  • ¥15 AT89C51控制8位八段数码管显示时钟。
  • ¥15 真我手机蓝牙传输进度消息被关闭了,怎么打开?(关键词-消息通知)
  • ¥15 下图接收小电路,谁知道原理
  • ¥15 装 pytorch 的时候出了好多问题,遇到这种情况怎么处理?
  • ¥20 IOS游览器某宝手机网页版自动立即购买JavaScript脚本
  • ¥15 手机接入宽带网线,如何释放宽带全部速度
  • ¥30 关于#r语言#的问题:如何对R语言中mfgarch包中构建的garch-midas模型进行样本内长期波动率预测和样本外长期波动率预测
  • ¥15 ETLCloud 处理json多层级问题