Symmetric difference
You are encouraged to solve this task according to the task description, using any language you may know.
Given two sets A and B, where A contains:
- John
- Bob
- Mary
- Serena
and B contains:
- Jim
- Mary
- John
- Bob
compute
That is, enumerate the items that are in A or B but not both. This set is called the symmetric difference of A and B.
Optionally, give the individual differences ( and ) as well.
Note: If your code uses lists of items to represent sets then ensure duplicate items in lists are correctly handled. For example two lists representing sets of a = ["John", "Serena", "Bob", "Mary", "Serena"] and b = ["Jim", "Mary", "John", "Jim", "Bob"] should produce the result of just two strings: ["Serena", "Jim"], in any order.
Ada
Ada has the lattice operation xor predefined on Boolean, modular types, 1D arrays, set implementations from the standard library. The provided solution is uses arrays: <lang Ada> with Ada.Text_IO; use Ada.Text_IO;
procedure Test_XOR is
type Person is (John, Bob, Mary, Serena, Jim);
type Group is array (Person) of Boolean;
procedure Put (Set : Group) is
First : Boolean := True;
begin
for I in Set'Range loop
if Set (I) then
if First then
First := False;
else
Put (',');
end if;
Put (Person'Image (I));
end if;
end loop;
end Put;
A : Group := (John | Bob | Mary | Serena => True, others => False); B : Group := (Jim | Mary | John | Bob => True, others => False);
begin
Put ("A xor B = "); Put (A xor B); New_Line;
Put ("A - B = "); Put (A and not B); New_Line;
Put ("B - A = "); Put (B and not A); New_Line;
end Test_XOR; </lang> Sample output:
A xor B = SERENA,JIM A - B = SERENA B - A = JIM
AutoHotkey
<lang autohotkey>setA = John, Bob, Mary, Serena setB = Jim, Mary, John, Bob MsgBox,, Singles, % SymmetricDifference(setA, setB)
setA = John, Serena, Bob, Mary, Serena setB = Jim, Mary, John, Jim, Bob MsgBox,, Duplicates, % SymmetricDifference(setA, setB)
- ---------------------------------------------------------------------------
SymmetricDifference(A, B) { ; returns the symmetric difference of A and B
- ---------------------------------------------------------------------------
StringSplit, A_, A, `,, %A_Space%
Loop, %A_0%
If Not InStr(B, A_%A_Index%)
And Not InStr(Result, A_%A_Index%)
Result .= A_%A_Index% ", "
StringSplit, B_, B, `,, %A_Space%
Loop, %B_0%
If Not InStr(A, B_%A_Index%)
And Not InStr(Result, B_%A_Index%)
Result .= B_%A_Index% ", "
Return, SubStr(Result, 1, -2)
}</lang> Message boxes show:
Singles --------------------------- Serena, Jim OK
Duplicates --------------------------- Serena, Jim OK
Bash
<lang bash>uniq() {
u=("$@")
for ((i=0;i<${#u[@]};i++)); do
for ((j=i+1;j<=${#u[@]};j++)); do
[ "${u[$i]}" = "${u[$j]}" ] && unset u[$i]
done
done
u=("${u[@]}")
}
a=(John Serena Bob Mary Serena) b=(Jim Mary John Jim Bob)
uniq "${a[@]}" au=("${u[@]}") uniq "${b[@]}" bu=("${u[@]}")
ab=("${au[@]}") for ((i=0;i<=${#au[@]};i++)); do
for ((j=0;j<=${#bu[@]};j++)); do
[ "${ab[$i]}" = "${bu[$j]}" ] && unset ab[$i]
done
done ab=("${ab[@]}")
ba=("${bu[@]}") for ((i=0;i<=${#bu[@]};i++)); do
for ((j=0;j<=${#au[@]};j++)); do
[ "${ba[$i]}" = "${au[$j]}" ] && unset ba[$i]
done
done ba=("${ba[@]}")
sd=("${ab[@]}" "${ba[@]}")
echo "Set A = ${a[@]}" echo " = ${au[@]}" echo "Set B = ${b[@]}" echo " = ${bu[@]}" echo "A - B = ${ab[@]}" echo "B - A = ${ba[@]}" echo "Symmetric difference = ${sd[@]}"</lang> Output:
Set A = John Serena Bob Mary Serena
= John Bob Mary Serena
Set B = Jim Mary John Jim Bob
= Mary John Jim Bob
A - B = Serena
B - A = Jim
Symmetric difference = Serena Jim
C
<lang c>#include <stdio.h>
- include <string.h>
- include <stdlib.h>
const char mary[]="Mary"; const char bob[]="Bob"; const char jim[]="Jim"; const char john[]="John"; const char serena[]="Serena";
const char *setA[] = {john,bob,mary,serena}; const char *setB[] = {jim,mary,john,bob};
- define XSET(j) j, (sizeof(j)/sizeof(*j))
- define TALLOC(n,typ) malloc(n*sizeof(typ))
typedef enum {
esdDIFFERENCE, esdSYMMETRIC } EsdFunction;
/** * * * * * * * * * * * * * * * * * * * *
* return value is difference or symmetric difference set * its size is returned in sym_size * f determinse whether it is a symmetric difference, or normal difference * * * * * * * * * * * * * * * * * * * * **/
const char ** symmdiff( int *sym_size, EsdFunction f, const char *setA[], int setAsize, const char *setB[], int setBsize) {
int union_size; int max_union_size; int diff_size; const char **union_set; const char **diff_set; int *union_xor; int ix, ixu;
max_union_size = setAsize + setBsize; union_set = TALLOC(max_union_size, const char *); union_xor = TALLOC(max_union_size, int);
/* I'm assuming here that setA has no duplicates,
* i.e. is a set in mathematical sense */
for (ix=0; ix<setAsize; ix++) {
union_set[ix] = setA[ix];
union_xor[ix] = 1;
}
diff_size = union_size = setAsize;
for (ix=0; ix<setBsize; ix++) {
for (ixu=0; ixu<union_size; ixu++) {
if (union_set[ixu] == setB[ix]) break;
}
if (ixu < union_size) { /* already in union */
union_xor[ixu] = 1-union_xor[ixu];
diff_size--;
}
else { /* not already in union -add */
if (f == esdSYMMETRIC) {
union_set[ixu] = setB[ix];
union_xor[ixu] = 1;
union_size++;
diff_size++;
}
}
}
/* Put results in symdiff set */
diff_set = TALLOC(diff_size, const char *);
ix = 0;
for (ixu=0; ixu<union_size; ixu++) {
if (union_xor[ixu]) {
if (ix == diff_size) {
printf("Short of space in diff_set\n");
exit(1);
}
diff_set[ix] = union_set[ixu];
ix++;
}
}
*sym_size = diff_size;
free(union_xor);
free(union_set);
return diff_set;
}
void printSet (const char *set[], int ssize)
{
int ix;
printf(" = {");
for (ix=0;ix<ssize; ix++) {
printf( "%s ", set[ix]);
}
printf("}\n");
}
int main() {
const char **symset; int sysize;
printf ("A symmdiff B");
symset = symmdiff( &sysize, esdSYMMETRIC, XSET(setA), XSET(setB));
printSet(symset, sysize);
free(symset);
printf ("A - B");
symset = symmdiff( &sysize, esdDIFFERENCE, XSET(setA), XSET(setB));
printSet(symset, sysize);
printf ("B - A");
symset = symmdiff( &sysize, esdDIFFERENCE, XSET(setB), XSET(setA));
printSet(symset, sysize);
free(symset);
return 0;
}</lang> Output
A symmdiff B = {Serena Jim }
A - B = {Serena }
B - A = {Jim }
C++
<lang cpp>#include <iostream>
- include <set>
- include <algorithm>
- include <iterator>
using namespace std ;
int main( ) {
string setA[ ] = { "John" , "Bob" , "Mary" , "Serena" } ;
string setB[ ] = { "Jim" , "Mary" , "John" , "Bob" } ;
set<string> firstSet ( setA , setA + 4 ) , secondSet( setB , setB + 4 ) , symdiff ;
set_symmetric_difference ( firstSet.begin( ) , firstSet.end( ) ,
secondSet.begin( ) , secondSet.end( ) ,
inserter( symdiff, symdiff.begin( ) ) ) ;
copy( symdiff.begin( ) , symdiff.end( ) , ostream_iterator<string>( cout , " " )) ;
cout << endl ;
return 0 ;
}</lang> Output: Jim Serena
Clojure
<lang clojure>(use '[clojure.set])
(defn symmetric-difference [s1 s2]
(union (difference s1 s2) (difference s2 s1)))
(symmetric-difference #{:john :bob :mary :serena} #{:jim :mary :john :bob})</lang>
Common Lisp
<lang lisp>(defun symmetric-difference (l0 l1)
(union (set-difference l0 l1)
(set-difference l1 l0)))
(symmetric-difference '(John Bob Mary Serena) '(Jim Mary John Bob))</lang> Output
(SERENA JIM)
D
Works with sets of any type (as long as they are of the same type) <lang d>import std.stdio; import std.algorithm;
class Set(T) {
alias Set!(T) SetT; T[] items;
this(T[] items) {
this.items = items;
}
SetT opSub(SetT other) {
T[] array;
foreach(a; items)
if(find(other.items, a).length == 0)
array ~= a;
return new SetT(array);
}
SetT opAdd(SetT other) {
return new SetT(this.items ~ (other - this).items);
}
}
T symDiff(T)(T left, T right) {
return (left - right) + (right - left);
}
void main() {
auto A = new Set!(string)(["John", "Bob", "Mary", "Serena"]); auto B = new Set!(string)(["Jim", "Mary", "John", "Bob"]);
writefln(" A/B: [%s]", (A - B).items);
writefln(" B/A: [%s]", (B - A).items);
writefln("A symdiff B: [%s]", (symDiff(A, B)).items);
}</lang> Output:
A/B: [Serena]
B/A: [Jim]
A symdiff B: [Serena Jim]
Factor
<lang factor>: symmetric-diff ( a b -- c )
[ diff ] [ swap diff ] 2bi append ;
{ "John" "Bob" "Mary" "Serena" } { "Jim" "Mary" "John" "Bob" } symmetric-diff .</lang>
F#
<lang fsharp>> let a = Set.ofList ["John"; "Bob"; "Mary"; "Serena"] let b = Set.ofList ["Jim"; "Mary"; "John"; "Bob"];;
val a : Set<string> = set ["Bob"; "John"; "Mary"; "Serena"] val b : Set<string> = set ["Bob"; "Jim"; "John"; "Mary"]
> (a-b) + (b-a);; val it : Set<string> = set ["Jim"; "Serena"]</lang> Or, if you don't like the infix operators: <lang fsharp>> Set.union (Set.difference a b) (Set.difference b a);; val it : Set<string> = set ["Jim"; "Serena"]</lang>
Haskell
<lang haskell>import Data.Set
a = fromList ["John", "Bob", "Mary", "Serena"] b = fromList ["Jim", "Mary", "John", "Bob"]
(-|-) :: Ord a => Set a -> Set a -> Set a (-|-) x y = (x \\ y) `union` (y \\ x)
-- Equivalently: (x `union` y) \\ (x `intersect` y)</lang>
Symmetric difference:
<lang haskell>*Main> a -|- b fromList ["Jim","Serena"]</lang>
Individual differences:
<lang haskell>*Main> a \\ b fromList ["Serena"]
- Main> b \\ a
fromList ["Jim"]</lang>
HicEst
<lang HicEst>CALL SymmDiff("John,Serena,Bob,Mary,Serena,", "Jim,Mary,John,Jim,Bob,") CALL SymmDiff("John,Bob,Mary,Serena,", "Jim,Mary,John,Bob,")
SUBROUTINE SymmDiff(set1, set2)
CHARACTER set1, set2, answer*50 answer = " " CALL setA_setB( set1, set2, answer ) CALL setA_setB( set2, set1, answer ) WRITE(Messagebox,Name) answer ! answer = "Serena,Jim," in both cases
END
SUBROUTINE setA_setB( set1, set2, differences )
CHARACTER set1, set2, differences, a*100 a = set1 EDIT(Text=a, $inLeXicon=set2) ! eg a <= $John,Serena,$Bob,$Mary,Serena, EDIT(Text=a, Right="$", Mark1, Right=",", Mark2, Delete, DO) ! Serena,Serena, EDIT(Text=a, Option=1, SortDelDbls=a) ! Option=1: keep case; Serena, differences = TRIM( differences ) // a
END</lang>
Icon and Unicon
Icon
Set operations are built into Icon/Unicon. <lang Icon>procedure main()
a := set(["John", "Serena", "Bob", "Mary", "Serena"]) b := set(["Jim", "Mary", "John", "Jim", "Bob"])
showset("a",a) showset("b",b) showset("(a\\b) \xef (b\\a)",(a -- b) ++ (b -- a)) showset("(a\\b)",a -- b) showset("(b\\a)",b -- a) end
procedure showset(n,x)
writes(n," = { ")
every writes(!x," ")
write("}")
return
end</lang>
Sample output:
a = { Serena Mary Bob John }
b = { Mary Bob Jim John }
(a\b) ∩ (b\a) = { Serena Jim }
(a\b) = { Serena }
(b\a) = { Jim }
Unicon
This Icon solution works in Unicon.
J
<lang j> A=: ;:'John Serena Bob Mary Serena'
B=: ;:'Jim Mary John Jim Bob'
(A-.B) ,&~. (B-.A) NB. Symmetric Difference
┌──────┬───┐ │Serena│Jim│ └──────┴───┘
A (-. ,&~. -.~) B NB. Tacit equivalent
┌──────┬───┐ │Serena│Jim│ └──────┴───┘
A -.&~. B NB. items in A but not in B
┌──────┐ │Serena│ └──────┘
B -.&~. A NB. items in B but not in A
┌───┐ │Jim│ └───┘</lang>
Java
<lang java>import java.util.Arrays; import java.util.HashSet; import java.util.Set;
public class SymmetricDifference {
public static void main(String[] args) {
Set<String> setA = new HashSet<String>(Arrays.asList("John", "Serena", "Bob", "Mary", "Serena"));
Set<String> setB = new HashSet<String>(Arrays.asList("Jim", "Mary", "John", "Jim", "Bob"));
// Present our initial data set
System.out.println("In set A: " + setA);
System.out.println("In set B: " + setB);
// Get our individual differences.
Set<String> notInSetA = new HashSet<String>(setB);
notInSetA.removeAll(setA);
Set<String> notInSetB = new HashSet<String>(setA);
notInSetB.removeAll(setB);
// The symmetric difference is the concatenation of the two individual differences
Set<String> symmetricDifference = new HashSet<String>(notInSetA);
symmetricDifference.addAll(notInListB);
// Present our results
System.out.println("Not in set A: " + notInSetA);
System.out.println("Not in set B: " + notInSetB);
System.out.println("Symmetric Difference: " + symmetricDifference);
}
}</lang>
This outputs:
In set A: [Mary, Bob, Serena, John] In set B: [Mary, Bob, Jim, John] Not in set A: [Jim] Not in set B: [Serena] Symmetric Difference: [Jim, Serena]
JavaScript
for the print() function.
Uses the Array function unique() defined here.
<lang javascript>// in A but not in B
function relative_complement(A, B) {
return A.filter(function(elem) {return B.indexOf(elem) == -1});
}
// in A or in B but not in both function symmetric_difference(A,B) {
return relative_complement(A,B).concat(relative_complement(B,A));
}
var a = ["John", "Serena", "Bob", "Mary", "Serena"].unique(); var b = ["Jim", "Mary", "John", "Jim", "Bob"].unique();
print(a); print(b); print(symmetric_difference(a,b));</lang> outputs
Bob,John,Mary,Serena Bob,Jim,John,Mary Serena,Jim
Logo
<lang logo> to diff :a :b [:acc []]
if empty? :a [output sentence :acc :b] ifelse member? first :a :b ~ [output (diff butfirst :a remove first :a :b :acc)] ~ [output (diff butfirst :a :b lput first :a :acc)]
end
make "a [John Bob Mary Serena] make "b [Jim Mary John Bob]
show diff :a :b ; [Serena Jim] </lang>
Lua
<lang lua>A = { ["John"] = true, ["Bob"] = true, ["Mary"] = true, ["Serena"] = true } B = { ["Jim"] = true, ["Mary"] = true, ["John"] = true, ["Bob"] = true }
A_B = {} for a in pairs(A) do
if not B[a] then A_B[a] = true end
end
B_A = {} for b in pairs(B) do
if not A[b] then B_A[b] = true end
end
for a_b in pairs(A_B) do
print( a_b )
end for b_a in pairs(B_A) do
print( b_a )
end</lang>
MATLAB
If you are using a vector of numbers as the sets of which you like to find the symmetric difference, then there are already utilities that operate on these types of sets built into MATLAB. This code will take the symmetric difference of two vectors:
<lang MATLAB>>> [setdiff([1 2 3],[2 3 4]) setdiff([2 3 4],[1 2 3])]
ans =
1 4</lang>
On the other hand, if you are using cell-arrays as sets, there are no built-in set utilities to operate on those data structures, so you will have to program them yourself. Also, the only way to have a set of strings is to put each string in a cell of a cell array, trying to put them into a vector will cause all of the strings to concatenate.
This code will return the symmetric difference of two sets and will take both cell arrays and vectors (as in the above example) as inputs.
<lang MATLAB>function resultantSet = symmetricDifference(set1,set2)
assert( ~xor(iscell(set1),iscell(set2)), 'Both sets must be of the same type, either cells or matricies, but not a combination of the two' );
%% Helper function definitions
%Define what set equality means for cell arrays
function trueFalse = equality(set1,set2)
if xor(iscell(set1),iscell(set2)) %set1 or set2 is a set and the other isn't
trueFalse = false;
return
elseif ~(iscell(set1) || iscell(set2)) %set1 and set2 are not sets
if ischar(set1) && ischar(set2) %set1 and set2 are chars or strings
trueFalse = strcmp(set1,set2);
elseif xor(ischar(set1),ischar(set2)) %set1 or set2 is a string but the other isn't
trueFalse = false;
else %set1 and set2 are not strings
if numel(set1) == numel(set2) %Since they must be matricies if the are of equal cardinality then they can be compaired
trueFalse = all((set1 == set2));
else %If they aren't of equal cardinality then they can't be equal
trueFalse = false;
end
end
return
else %set1 and set2 are both sets
for x = (1:numel(set1))
trueFalse = false;
for y = (1:numel(set2))
%Compair the current element of set1 with every element
%in set2
trueFalse = equality(set1{x},set2{y});
%If the element of set1 is equal to the current element
%of set2 remove that element from set2 and break out of
%this inner loop
if trueFalse
set2(y) = [];
break
end
end
%If the loop completes without breaking then the current
%element of set1 is not contained in set2 therefore the two
%sets are not equal and we can return an equality of false
if (~trueFalse)
return
end
end
%If, after checking every element in both sets, there are still
%elements in set2 then the two sets are not equivalent
if ~isempty(set2)
trueFalse = false;
end
%If the executation makes it here without the previous if
%statement evaluating to true, then this function will return
%true.
end
end %equality
%Define the relative compliment for cell arrays
function set1 = relativeComplement(set1,set2)
for k = (1:numel(set2))
if numel(set1) == 0
return
end
j = 1;
while j <= numel(set1)
if equality(set1{j},set2{k})
set1(j) = [];
j = j-1;
end
j = j+1;
end
end
end %relativeComplement
%% The Symmetric Difference Algorithm
if iscell(set1) && iscell(set2)
resultantSet = [relativeComplement(set1,set2) relativeComplement(set2,set1)];
else
resultantSet = [setdiff(set1,set2) setdiff(set2,set1)];
end
resultantSet = unique(resultantSet); %Make sure there are not duplicates
end %symmetricDifference</lang>
Solution Test: <lang MATLAB>>> A = {'John','Bob','Mary','Serena'}
A =
'John' 'Bob' 'Mary' 'Serena'
>> B = {'Jim','Mary','John','Bob'}
B =
'Jim' 'Mary' 'John' 'Bob'
>> symmetricDifference(A,B)
ans =
'Serena' 'Jim' %Correct
>> symmetricDifference([1 2 3],[2 3 4])
ans =
1 4 %Correct</lang>
OCaml
<lang ocaml> let unique u =
let rec g u v = match u with [ ] -> v | x::q -> if List.exists (function y -> y=x) v then g q v else g q (x::v)
in g u [ ];;
let ( -| ) a b =
unique (List.filter (fun v -> not (List.mem v b)) a)
let ( -|- ) a b = (b -| a) @ (a -| b)</lang>
in the toplevel:
<lang ocaml># let a = [ "John"; "Bob"; "Mary"; "Serena" ]
and b = [ "Jim"; "Mary"; "John"; "Bob" ] ;;
val a : string list = ["John"; "Bob"; "Mary"; "Serena"] val b : string list = ["Jim"; "Mary"; "John"; "Bob"]
- a -|- b ;;
- : string list = ["Jim"; "Serena"]
- a -| b ;;
- : string list = ["Serena"]
- b -| a ;;
- : string list = ["Jim"]</lang>
Oz
Oz does not have a general set data type. We can implement some basic set operations in terms of list functions and use them to define the symmetric difference: <lang oz>declare
fun {SymDiff A B}
{Union {Diff A B} {Diff B A}}
end
%% implement sets in terms of lists
fun {MakeSet Xs}
set({Nub2 Xs nil})
end
fun {Diff set(A) set(B)}
set({FoldL B List.subtract A})
end
fun {Union set(A) set(B)}
set({Append A B})
end
%% --
fun {Nub2 Xs Ls}
case Xs of nil then nil
[] X|Xr andthen {Member X Ls} then {Nub2 Xr Ls}
[] X|Xr then X|{Nub2 Xr X|Ls}
end
end
in
{Show {SymDiff
{MakeSet [john bob mary serena]} {MakeSet [jim mary john bob]}}}
{Show {SymDiff
{MakeSet [john serena bob mary serena]} {MakeSet [jim mary john jim bob]}}} </lang>
Oz does have a type for finite sets of non-negative integers. This is part of the constraint programming support. For the given task, we could use it like this if we assume numbers instead of names: <lang oz>declare
fun {SymDiff A B}
{FS.union {FS.diff A B} {FS.diff B A}}
end
A = {FS.value.make [1 2 3 4]}
B = {FS.value.make [5 3 1 2]}
in
{Show {SymDiff A B}}</lang>
Perl
<lang perl>my @a = qw(John Serena Bob Mary Serena); my @b = qw(Jim Mary John Bob);
- Get the individual differences.
my @a_minus_b = setminus(\@a, \@b); my @b_minus_a = setminus(\@b, \@a);
- merge then together and remove possible duplicates
my @symmetric_difference = uniq(@a_minus_b, @b_minus_a);
- Present our results.
print 'List A: ', join(', ', @a),
"\nList B: ", join(', ', @b),
"\nA \\ B: ", join(', ', @a_minus_b),
"\nB \\ A: ", join(', ', @b_minus_a),
"\nSymmetric difference: ", join(', ', @symmetric_difference), "\n";
- Takes two array references. Returns a list of elements in the first
- array that aren't in the second.
sub setminus {
my ($a, $b) = @_;
# Convert $b to hash keys, so it's easier to search.
my %b;
@b{@$b} = ();
return grep !exists $b{$_}, @$a;
}
- take a list and return only uniq items
sub uniq {
my %saw;
return grep !$saw{$_}++, @_;
}</lang>
This outputs:
List A: John, Serena, Bob, Mary, Serena List B: Jim, Mary, John, Bob A \ B: Serena, Serena B \ A: Jim Symmetric difference: Serena, Jim
Perl 6
<lang Perl 6>my @firstnames = <John Serena Bob Mary Serena> ; my @secondnames = <Jim Mary John Jim Bob> ; my %infirstnames ; my %insecondnames ; for @firstnames -> $name {
%infirstnames{$name} = 0 ;
} for @secondnames -> $name {
%insecondnames{$name} = 0 ;
} my @symdifference ; for %infirstnames.keys -> $name {
push @symdifference , $name unless ( %insecondnames.exists( $name ) ) ;
} for %insecondnames.keys -> $name {
push @symdifference , $name unless ( %infirstnames.exists( $name ) ) ;
} say @symdifference.join( ", " ) ; </lang>
This produces the output:
Serena, Jim
PHP
<lang php><?php $a = array('John', 'Bob', 'Mary', 'Serena'); $b = array('Jim', 'Mary', 'John', 'Bob');
// Remove any duplicates $a = array_unique($a); $b = array_unique($b);
// Get the individual differences, using array_diff() $a_minus_b = array_diff($a, $b); $b_minus_a = array_diff($b, $a);
// Simply merge them together to get the symmetric difference $symmetric_difference = array_merge($a_minus_b, $b_minus_a);
// Present our results. echo 'List A: ', implode(', ', $a),
"\nList B: ", implode(', ', $b),
"\nA \\ B: ", implode(', ', $a_minus_b),
"\nB \\ A: ", implode(', ', $b_minus_a),
"\nSymmetric difference: ", implode(', ', $symmetric_difference), "\n";
?></lang>
This outputs:
List A: John, Bob, Mary, Serena List B: Jim, Mary, John, Bob A \ B: Serena B \ A: Jim Symmetric difference: Serena, Jim
PicoLisp
<lang PicoLisp>(de symdiff (A B)
(uniq (conc (diff A B) (diff B A))) )</lang>
Output:
(symdiff '(John Serena Bob Mary Serena) '(Jim Mary John Jim Bob)) -> (Serena Jim)
Prolog
Works with SWI-Prolog <lang Prolog>sym_diff :-
A = ['John', 'Serena', 'Bob', 'Mary', 'Serena'],
B = ['Jim', 'Mary', 'John', 'Jim', 'Bob'],
format('A : ~w~n', [A]),
format('B : ~w~n', [B]),
list_to_set(A, SA),
list_to_set(B, SB),
format('set from A : ~w~n', [SA]),
format('set from B : ~w~n', [SB]),
subtract(SA, SB, DAB),
format('difference A\\B : ~w~n', [DAB]),
subtract(SB, SA, DBA),
format('difference B\\A : ~w~n', [DBA]),
union(DAB, DBA, Diff),
format('symetric difference : ~w~n', [Diff]).
</lang> output : <lang html>A : [John,Serena,Bob,Mary,Serena] B : [Jim,Mary,John,Jim,Bob] set from A : [John,Serena,Bob,Mary] set from B : [Jim,Mary,John,Bob] difference A\B : [Serena] difference B\A : [Jim] symetric difference : [Serena,Jim] true.</lang>
PureBasic
Simple approach
<lang PureBasic>Dim A.s(3) Dim B.s(3)
A(0)="John": A(1)="Bob": A(2)="Mary": A(3)="Serena" B(0)="Jim": B(1)="Mary":B(2)="John": B(3)="Bob"
For a=0 To ArraySize(A()) ; A-B
For b=0 To ArraySize(B())
If A(a)=B(b)
Break
ElseIf b=ArraySize(B())
Debug A(a)
EndIf
Next b
Next a
For b=0 To ArraySize(B()) ; B-A
For a=0 To ArraySize(A())
If A(a)=B(b)
Break
ElseIf a=ArraySize(A())
Debug B(b)
EndIf
Next a
Next b</lang>
Solution using lists
<lang PureBasic>DataSection
SetA: Data.i 4 Data.s "John", "Bob", "Mary", "Serena" ; Data.i 5 ; Data.s "John", "Serena", "Bob", "Mary", "Serena" SetB: Data.i 4 Data.s "Jim", "Mary", "John", "Bob" ; Data.i 5 ; Data.s "Jim", "Mary", "John", "Jim", "Bob"
EndDataSection
Procedure addElementsToSet(List x.s())
;requires the read pointer to be set prior to calling by using 'Restore' Protected i, count Read.i count For i = 1 To count AddElement(x()) Read.s x() Next
EndProcedure
Procedure displaySet(List x.s())
Protected i, count = ListSize(x())
FirstElement(x())
For i = 1 To count
Print(x())
NextElement(x())
If i <> count: Print(", "): EndIf
Next
PrintN("")
EndProcedure
Procedure symmetricDifference(List a.s(), List b.s(), List result.s())
Protected ACount = ListSize(a()), BCount = ListSize(b()), prev.s
;this may leave set a and b in a different order
SortList(a(),#PB_Sort_Ascending)
SortList(b(),#PB_Sort_Ascending)
FirstElement(a())
FirstElement(b())
LastElement(result()) ;add to end of result()
While ACount > 0 Or BCount > 0
If ACount <> 0 And BCount <> 0 And a() = b()
ACount - 1: NextElement(a())
BCount - 1: NextElement(b())
ElseIf BCount = 0 Or (ACount <> 0 And a() < b())
AddElement(result()): result() = a()
prev = a(): Repeat: ACount - 1: NextElement(a()): Until ACount = 0 Or (a() <> prev)
ElseIf ACount = 0 Or (BCount <> 0 And a() > b())
AddElement(result()): result() = b()
prev = b(): Repeat: BCount - 1: NextElement(b()): Until BCount = 0 Or (b() <> prev)
EndIf
Wend
EndProcedure
If OpenConsole()
NewList a.s(): Restore SetA: addElementsToSet(a())
NewList b.s(): Restore SetB: addElementsToSet(b())
Print("Set A: "): displaySet(a())
Print("Set B: "): displaySet(b())
NewList sd.s()
symmetricDifference(a(), b(), sd())
Print("Symmetric Difference: "): displaySet(sd())
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
Input()
CloseConsole()
EndIf</lang> Sample output:
Set A: John, Bob, Mary, Serena Set B: Jim, Mary, John, Bob Symmetric Difference: Jim, Serena
Python
Python's set type supports difference as well as symmetric difference operators <lang python>>>> setA = set(["John", "Bob", "Mary", "Serena"]) >>> setB = set(["Jim", "Mary", "John", "Bob"]) >>> setA ^ setB # symmetric difference of A and B set(['Jim', 'Serena']) >>> setA - setB # elements in A that are not in B set(['Serena']) >>> setB - setA # elements in B that are not in A set(['Jim'])</lang>
R
<lang R> a <- c( "John", "Bob", "Mary", "Serena" ) b <- c( "Jim", "Mary", "John", "Bob" ) c(setdiff(b, a), setdiff(a, b))
a <- c("John", "Serena", "Bob", "Mary", "Serena") b <- c("Jim", "Mary", "John", "Jim", "Bob") c(setdiff(b, a), setdiff(a, b)) </lang> In both cases answer is: <lang R> [1] "Jim" "Serena" </lang>
REBOL
<lang rebol>a: [John Serena Bob Mary Serena] b: [Jim Mary John Jim Bob] difference a b </lang>
Result is
[Serena Jim]
REXX
<lang rexx> /*REXX program to find the symmetric difference (between two strings). */
a='["John", "Serena", "Bob", "Mary", "Serena"]' b='["Jim", "Mary", "John", "Jim", "Bob"]'
say 'list A=' a say 'list B=' b a.=0 /*falisify all the a.k._ booleans. */ a.1=a /*store listA as a stemmed array (1).*/ a.2=b /*store listA as a stemmed array (2).*/
do k=1 for 2 /*process both lists (stemmed array).*/ if left(a.k,1)=='[' then a.k=substr(a.k,2) if right(a.k,1)==']' then a.k=substr(a.k,1,length(a.k)-1)
do j=1 /*parse names in list, they may have blanks.*/ if left(a.k,1)==',' then a.k=substr(a.k,2) /*strip comma (if any)*/ if a.k= then leave /*Null? We're done.*/ parse var a.k '"' _ '"' a.k /*get the list's name.*/ a.k.j=_ /*store the list name.*/ a.k._=1 /*make a boolean val. */ end
a.k.0=j-1 /*number of list names*/ end
SD= /*symmetric diff list.*/ SD.=0 /*falsify all SD bools*/
do k=1 for 2 /*process both lists. */ ko=word(2 1,k) /*point to other list.*/
do j=1 for a.k.0 /*process list names. */
_=a.k.j /*a name in the list. */
if \a.ko._ & \SD._ then do /*if not in both... */
SD=SD '"'_'",' /*add to sym diff list*/
SD._=1 /*trueify a boolean. */
end
end
end
SD="["strip(space(SD),'T',",")']' /*clean up and bracket*/ say say 'symmetric difference='SD /*show and tell time. */
SA= /*symmetric AND list. */ SA.=0 /*falsify all SA bools*/
do j=1 for a.1.0 /*process A list names*/
_=a.1.j /*a name in the A list*/
if a.1._ & a.2._ & \SA._ then do /*if common to both...*/
SA=SA '"'_'",' /*add to sym AND list.*/
SA._=1 /*trueify a boolean. */
end
end
SA="["strip(space(SA),'T',",")']' /*clean up and bracket*/ say say ' symmetric AND='SA /*show and tell time. */ </lang> Output:
list A= ["John", "Serena", "Bob", "Mary", "Serena"]
list B= ["Jim", "Mary", "John", "Jim", "Bob"]
symmetric difference=["Serena", "Jim"]
symmetric AND=["John", "Bob", "Mary"]
Ruby
First, handle possible non-unique elements <lang ruby># with sets require 'set' a = Set["John", "Serena", "Bob", "Mary", "Serena"] b = Set["Jim", "Mary", "John", "Jim", "Bob"]
- or, with arrays
a = ["John", "Serena", "Bob", "Mary", "Serena"] b = ["Jim", "Mary", "John", "Jim", "Bob"] a.uniq! b.uniq!</lang>
Then, find the differences. Both Set and Array objects understand these operations: <lang ruby>a_not_b = a - b b_not_a = b - a sym_diff = a_not_b + b_not_a</lang>
Scala
<lang Scala> import scala.collection.mutable.Set import scala.collection.mutable.HashSet
val s1 = HashSet("John", "Serena", "Bob", "Mary", "Serena") val s2 = HashSet("Jim", "Mary", "John", "Jim", "Bob")
def complement(fst: Set[String], snd: Set[String]) =
fst.filter{ el => !snd.contains(el) }.toList
def symdiff(fst: Set[String], snd: Set[String]) =
HashSet(complement(fst, snd) ++ complement(snd, fst):_*)
println(s1) println(s2) println(symdiff(s1, s2)) </lang>
Output is
Set(John, Serena, Mary, Bob) Set(John, Mary, Jim, Bob) Set(Serena, Jim)
Smalltalk
<lang smalltalk>|A B| A := Set new. B := Set new. A addAll: #( 'John' 'Bob' 'Mary' 'Serena' ). B addAll: #( 'Jim' 'Mary' 'John' 'Bob' ).
( (A - B) + (B - A) ) displayNl.</lang>
Output is
Set ('Jim' 'Serena' )
Tcl
It's common to represent sets as an unordered list of elements. (It is also the most efficient representation.) The struct::set package contains operations for working on such sets-as-lists.
<lang tcl>package require struct::set
set A {John Bob Mary Serena} set B {Jim Mary John Bob}
set AnotB [struct::set difference $A $B] set BnotA [struct::set difference $B $A] set SymDiff [struct::set union $AnotB $BnotA]
puts "A\\B = $AnotB" puts "B\\A = $BnotA" puts "A\u2296B = $SymDiff"
- Of course, the library already has this operation directly...
puts "Direct Check: [struct::set symdiff $A $B]"</lang>
Produces this output:
A\B = Serena B\A = Jim A⊖B = Jim Serena Direct Check: Jim Serena
Ursala
<lang Ursala>a = <'John','Bob','Mary','Serena'> b = <'Jim','Mary','John','Bob'>
- cast %sLm
main =
<
'a': a, 'b': b, 'a not b': ~&j/a b, 'b not a': ~&j/b a, 'symmetric difference': ~&jrljTs/a b></lang>
output:
< 'a': <'John','Bob','Mary','Serena'>, 'b': <'Jim','Mary','John','Bob'>, 'a not b': <'Serena'>, 'b not a': <'Jim'>, 'symmetric difference': <'Jim','Serena'>>