Operations on Sets

Question

Note: I have accepted an answer, but I'm willing to accept a better answer if it comes.

Write a program that computes operations on sets. You may take input either from standard input or from command line arguments. Your program must be able to compute unions, intersections, relative complements, and cartesian products. Output should be the result of these operations.

You may not use built-in functions to do the work for you.

Input Format

<A> and <B> represent sets. The format for sets can be anything that is convenient, as long as it actually represents a set (no taking advantage of this "looseness"). The elements of a set don't always have to be in the same order because sets aren't ordered. You define what kind of object these elements can be (integers, letters, ...).

• Union: union <A> <B>
• Intersection: intersect <A> <B>
• Relative complement (difference of sets): complement <A> <B>
• Cartesian product: product <A> <B> (format for ordered pairs can be anything convenient -- don't take advantage of this "looseness" either)

For info on what these operations even are, see the Wikipedia page on it.

Answer 1

GolfScript, 73 characters

.' '?:^>~`"~{:^1$?0<{[^]+}*}/
{\\`{[\\]}+/}+%
{?0<!}+,
{?0<}+,"n/^2/2-=~`

Uses non of the GolfScript set operators and should work on all valid GolfScript objects. Input must be given on STDIN, for format see also the online examples.

> union [1 2 3] [2 3 4]
[1 2 3 4]

> intersect [1 2 3] [2 3 4]
[2 3]

> complement [1 2 3] [2 3 4]
[1]

> product [1 2 3] [2 3 4]
[[1 2] [1 3] [1 4] [2 2] [2 3] [2 4] [3 2] [3 3] [3 4]]

The code does not use GolfScript's set operators but implements them using loops.

.' '?        # find the first space character in the input
:^>          # save the position to variable ^ and remove from start of string
~            # evaluate the string (i.e. get two sets as arguments)
`            # transform the second set into a string
"..."n/      # generates an array of 4 strings which represent the set operations
             # (see below)
^2/2-        # take position of the first space (i.e. length of the operator)
             # divide by two, subtract two (i.e. union->0, intersect->2, 
             # complement->3, product->1)
=~           # take the corresponding command string and evaluate on the arguments
`            # transform the result back into a string representation

### union
~{           # evaluate the second argument (i.e. revert the ` operation)
             # and loop over all items
  :^         #   save item to variable ^
  1$?        #   is it contained in the first set?
  0<{        #   if no then
    [^]+     #     add to set
  }*         #   end if
}/           # end loop

### intersection
{            # prepend second argument to code block {...}+ and filter the first set
  ?0<!       #   is the current item contained in the second set? if yes, keep
}+,          # end filter block

### complement
{            # prepend second argument to code block {...}+ and filter the first set
  ?0<!       #   is the current item contained in the second set? if no, keep
}+,          # end filter block

### product
{            # prepend second argument to code block {...}+ and map on first set
  \`{        #   take current item and prepend to code block `{...}+ and iterate
    [\]      #     swap both items (item of second set + item of first set) and
             #     build a tuple of them
  }+/        #   end loop
}+%          # end map

Answer 2

Ruby, 97 characters

$_,a=$*;A,B=eval a
p (~/c/?B.map{|i|~/d/?A.map{|j|[i,j]}:!A.index(i)^~/m/?p: i}:A+B).uniq.compact

Usage examples:

$ ruby set.rb union [[1,2,3],[8]]
[1, 2, 3, 8]
$ ruby set.rb complement [[1,2,3,6,7],[7,2,1,5]]
[5]
$ ruby set.rb intersect [[1,2,3,6,7],[7,2,1,5]]
[7, 2, 1]
$ ruby set.rb product [[1,2],[7,5,2]]
[[[7, 1], [7, 2]], [[5, 1], [5, 2]], [[2, 1], [2, 2]]]

Answer 3

GolfScript, 77 characters

(\~@99-:x{6x={&}{13x={'"#{['@','*+'].product ['+\','*+']}"'+~}{|}if}if}{-}if`

Sample inputs and outputs:

$ echo "union [1 2 3] [2 3 4]" | golfscript setops.gs
[1 2 3 4]
$ echo "intersect [1 2 3] [2 3 4]" | golfscript setops.gs
[2 3]
$ echo "complement [1 2 3] [2 3 4]" | golfscript setops.gs
[1]
$ echo "product [1 2 3] [2 3 4]" | golfscript setops.gs
"[[1, 2], [1, 3], [1, 4], [2, 2], [2, 3], [2, 4], [3, 2], [3, 3], [3, 4]]"

---

Okay, now time to explain this gobbledygook. First, here's an explanation of how it chooses which one of the four blocks (union, intersect, complement, product) to execute.

I noticed something convenient about these commands. They each begin with a unique letter (u, i, c, p). Therefore, we only care about this first letter.

Now, to make the code even shorter, these can be converted into ASCII codes (117, 105, 99, 112). Here's an explanation of the main logic of the program:

(     # grab the ASCII code of the first letter of the input string
\~    # evaluate the rest of the string. GS will ignore "nion", "tersect", etc.
@     # stack is now [A B CMD]
99-:x # subtract 99 for shorter code. Now 'uicp' maps to [18 6 0 13]

After this comes a huge chain of ifs. With the set operation logic removed, it looks like this:

{6x={INTERSECT_CODE}{13x={PRODUCT_CODE}{UNION_CODE}if}if}{COMPLEMENT_CODE}if`

Converted to a more readable C-like format, it looks like this:

if (x) {
  if (x == 6) {
    INTERSECT_CODE
  } else {
    if (x == 13) {
      PRODUCT_CODE
    } else {
      // x must be 18
      UNION_CODE
    }
  }
} else {
  // x is 0
  COMPLEMENT_CODE
}

Now, it's just a matter of looking at the code for the set operations. Most of them are fairly straightforwards: & for intersect, | for union, and - for complement. However, GolfScript doesn't have a built-in product operator, so I had to build some Ruby code for that. Here's an explanation of that mess:

'"#{['         # stack: [1 2 3] [2 3 4] '"#{['
@','*+         # stack: [2 3 4] '"#{[1,2,3'
'].product ['+ # stack: [2 3 4] '"#{[1,2,3].product ['
\','*+         # stack: '"#{[1,2,3].product [2,3,4'
']}"'+         # stack: '"#{[1,2,3].product [2,3,4]}"'
~              # evaluate

Simply tack on a ` to show array output correctly, and it's done!

Answer 4

Bash+coreutils, 200 bytes

I'm not exactly sure what "You may not use built-in functions to do the work for you" means, but I am assuming it means no use of APIs specifically designed for handling sets. Some of the coreutils used here might be considered to come close, but I am asserting that these utilities operate on files and lines of files, and not specifically on sets:

f()(tr \  \\n<<<$1|sort -u)
c()(comm -2$1 <(echo "$a") <(echo "$b"))
a=`f "$2"`
b=`f "$3"`
case $1 in
u*)sort -u<<<"$a
$b";;i*)c 1;;c*)c 3;;p*)eval printf '%s\\n' {${a//$'\n'/,}},{${b//$'\n'/,}};;esac

The union, intersect and complement cases are relatively uninteresting calls to sort and comm. The product case uses bash brace expansion. For example echo {1,2,3},{a,b} produces the output 1,a 1,b 2,a 2,b 3,a 3,b. The catch here is that brace expansion normally occurs before variable expansion, so the whole thing must be evaled so the variables are effectively expanded first.

Example output:

$ ./sets.sh union "1 2 3 4 3 2 1" "2 4 6 4 6"
1
2
3
4
6
$ ./sets.sh intersect "1 2 3 4 3 2 1" "2 4 6 4 6"
2
4
$ ./sets.sh complement "1 2 3 4 3 2 1" "2 4 6 4 6"
1
3
$ ./sets.sh product "1 2 3 4 3 2 1" "2 4 6 4 6"
1,2
1,4
1,6
2,2
2,4
2,6
3,2
3,4
3,6
4,2
4,4
4,6
$ 

Answer 5

Axiom, 186 bytes

union(a,b)==removeDuplicates concat(a,b)
intersection(a,b)==[x for x in a|member?(x,b)]
complement(a,b)==[x for x in a|~member?(x,b)]
product(a,b)==concat[[[x,y]for y in b]for x in a]

All input for above function has to be List [of ints] that have not repetition (for to be a set).

Here the necessary functions for see if one List is a set and for see if two set are equals:

isEq?(a,b)==(#a~=#b=>false;(sort(a)=sort(b))@Boolean)
isSet?(a)==isEq?(removeDuplicates(a),a)

Some results

(9) -> union([1,2,3], [2,3,4])
   (9)  [1,2,3,4]
                                               Type: List PositiveInteger
(10) -> intersection([1,2,3], [2,3,4])
   (10)  [2,3]
                                               Type: List PositiveInteger
(11) -> complement([1,2,3], [2,3,4])
   (11)  [1]
                                               Type: List PositiveInteger
(12) -> product([1,2,3], [2,3,4])
   (12)  [[1,2],[1,3],[1,4],[2,2],[2,3],[2,4],[3,2],[3,3],[3,4]]
                                          Type: List List PositiveInteger

Answer 6

APL NARS 100 chars

union←{∪⍺,⍵}⋄intersection←{(⍺∊⍵)/⍺}⋄complement←{(∼⍺∊⍵)/⍺}
∇r←x product y;i;j
r←⍬⋄:for i:in x⋄:for j:in y⋄r←r,⊂(i,j)⋄:endfor⋄:endfor

the symbol ∪ in union above means "each elment appear one time only" so it doesn't make union. They are about 135 chars but if i cut the names of anonimous functions it would be 100 chars(25+19+56=100 chars). Test

  1 2 3 union 2 3 4
1 2 3 4 
  1 2 3 intersection 2 3 4
2 3 
  1 2 3 complement 2 3 4
1 
  1 2 3 product 2 3 4
1 2  1 3  1 4  2 2  2 3  2 4  3 2  3 3  3 4 

The APL functions for doing above union, intersection, complement and product could be:

  sysunion←∪
  sysintersection←∩
  syscomplement←∼
  sysproduct←{,⍺∘.,⍵}
  1 2 3 sysunion 2 3 4
1 2 3 4 
  1 2 3 sysintersection 2 3 4
2 3 
  1 2 3 syscomplement 2 3 4
1 
  1 2 3 sysproduct 2 3 4
1 2  1 3  1 4  2 2  2 3  2 4  3 2  3 3  3 4 
  x←1 3
  y←2 3
  x sysproduct y
1 2  1 3  3 2  3 3

Answer 7

R, 105 bytes

function(A,B)list(U<-unique(c(A,B)),U[U%in%A&U%in%B],A[!A%in%B],cbind(rep(A,sum(B|1)),rep(B,e=sum(A|1))))

Try it online!

Returns a list with four elements, the Union, the Intersection, the Difference, and the Cartesian Product, in that order.

Takes input as an R vector of integers.

The Union is the unique values in the concatenation of the two vectors, U=unique(c(A,B)).

The Intersection is the subset of the Union where x in A & x in B, so U[U%in%A&U%in%B].

The Set Difference is those a in A where a notin B, so A[!A%in%B]

The Cartesian Product is returned as a matrix where each row is an ordered pair. It repeats A |B| times and the elements of B |A| times each, then binds them together as matrix columns, i.e.:

cbind(                # bind as matrix columns
 rep(A,sum(B|1)),     # repeat A |B| times (concatenate |B| copies of A)
 rep(B,e=sum(A|1)))   # repeat each element of B |A| times

Answer 8

Haskell Prelude Control.Applicative, 96 bytes

Not sure whether this is considered cheating, but:

union=liftA2(||)
intersect=liftA2(&&)
complement f=liftA2(&&)f.(not.)
product f g (x,y)=f x&&g y

If allowed, product could be curried to save extra 1 byte.

The key idea is to implement sets as a predicate (a -> Bool) that returns True if the element is present. This can represent not only finite sets, but also infinite sets.

Being possibly infinite, the outputted set cannot be represented in a string, but it can be queried:

Prelude Control.Applicative> union (\_->False) (\_->False) 0
False
Prelude Control.Applicative> union (\_->False) (\_->True) 0
True
Prelude Control.Applicative> union (\_->False) even 0
True
Prelude Control.Applicative> union (\_->False) odd 0
False
Prelude Control.Applicative> union even odd 0
True
Prelude Control.Applicative> intersect (\_->False) (\_->True) 0
False
Prelude Control.Applicative> intersect (\_->True) even 0
True
Prelude Control.Applicative> intersect odd even 0
False
Prelude Control.Applicative> complement (\_->True) even 0
False
Prelude Control.Applicative> complement (\_->True) odd 0
True
Prelude Control.Applicative> product even odd (0,0)
False
Prelude Control.Applicative> product even odd (0,1)
True
Prelude Control.Applicative> product even odd (1,1)
False

Answer 9

PowerShell, 131

param($o,[array]$a,[array]$b)switch($o[0]){'u'{$a+$b|sort -u}'i'{$a|?{$_-in$b}}'c'{$b|?{$_-notin$a}}'p'{$a|%{$x=$_
$b|%{"$x,$_"}}}}

Fairly straightforward rendition of all the operators. Sets are given as comma-separated lists and the script takes arguments:

PS> .\set.ps1 union 1,2,3 8
1
2
3
8
PS> .\set.ps1 intersect 1,2,3,6,7 7,2,1,5
1
2
7
PS> .\set.ps1 complement 1,2,3,6,7 7,2,1,5
5
PS> .\set.ps1 product 1,2 7,5
1,7
1,5
2,7
2,5