Geek asks and answers

Assessment of the given expressions

I have a universe of elements organized in n disjoint sets. I have m expressions built using these sets using union / intersection / difference operators. Therefore, given the element, I need to evaluate these m expressions to find out which of the "derived" sets contains this element. I do not want to compute a "derived" set, because it will be very little time and space. Is there a way to say whether an element will lie in one of the derived sets simply by looking at its expression? E.g. if the expression C = AUB and the element lies in the set A, then I can say that it will lie in the set C. Are there any C libraries to perform such calculations?

+5
source share
1 answer

if im not an error, let e = element

replace each set A, B with true if e is in the set, false if it is not. Then convert the set operators to their logical equivalents and evaluate the expression as logical. It should display logical operators well, even xor and more.

for example, if e is in both AB, but not D

C = (A U B) xor D

he will be in C because

    C = (true or true) xor false
->      (true)        xor false
-> true

This can be pretty fast if you can quickly find if an item is in a set

+4
source

More articles:


All Articles