# Operations on Sets

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.

• I'm actually not clear on "actually represents a set". How can one determine whether a proposed representation represents the given set? Does it have to be that a representation of a set is always character for character the same? Python fails the previous point because it lists elements in an arbitrary order. What can the elements of these sets be? (Sorry, I should have asked these all while the question was sandboxed).
– xnor
Jul 11 '14 at 2:50
• Could you explain what some of these terms for those that are not so familiar with them? Jul 11 '14 at 3:01
• Can you clarify "You may not use built-in functions to do the work for you"? Does this mean no built-in functions whatsoever or no built-in functions specifically designed for handling sets? Jul 11 '14 at 15:44
• @DigitalTrauma I mean no built-ins specifically for computing unions, intersections, etc. You may, for example, use eval() to convert a string to your language's representation of a set. Jul 11 '14 at 17:52
• So, I'm guessing T-SQL is out of the running here? Jul 11 '14 at 21:02

### 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]  > 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
}*         #   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


## 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],] [1, 2, 3, 8]$ ruby set.rb complement [[1,2,3,6,7],[7,2,1,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]]]

• you can swap .compact for -[p] iirc Dec 5 '17 at 1:36

# 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 $ 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!

• Well played ... using only the first character to know which command to use. Jul 11 '14 at 3:41
• I guess there is a shorter product implementation in GolfScript ;-) Jul 11 '14 at 4:21
• Doesn't this solution violate the You may not use built-in functions to do the work for you.? Jul 11 '14 at 4:42
• @Howard I interpret that as: no set(input())|set(input()) in python (as an example). Jul 11 '14 at 5:41
• @Quincunx Which - if you translate the python to GolfScript - is exactly what the code does. Jul 11 '14 at 6:48

# 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$


## 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


## PowerShell, 131

param($o,[array]$a,[array]$b)switch($o){'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


# 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)  
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


# 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


# 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
`