This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] how to calculate a "xor"
• Damien
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2003-12-05 (19:11) From: Damien Subject: [Caml-list] how to calculate a "xor"
```Hi algorithmers,

Given two sets A and B, I want to calculate A\B _and_ B\A.
The sets are represented by lists.

without using an order to sort the lists,
is there something better than the following (O(n^2)) ?

<<
let omem a =
let rec aux acc = function
| [] -> None
| a'::q when a=a' -> Some (List.rev_append acc q)
| a'::q -> aux (a'::acc) q
in aux []

let xor x =
let rec aux (a',b') = function
| la, [] -> List.rev_append a' la, b'
| [], lb -> a', List.rev_append b' lb
| a::qa, b::qb when a=b -> aux (a',b') (qa,qb)
| a::qa, b::qb -> match omem a qb, omem b qa with
| None,     None     -> aux (a::a', b::b') (qa, qb )
| Some qb', None     -> aux (   a', b::b') (qa, qb')
| None,     Some qa' -> aux (a::a',    b') (qa',qb )
| Some qb', Some qa' -> aux (   a',    b') (qa',qb')
in aux ([],[]) x
>>

# xor ([4;1;6;2;8],[3;9;5;2;8;1;7]);;
- : int list * int list = ([6; 4], [3; 9; 5; 7])

with an order, is there something better than (O(n*ln n)) :
* sort the two lists,
* "merge" them to extract the result
?

what's the complexity of <Set.Make(M).diff>, from the standard library ?

thanks,
damien

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

```