Symmetric difference
From Rosetta Code
Symmetric difference is a programming task. Visitors like you are encouraged to solve it according to the task description, using any language they may happen to 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.
Contents |
[edit] 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;
}
Output
A symmdiff B = {Serena Jim }
A - B = {Serena }
B - A = {Jim }
[edit] C++
#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 ;
}
Output: Jim Serena
[edit] 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})
[edit] Common 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))
Output
(SERENA JIM)
[edit] D
Works with sets of any type (as long as they are of the same type)
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);
}
Output:
A/B: [Serena]
B/A: [Jim]
A symdiff B: [Serena Jim]
[edit] Factor
: symmetric-diff ( a b -- c )
[ diff ] [ swap diff ] 2bi append ;
{ "John" "Bob" "Mary" "Serena" } { "Jim" "Mary" "John" "Bob" } symmetric-diff .
[edit] 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)
Symmetric difference:
*Main> a -|- b
fromList ["Jim","Serena"]
Individual differences:
*Main> a \\ b
fromList ["Serena"]
*Main> b \\ a
fromList ["Jim"]
[edit] 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│
└───┘
[edit] Java
import java.util.*;
public class SymmetricDifference {
/** Checks for elements in the first collection that aren't in the second collection.
We call this for each list, so we can get the symmetric difference. */
public static <E> Collection<E> inLeftNotRight(Collection<E> leftList, Collection<E> rightList) {
Collection<E> notFound = new ArrayList<E>(leftList);
notFound.removeAll(rightList);
return notFound;
}
public static void main(String[] args) {
Collection<String> listA = Arrays.asList("John", "Bob", "Mary", "Serena");
Collection<String> listB = Arrays.asList("Jim", "Mary", "John", "Bob");
// Present our initial data set
System.out.println("In list A: " + listA);
System.out.println("In list B: " + listB);
// Get our individual differences.
Collection<String> notInListA = inLeftNotRight(listB, listA);
Collection<String> notInListB = inLeftNotRight(listA, listB);
// The symmetric difference is the concatenation of the two individual differences
Collection<String> symmetricDifference = new ArrayList<String>(notInListA);
symmetricDifference.addAll(notInListB);
// Present our results
System.out.println("Not in list A: " + notInListA);
System.out.println("Not in list B: " + notInListB);
System.out.println("Symmetric Difference: " + symmetricDifference);
}
}
This outputs:
In list A: [John, Bob, Mary, Serena] In list B: [Jim, Mary, John, Bob] Not in list A: [Jim] Not in list B: [Serena] Symmetric Difference: [Jim, Serena]
[edit] JavaScript
Works with: JavaScript version 1.6 Works with: Firefox version 1.5
Works with: SpiderMonkey for the print() function.
Uses the Array function unique() defined here.
// 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));
outputs
Bob,John,Mary,Serena Bob,Jim,John,Mary Serena,Jim
[edit] Logo
Works with: UCB 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]
[edit] OCaml
let ( -| ) a b =
List.filter (fun v -> not (List.mem v b)) a
let ( -|- ) a b = (b -| a) @ (a -| b)
in the toplevel:
# 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"]
[edit] 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:
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]}}}
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:
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}}
[edit] 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{$_}++, @_;
}
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
[edit] PHP
<?php
$a = array('John', 'Bob', 'Mary', 'Serena');
$b = array('Jim', 'Mary', 'John', 'Bob');
// 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";
?>
This outputs:
List A: John, Bob, Mary, Serena List B: Jim, Mary, John, Bob A \ B: Serena B \ A: Jim Symmetric difference: Serena, Jim
[edit] Python
Python's set type supports difference as well as symmetric difference operators
>>> 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'])
[edit] 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))
In both cases answer is:
[1] "Jim" "Serena"
[edit] Ruby
First, handle possible non-unique elements
# 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!
Then, find the differences. Both Set and Array objects understand these operations:
a_not_b = a - b
b_not_a = b - a
sym_diff = a_not_b + b_not_a
[edit] 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.
Output is
Set ('Jim' 'Serena' )
[edit] 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.
Library: tcllib
package require struct::setProduces this output:
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]"
A\B = Serena B\A = Jim A⊖B = Jim Serena Direct Check: Jim Serena
[edit] 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>
output:
< 'a': <'John','Bob','Mary','Serena'>, 'b': <'Jim','Mary','John','Bob'>, 'a not b': <'Serena'>, 'b not a': <'Jim'>, 'symmetric difference': <'Jim','Serena'>>
Categories: Programming Tasks | Solutions by Programming Task | C | C++ | Clojure | Common Lisp | D | Factor | Haskell | J | Java | JavaScript | Logo | OCaml | Oz | Perl | PHP | PHP examples needing attention | Examples needing attention | Python | R | Ruby | Smalltalk | Tcl | Tcllib | Ursala
