Symmetric difference

From Rosetta Code
Revision as of 16:24, 30 December 2009 by Ulrie (talk | contribs)
Task
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.

C

<lang c>#include <stdio.h>

  1. include <string.h>
  2. include <stdlib.h>

char mary[]="Mary"; char bob[]="Bob"; char jim[]="Jim"; char john[]="John"; char serena[]="Serena";

char *setA[] = {john,bob,mary,serena}; char *setB[] = {jim,mary,john,bob};

  1. define XSET(j) j, (sizeof(j)/sizeof(char*))
  2. define TALLOC(n,typ) (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
* * * * * * * * * * * * * * * * * * * * **/

char ** symmdiff( int *sym_size, EsdFunction f, char**setA,int setAsize, char **setB, int setBsize) { 

   int union_size;
   int max_union_size;
   int diff_size;
   char **union_set;
   char **diff_set;
   int *union_xor;
   int ix, ixu;

   max_union_size = setAsize + setBsize;
   union_set = TALLOC(max_union_size, 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 -= 1;
       }
       else {		/* not already in union -add */
           if (f == esdSYMMETRIC) {
               union_set[ixu] = setB[ix];
               union_xor[ixu] = 1;
               union_size += 1;
               diff_size += 1;
           }
       }
   }
   /* Put results in symdiff set */
   diff_set = TALLOC(diff_size, char *);
   ix = 0;
   for (ixu=0; ixu<union_size; ixu++) {
       if (union_xor[ixu] == 1) {
           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 (char **set, int ssize) { 

   int ix;
   printf( "= {");
   for (ix=0;ix<ssize; ix++) {
       printf( "%s ", set[ix]);
   }
   printf("}\n");

}

int main(int argc, char **argv) { 

   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 C++>#include <iostream>

  1. include <set>
  2. include <algorithm>
  3. 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 ;
  insert_iterator<set<string> > res_ins( symdiff, symdiff.begin( ) ) ;
  set_symmetric_difference ( firstSet.begin( ) , firstSet.end( ) , secondSet.begin( ) , secondSet.end( ) , res_ins) ;
  copy( symdiff.begin( ) , symdiff.end( ) , ostream_iterator<string>( cout , " " )) ;
  cout << endl ;
  return 0 ;

} </lang> Output: Jim Serena

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)

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>

J

<lang j> A=: ;:'John Bob Mary Serena' 

  B=: ;:'Jim Mary John Bob'

  (A-.B),(B-.A)       NB. Symmetric Difference - similar syntax to set notation

┌──────┬───┐ │Serena│Jim│ └──────┴───┘ 

  A (-. , -.~) B      NB. Tacit equivalent

┌──────┬───┐ │Serena│Jim│ └──────┴───┘ 

  A -. B              NB. A without elements in B

┌──────┐ │Serena│ └──────┘ 

  B -. A              NB. B without elements in A

┌───┐ │Jim│ └───┘</lang>

Java

<lang 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);
   }

}</lang>

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]

Works with: UCB 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>

OCaml

<lang ocaml>let ( -| ) a b = 

 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"]

  1. a -|- b ;;

- : string list = ["Jim"; "Serena"]

  1. a -| b ;;

- : string list = ["Serena"]

  1. b -| a ;;

- : string list = ["Jim"]</lang>

Perl

<lang perl>#!/usr/bin/perl -w use strict;

our @listA = ("John", "Bob", "Mary", "Serena"); our @listB = ("Jim", "Mary", "John", "Bob");

  1. Present our initial data set

print "In list A: " . &formatList(@listA) . "\n"; print "In list B: " . &formatList(@listB) . "\n";

  1. Get our individual differences.

our @notInListA = &inLeftNotRight(\@listB, \@listA); our @notInListB = &inLeftNotRight(\@listA, \@listB);

  1. Given two lists in a list context, Perl 5 collapses them to a single list.
  2. Since our two differences will never have common elements,
  3. we don't worry about losing elements.

our @symmetricDifference = (@notInListA, @notInListB);

  1. Present our results

print "Not in list A: " . &formatList(@notInListA) . "\n"; print "Not in list B: " . &formatList(@notInListB) . "\n"; print "Symmetric Difference: " . &formatList(@symmetricDifference) . "\n";

  1. Checks for elements in the first listref that aren't in the second listref.
  2. We call this for each list, so we can get the symmetric difference.

sub inLeftNotRight { 

   # Our parameters; The referenced left list contains the elements we're searching for.
   # The referenced right list is what we're searching in.
   # We have to use list *references*, as Perl would otherwise collapse
   # both lists into a list, and we wouldn't know
   # which elements came from what list.
   my $leftList = shift;
   my $rightList = shift;

   # Convert to a hash; It makes it easier to search.
   my %rightHash = map {$_, "Some filler value that doesn't matter"} @$rightList;

   # Since each element in the "right" list is now a key in %rightHash
   # we can use Perl's "exists" keyword to quickly find out if our element
   # is in %rightHash, and therefor is in @$rightList. We "grep" through
   # the "left" list to extract only the ones not in the "right" list
   my @notFound = grep { !exists $rightHash{$_} } @$leftList;

   return @notFound;

}

  1. Formats our list as a string that's a little nicer to look at.

sub formatList { 

   join ', ', @_

}</lang>

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

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>

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.

Library: tcllib

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

  1. 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'>

  1. 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'>>
Retrieved from "https://rosettacode.org/wiki/Symmetric_difference?oldid=133261"