Sets union in O(N)

Revision en3, by Kambar_Z, 2023-06-06 01:25:21

Hello everyone!

While solving a math problem recently, I came up with an interesting trick on sets union. The ordinary solution using inclusion-exclusion principle for 3 sets looks as following:

|x1 ∪ x2 ∪ x3| = |x1| + |x2| + |x3| — (|x1 ∩ x2| + |x1 ∩ x3| + |x2 ∩ x3|) + |x1 ∩ x2 ∩ x3|

Obviously the time complexity to compute union of N sets by this approach is O(2 ^ N).

Now, lets store for each set xi (1 <= i <= N) only those subsets that are not intersected with other subsets on prefix:

u1 = x1

u2 = |x2| — |x2 ∩ u1|

u3 = |x3| — |x3 ∩ u2| — |x3 ∩ u1|

Then answer could be found as following:

|x1 ∪ x2 ∪ x3| = |u1| + |u2| + |u3|

The algorithm is simplified to O(N ^ 2).

But, we can reorder the formula to compute each ui as following:

u3 = |x3| — |x3 ∩ |u1 ∪ u2||

u4 = |x4| — |x4 ∩ |u1 ∪ u2 ∪ u3||

...

Here we only need to maintain the union of previous subsets on prefix, that could be done in O(1) since they do not intersect.

Thus total complexity to find union of N sets is reduced to O(N).

Tags math, inclusion-exclusion, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Kambar_Z 2023-06-06 01:25:21 26 Tiny change: ' found as union of all subsets (ui):\n\n|x1 ∪' -> ' found as following:\n\n|x1 ∪'
en2 English Kambar_Z 2023-06-06 01:24:22 19
en1 English Kambar_Z 2023-06-06 01:19:08 1120 Initial revision (published)