Perl Weekly Challenge 127: Disjoint Sets

Input: @S1 = (1, 2, 5, 3, 4)
       @S2 = (4, 6, 7, 8, 9)
Output: 0 as the given two sets have common member 4.

Input: @S1 = (1, 3, 5, 7, 9)
       @S2 = (0, 2, 4, 6, 8)
Output: 1 as the given two sets do not have common member.

Given that the two input sets contain unique integers, the sets are disjoint, if and only, their union does not contain duplicates.

There are a few, all simple, ways to check for this.

Here, we put all the numbers (from both sets) in a hash, and check of the hash has as many keys as the union of the sets. Here, $_ will contain the input, the sets separated by a semi-colon, and the values with a space (the separators don't really matter, as we will just extract the numbers).

First we extract the numbers (of both sets) into an array @_:

@_ = /[-+]?[0-9]+/g;

We then put the numbers into a hash %_:

%_ = map {$_ => $_} @_

Finally, we contain the number of keys of %_ with the number of elements of @_. In modern Perls, a hash in scalar context returns the number of keys, and an array in scalar context returns the number of elements. So we get:

say %_ == @_ ? 1 : 0;

Find the full program on GitHub.

C lacks hashes, so we use a different strategy here. We take all the numbers, sort them, then do a single pass over them seeing if we have two indentical subsequent numbers. If we have such a pair, the sets are not disjoint; else, the sets are.

Here we have all the numbers in an array (of type int *) numbers; this array has i elements. We start off by sorting them, using quicksort:

/*
 * Compare two numbers
 */
int cmp (const void * a, const void * b) {
    return (* (int *) a - * (int *) b);
}

qsort (numbers, i, sizeof (int), cmp);

Now we can pass over the array, looking for duplicates:

int out = 1;
for (int j = 1; j < i; j ++) {
    if (numbers [j] == numbers [j - 1]) {
        out = 0;
        break;
    }
} 

printf ("%d\n", out);

Find the full program on GitHub.

A third way of solving this is by iterating over the numbers of the sets, while keeping a hash of numbers seen. For each of the numbers, if we have seen it before, the sets are not disjoint. Else, we store the number in the hash, and continue with the next.

Here, line contains the input:

local seen = {}
local out  = 1
for number in line : gmatch ("([-+]?[0-9]+)") do
    if seen [number] then
        out = 0
    else
        seen [number] = 1
    end
end
print (out)

Find the full program on GitHub.