问题描述,有属性集<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,那么怎样都好办。
如果数据量再大,解的规模都是指数级的,再快还能快到哪里去?
如果数据规模只是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(属性)的二进制数,则表示符合,否则不符合;
对于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,那么怎样都好办。
如果数据量再大,解的规模都是指数级的,再快还能快到哪里去?
如果数据规模只是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(属性)的二进制数,则表示符合,否则不符合;
对于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
属性集、对象集的大小也不固定