[Caml-list] how to calculate a "xor"

[Caml-list] how to calculate a "xor"

[Damien]

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

[Caml-list] Re: how to calculate a "xor"

[Alan Post]

In article <20031205200829.7e29a2c6.Damien.Pous@ens-lyon.fr>, Damien wrote:
> 
> 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)) ?

If you have a decent hashing function, you can get expected linear
time by putting the elements into hash tables.

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

Re: [Caml-list] how to calculate a "xor"

[Jean-Baptiste Rouquier]

Damien wrote:

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

Consider the case A = [a_1; a_3; a_5; ...] and B = [a_2; a_4; a_6; ...] 
where a_i < a__{i+1}.
I think it's a worst case for any algorithm.

> without using an order to sort the lists,

that is, if the only allowed comparison is "="

> is there something better than (...) (O(n2)) ?

In my example, any algorithm has to test if a_{2i} = a_{2j+1}. So the 
worst case is O(n2).


> with an order, is there something better than (O(n*ln n)) ?

Consider the case where an algorithm M hasn't sorted B. So there are 2 
consecutive elements, say a_4 and a_6, that hasn't been compared 
(directly or with transitivity). a_5 can't have been compared to both 
a_4 and a_6, let's consider a_5 hasn't been compared to a_4. Then M 
can't decide whether a_4 = a_5 or not, even using transitivity.

This proove that any algorithm has to sort both A and B in my example, 
so the worst case is
O(n ln n).

See you soon,
Jean-Baptiste.

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