Symmetric difference: Difference between revisions
No edit summary |
Underscore (talk | contribs) (→{{header|Perl}}: Cleaned up. I deleted some of the comments because I thought they were more noisy than enlightening.) |
||
Line 300: | Line 300: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
<lang perl> |
<lang perl>our @a = qw(John Bob Mary Serena); |
||
our @b = qw(Jim Mary John Bob); |
|||
use strict; |
|||
⚫ | |||
our @listA = ("John", "Bob", "Mary", "Serena"); |
|||
our @ |
our @a_minus_b = setminus(\@a, \@b); |
||
our @b_minus_a = setminus(\@b, \@a); |
|||
# Perl 5 automatically flattens arrays in list context. Since our two |
|||
⚫ | |||
# duplicate elements in the symmetric difference. |
|||
our @symmetric_difference = (@a_minus_b, @b_minus_a); |
|||
# Present our |
# Present our results. |
||
print |
print 'List A: ', join(', ', @a), |
||
"\nList B: ", join(', ', @b), |
|||
print "In list B: " . &formatList(@listB) . "\n"; |
|||
"\nA \\ B: ", join(', ', @a_minus_b), |
|||
"\nB \\ A: ", join(', ', @b_minus_a), |
|||
⚫ | |||
"\nSymmetric difference: ", join(', ', @symmetric_difference), "\n"; |
|||
our @notInListA = &inLeftNotRight(\@listB, \@listA); |
|||
our @notInListB = &inLeftNotRight(\@listA, \@listB); |
|||
sub setminus |
|||
# |
# Takes two array references. Returns a list of elements in the first |
||
# array that aren't in the second. |
|||
⚫ | |||
# we don't worry about losing elements. |
|||
our @symmetricDifference = (@notInListA, @notInListB); |
|||
# 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"; |
|||
# Checks for elements in the first listref that aren't in the second listref. |
|||
# 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 $rightList = shift; |
|||
# Convert to a hash |
# Convert @b to a hash, so it's easier to search. |
||
my %b; |
|||
my %rightHash = map {$_, "Some filler value that doesn't matter"} @$rightList; |
|||
@b{@$b} = (); |
|||
# 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 |
|||
⚫ | |||
return @notFound; |
|||
} |
|||
# Formats our list as a string that's a little nicer to look at. |
|||
sub formatList |
|||
{ |
|||
join ', ', @_ |
|||
}</lang> |
}</lang> |
||
This outputs: |
This outputs: |
||
<pre> |
<pre>List A: John, Bob, Mary, Serena |
||
List B: Jim, Mary, John, Bob |
|||
A \ B: Serena |
|||
Not in list A: Jim |
|||
B \ A: Jim |
|||
Not in list B: Serena |
|||
Symmetric |
Symmetric difference: Serena, Jim</pre> |
||
</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 23:18, 30 December 2009
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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>
- include <string.h>
- 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};
- define XSET(j) j, (sizeof(j)/sizeof(char*))
- 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>
- 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 ; 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]
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"]
- a -|- b ;;
- : string list = ["Jim"; "Serena"]
- a -| b ;;
- : string list = ["Serena"]
- b -| a ;;
- : string list = ["Jim"]</lang>
Perl
<lang perl>our @a = qw(John Bob Mary Serena); our @b = qw(Jim Mary John Bob);
- Get the individual differences.
our @a_minus_b = setminus(\@a, \@b); our @b_minus_a = setminus(\@b, \@a);
- Perl 5 automatically flattens arrays in list context. Since our two
- differences don't have common elements, we needn't worry about
- duplicate elements in the symmetric difference.
our @symmetric_difference = (@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";
sub setminus
- Takes two array references. Returns a list of elements in the first
- array that aren't in the second.
{
my ($a, $b) = @_;
# Convert @b to a hash, so it's easier to search. my %b; @b{@$b} = (); return grep { not exists $b{$_} } @$a;
}</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
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.
<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'>>