r*******y
发帖数: 1081 | 1 givn m sets. some sets may be subsets of others. If one set is a subset of
another set, then this smaller set will be removed. Finally we have the sets
from which we can not remove any set. Assume the elements in all the sets
are
same type and only "==" operator is supported on these elements.
Is there any good algorithm to do this job ? Thanks. | g**********y
发帖数: 14569 | 2 基本想法：把Element映射到数字，然后用Bitmap来计算包容关系。
pesudo-code =>
foreach set in sets {
Bitmap b1 = transform(set);
boolean add = true;
foreach b2 in map.keySet() {
Bitmap b3 = b1.and(b2);
if (b3.equals(b2)) {
bitmaps.remove(b2);
}
else if (b3.equals(b1)) {
add = false;
}
}
if (add) map.put(b1, set);
}
return map.values(); | r*******y
发帖数: 1081 | 3 So it is using hashing. But how to do hashing here is also a big deal, right
?
Thanks
【在 g**********y 的大作中提到】
: 基本想法：把Element映射到数字，然后用Bitmap来计算包容关系。
: pesudo-code =>
: foreach set in sets {
: Bitmap b1 = transform(set);
: boolean add = true;
: foreach b2 in map.keySet() {
: Bitmap b3 = b1.and(b2);
: if (b3.equals(b2)) {
: bitmaps.remove(b2);
: }
| g**********y
发帖数: 14569 | 4 I am not sure what's your question. But as example, here is a simplified
Java implementation, assume sets no more than 32. If more than that, you can
use BigInteger or write your own class.
public class Subset {
public Set[] merge(Set[] sets) {
HashMap cardinal = new HashMap();
HashMap map = new HashMap();
HashSet remove = new HashSet();
for (Set set : sets) {
int b1 = transform(set, cardinal);
boolean add = true;
remove.clear();
for (int b2 : map.keySet()) {
int b = b1 & b2;
if (b == b1) {
add = false;
}
else if (b == b2) {
remove.add(b2);
}
}
if (add) map.put(b1, set);
for (Integer b : remove) map.remove(b);
}
Set[] result = new Set[map.size()];
return map.values().toArray(result);
}
private int transform(Set set, HashMap cardinal) {
int n = 0;
for (Object o : set) {
if (!cardinal.containsKey(o)) {
cardinal.put(o, cardinal.size());
}
n |= 1 << cardinal.get(o);
}
return n;
}
}
right
【在 r*******y 的大作中提到】
: So it is using hashing. But how to do hashing here is also a big deal, right
: ?
: Thanks
|
|
