StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><code>union(a, b, c) = union(union(a, b), c)</code>, and the same goes for <code>intersection()</code>. 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.</p> <p>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.</p> <pre><code>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]); } </code></pre> <p>Similar code works for <code>multi_union()</code>, 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.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload