intersection and union of n-arrays in C

Question

I have those functions which are making intersection/union but just of two arrays. I need too improve them to work with n-arrays: arr = {{1,2,3},{1,5,6},...,{1,9}}.
The arrays are sorted , and their elements are unique among them.
Example (intersection):
Input: {{1,2,3,4},{2,5,4},{4,7,8}}
Output: {4}

arr1[],arr2 - arrays
m,n - length of the arrays Intersection function:

int printIntersection(int arr1[], int arr2[], int m, int n)
{
  int i = 0, j = 0;
  while(i < m && j < n)
  {
    if(arr1[i] < arr2[j])
      i++;
    else if(arr2[j] < arr1[i])
      j++;
    else /* if arr1[i] == arr2[j] */
    {
      printf(" %d ", arr2[j++]);
      i++;
    }
  }
}

and union function:

int printUnion(int arr1[], int arr2[], int m, int n)
{
  int i = 0, j = 0;
  while(i < m && j < n)
  {
    if(arr1[i] < arr2[j])
      printf(" %d ", arr1[i++]);
    else if(arr2[j] < arr1[i])
      printf(" %d ", arr2[j++]);
    else
    {
      printf(" %d ", arr2[j++]);
      i++;
    }
  }

  while(i < m)
   printf(" %d ", arr1[i++]);
  while(j < n)
   printf(" %d ", arr2[j++]);
}

Why not loop over the n arrays calling either function with a solution -so-far array and the next array. — Mark Meyer

j_random_hacker j_random_hacker · Accepted Answer · 2012-11-06T15:25:00

union(a, b, c) = union(union(a, b), c), and the same goes for intersection(). I.e. you can decompose the union or intersection of n sets into n unions or intersections of 2 sets (as NuclearGhost points out in a comment on the question). What you need to do is change your current functions so that they build up a resulting set, instead of immediately printing the result. You can then make a separate function that prints a set.

For efficiency, you want to take the union or intersection of sets that are roughly of equal size. So a divide-and-conquer approach should work alright, assuming that all input sets are likely to be of roughly equal size.

void intersection(int arr1[], int arr2[], int m, int n, int *out)
{
  int i = 0, j = 0;
  while(i < m && j < n)
  {
    if(arr1[i] < arr2[j])
      i++;
    else if(arr2[j] < arr1[i])
      j++;
    else /* if arr1[i] == arr2[j] */
    {
      *out++ = arr2[j++];
      i++;
    }
  }
}

void multi_intersection(int n, int **arrays, int *lengths, int *out) {
  if (n == 2) {
    intersection(arrays[0], arrays[1], lengths[0], lengths[1], out);
  } else if (n == 1) {
    memcpy(out, arrays[0], lengths[0] * sizeof (int));
  } else {
    /* Allocate buffers large enough */
    int *buf[2];
    int len[2] = { INT_MAX, INT_MAX };
    int i;
    for (i = 0; i < n; ++i) {
      int which = i < n / 2;
      if (lengths[i] < len[which]) len[which] = lengths[i];
    }
    buf[0] = malloc(len[0] * sizeof (int));
    buf[1] = malloc(len[1] * sizeof (int));

    /* Recurse to process child subproblems */
    multi_intersection(n / 2, arrays, lengths, buf[0]);
    multi_intersection(n - n / 2, arrays + n / 2, lengths + n / 2, buf[1]);

    /* Combine child solutions */
    intersection(buf[0], buf[1], len, out);

    free(buf[0]);
    free(buf[1]);
}

Similar code works for multi_union(), except that the buffer lengths need to be calculated differently: the result of a union could be as large as the sum of the sizes of the inputs, rather than the minimum size of the inputs. It could probably be rewritten to do less buffer allocation. Also the recursion could be rewritten to use iteration, the same way mergesort can be written to use iteration, but the current recursive approach uses only O(log n) additional stack space anyway.

intersection and union of n-arrays in C

2 Answers