# Efficiently construct unique pairs of sets, over and over again

I have a problem that might be a well-known/researched issue in mathematics and set-theory.

Basically I want to efficiently combine pairs of sets into one single sets, and keep doing that (with an additional constraint that I will explain in my example). I'm trying to come up with an efficient algorithm to implement.

Example:

Let's say I start with five one-element sets: {a}, {b}, {c}, {d}, {e}. I run my constraint/condition test, which will tell me which set(s) I will keep and which set(s) I will remove.

Think of it like that: myConstraint({a}) = Yes (meaning I will keep) or No (meaning I will delete).

Let's assume that after running my constraint I am left with:

{a}, {b}, {c}, {e}: Set 1. ({d} did not satisfy my constraint).

Now I want to form pairs from the sets that I already have, which will give me:

{a, b}, {a, c}, {a, e}, {b, c}, {b, e}, {c, e}

• I can simply do that by starting from first set {a} and pair it with the remaining sets {b}, {c}, and {e}, then go the second set {b} and pair it with the remaining sets {c} and {e}, and finally go to the third set {c} and pair it with the remaining set {e}. - Let's call this Method 1

I run my 'myConstraint' on each set and let's say I'm left with:

{a, b}, {a, c}, {b, c}, {b, e}, {c, e}: Set 2. ({a, e} did not satisfy my constraint)

The total sets that satisfy my constraint are the following (Set 1 + Set 2):

{a}, {b}, {c}, {e}, {a, b}, {a, c}, {b, c}, {b, e}, {c, e}

Now I want to form pairs from those sets. The problem is that if I follow Method 1, I will have many duplicates and duplicates are inefficient to detect; will need to check all previous sets if there's a duplicate)

Here's a sample result for using Method 1

{a, b}, {a, c}, {a, e}, {a, a, b} = {a, b} (duplicate), {a, a, c} = {a, c} (duplicate) . . .: Set3

And finally, I will need to get $$Set 1 \cup Set3$$ Some duplicates in last step too.

I thought of a couple of algorithms by finding mutually exclusive sets, but I always end up with many duplicates. Is there a neat way to solve this problem?

-
Have you looked at BDDs? Represent each element as a variable, write sets as conjunction of variables ("is a member") and negated variables ("is not a member"), e.g., $a \wedge b \wedge \neg c \wedge \neg d \wedge \neg e$ for $\{ a, b\}$ (with elements $a,b,c,d,e$) and save all seen sets as a disjunction. This is relatively efficient, seen-BDD construction is easy (just build the set formula and OR it to the "seen BDD"), and containment checking is trivial (is set formula AND seen BDD not 0?). – Johannes Kloos Apr 19 '12 at 16:12
How large could the initial set be? How many rounds of pairings do you need to do? – Aryabhata Apr 19 '12 at 16:20
@Aryabhata: it's relatively large (could start with hundreds, or maybe thousands), but the constraint will get rid of a lot of them, as the size increases. – Roronoa Zoro Apr 19 '12 at 16:23
What about the number of rounds of pairings? – Aryabhata Apr 19 '12 at 16:27
@Aryabhata: for the data that I have, the final sets will consists of ~5 elements, probably never more than 10 – Roronoa Zoro Apr 19 '12 at 16:39

One thing you can possibly do is to use something similar to Tries.

You will have one trie for each possible set size.

Maintain each set in a sorted fashion, i.e. you represent set $\{d,a,b\}$ as $a\to b\to d$ (say using a linked list).

Now to combine two given sets $A$ and $B$, perform a merge sort of the corresponding linked lists, eliminating dupes.

You can find the length of $A \cup B$ (during the merge itself) and then perform a lookup on the corresponding Trie to see if it has appeared before. If it has not, you insert it into the trie.

Using a trie, a lookup of a given set would be dependent on the size of the set you are looking up, and not the number of existing sets.

Basically, a trie is a form of hashing, where you can do the lookup with time dependent only on the item you are looking up.

For instance, if your universe was smaller (say $\le 64$ elements), then on a $64$-bit machine, you could represent each set as a bitvector, which would correspond to a $64$-bit integer.

To merge two sets, all you do is a bitwise OR.

To make lookups of existing sets faster, you maintain a hashtable of the corresponding integers.

Of course, you could possibly use the bit vector approach when your universe is larger, but then computing the hash itself might take time, there might be more collisions etc. You can replace the hash table with a trie in that case.

-
Clever answer, but I still have three questions; 1) What if my data is not intrinsically sorted. Each element (a or b) is actually a pair of values read from a database, so like <name, id> or <age, id> (age would be replaced with the actual value of age, like 22, same goes for name or id, so it won't be trivial to sort those, especially if their different attributes. Like <name(Bob), id(9)> and <hairColor(black), age(22)>. My second question is that why "one Trie for each possible set size" it seems that there should be one Trie, and the length from the root to the leaf would be the length. – Roronoa Zoro Apr 20 '12 at 18:47
I deleted my last comment (third question); I figured out it doesn't really make sense... – Roronoa Zoro Apr 20 '12 at 19:17
@RoronoaZoro: 1) You can define any ordering, for instance you can use the row number in the database table, or just the index in an array where you store the elements. 2) That was just an attempt at an optimization, you can do it the way you say. In fact, you might save some space doing it your way. – Aryabhata Apr 20 '12 at 19:36

Ok, here is a solution using BDDs.

Assume a set $U := \{ a_1, \ldots, a_n \}$ of finitely many elements is given. We wish to represent a collection $S \subseteq 2^U$ of subsets of $U$, where adding a new subset to the collection and querying whether some subset is contained should be fast.

Associate to each $a_i$ a propositional variable $p_i$. Then a subset $T \subseteq S$ can be represented by a propositional formula as $\varphi_T = \bigwedge_{i: a_i \in T} p_i \cap \bigwedge_{j: a_j \not\in T} \neg p_j$. For example, if $U = \{ a_1, a_2, a_3, a_4, a_5\}$, the subset $T = \{ a_1, a_2, a_5\}$ is represented as $p_1 \wedge p_2 \wedge \neg p_3 \wedge \neg p_4 \wedge p_5$.

If you have a family $T_1, \ldots, T_k$ of subsets, this family can be represented by the propositional formula $\psi_{\{T_1,\ldots,T_k\}} := T_1 \vee \ldots \vee T_k$.

In other words, build a set representation formula is straightforward, and adding a subset $T$ to the collection $V$ of subsets is implemented as $\psi_{V \cup \{ T \}} = \psi_V \vee \varphi_T$.

To find out whether a subset $T$ is contained in a family $V$, we need to test whether $\psi_V \models \varphi_T$, or equivalently, $\neg \psi_V \wedge \varphi_T$ is unsatisfiable.

Now, to implement this in software, the easiest solution is to use an existing BDD library. This library will provide all required operations, and BDD operations for the formulas occuring in set representations such as these tend to be extremely fast.

-
Ok. So are you suggesting that I have one family for each specific number of elements? And then I construct all possible pairs, and for each pair, I check whether it exists or not (based on the level of pairing), if it does exist, ignore it, and if it doesn't exist add it. Is this what's on your mind? Another (interesting) question would be, can you go from the family of subsets to the subsets themselves? Like can you re-construct $$T_1 \bigvee ... \bigvee T_k \mbox{ from } \psi_{{T_1, ..., T_k}}$$ Is this by any chance related to something called representative sets? If Yes, any references? – Roronoa Zoro Apr 20 '12 at 22:45
You can use just a single family, basically representing "all sets seen so far". Then you can check if the set has been seen already and add it if it doesn't exist. You can easily go from families to subsets - just enumerate satisfying assignments, which are directly equivalent to subsets. I don't know about representative sets, since I have never heard that term so far. – Johannes Kloos Apr 21 '12 at 14:27
I think this will only work if I use all sets (not having my constraint). e.g. let's say I start with 3 sets $$T_1 = {a_1}, T_2 = {a_2}, T_3 = {a_3}$$ When pairing the three sets, I will get, $$T_1 \bigvee T_2 = \{a_1, a_2\}, T_1 \bigvee T_3 = \{a_1, a_3\}, T_2 \bigvee T_3 = \{a_2, a_3\}$$ Now let's say $$T_1 \bigvee T_2$$ does not satisfy my constraint. The final family: $$(T_1 \bigvee T_3) \bigvee (T_2 \bigvee T_3)$$ Will be $$p_1 \bigvee p_2 \bigvee p_3$$ Which, if we enumerate, will give us all possible pairs. But $$T_1 \bigvee T_2$$ is wrong... – Roronoa Zoro Apr 21 '12 at 16:51
No, this is not how it works. $T_1 \vee T_2$ corresponds to $\{ \{ a_1 \}, \{ a_2 \} \}$, not $\{ a_1, a_2 \}$. – Johannes Kloos Apr 21 '12 at 22:34