串匹配问题,求快速解法!

时间:2021-12-28 23:30:26

问题描述,有属性集<a,b,c,d>,对象集<1,2,3,4>,若对象具有某属性则mark “1”,否则mark “0”,构建如下矩阵:
a b c d 
1 1 1 0 1
2 1 0 1 0
3 0 1 1 0
4 1 1 1 1
求解:找出这样的对象集属性集的对: <set(对象),set(属性)>,满足set(对象)中所有对象共有的属性都在set(属性)中,且覆盖set(属性)中所有属性的对象都在set(对象)中。

则上述问题的解为:

124,a  (1000)
134,b (0100)
234,c (0010)
24,ac (1010)
34,bc (0110)
14,abd (1101)
4,abcd (1111)

解题的基本方法是有,但要找个快速的则小有难度,大家有什么比较快的方法么?

5 个解决方案

#1


实际上是要找所有元素都为1的(最大)子矩阵。
如果数据规模只是4×4,那么怎样都好办。
如果数据量再大,解的规模都是指数级的,再快还能快到哪里去?

#2


如果属性的个数是固定的;只是对象多的话,可以看成是o(n)的;


对于4个属性的所有组合有2^4==16个,也就是set(属性)最多16个;这样对象集属性集的对数也最多有16个,
每个组合(set(属性))可以对应于一个0-16之间的二进制数;如:a (1000),ac (1010) 

每一个对象所具有的属性也对应于一个0-16之间的二进制数,如对象1 (1 1 0 1);

对每一个对象,判断符合16个组合的哪些组合,若符合,则加入对应的set(对象);
对象的二进制数 与 set(属性)的二进制数 的逻辑与的结果 ==set(属性)的二进制数,则表示符合,否则不符合;

#3


嗯 矩阵的规模不只4×4,而且可能很大。担心的就是矩阵扩大时的算法效率

#4


属性集的大小与对象集的大小都不固定

#5


属性集、对象集的大小也不固定

#1


实际上是要找所有元素都为1的(最大)子矩阵。
如果数据规模只是4×4,那么怎样都好办。
如果数据量再大,解的规模都是指数级的,再快还能快到哪里去?

#2


如果属性的个数是固定的;只是对象多的话,可以看成是o(n)的;


对于4个属性的所有组合有2^4==16个,也就是set(属性)最多16个;这样对象集属性集的对数也最多有16个,
每个组合(set(属性))可以对应于一个0-16之间的二进制数;如:a (1000),ac (1010) 

每一个对象所具有的属性也对应于一个0-16之间的二进制数,如对象1 (1 1 0 1);

对每一个对象,判断符合16个组合的哪些组合,若符合,则加入对应的set(对象);
对象的二进制数 与 set(属性)的二进制数 的逻辑与的结果 ==set(属性)的二进制数,则表示符合,否则不符合;

#3


嗯 矩阵的规模不只4×4,而且可能很大。担心的就是矩阵扩大时的算法效率

#4


属性集的大小与对象集的大小都不固定

#5


属性集、对象集的大小也不固定