From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id UAA27114; Fri, 5 Dec 2003 20:11:04 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id UAA24839 for ; Fri, 5 Dec 2003 20:11:02 +0100 (MET) Received: from avalon.ens-lsh.fr (mailhost.ens-lsh.fr [193.51.131.2]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id hB5JB1102642 for ; Fri, 5 Dec 2003 20:11:02 +0100 (MET) Received: from avalon.ens-lsh.fr (localhost [127.0.0.1]) by avalon.ens-lsh.fr (8.12.8/8.12.8) with ESMTP id hB5KAP0X012214 for ; Fri, 5 Dec 2003 20:10:25 GMT Received: from ens-notes1.ens-lsh.fr (ens-notes1.ens-lsh.fr [10.2.1.44]) by avalon.ens-lsh.fr (8.12.8/8.12.8) with ESMTP id hB5KAOPN012211 for ; Fri, 5 Dec 2003 20:10:24 GMT Received: from gloups ([10.3.20.31]) by ens-notes1.ens-lsh.fr (Lotus Domino Release 5.0.10) with SMTP id 2003120520105844:87724 ; Fri, 5 Dec 2003 20:10:58 +0100 Date: Fri, 5 Dec 2003 20:08:29 +0100 From: Damien To: caml-list@inria.fr Subject: [Caml-list] how to calculate a "xor" Message-Id: <20031205200829.7e29a2c6.Damien.Pous@ens-lyon.fr> Organization: mosthagloups X-Mailer: Sylpheed version 0.9.6claws (GTK+ 1.2.10; i386-pc-linux-gnu) Mime-Version: 1.0 X-MIMETrack: Itemize by SMTP Server on ens-notes1/ENS-LSH(Release 5.0.10 |March 22, 2002) at 05/12/2003 20:10:58, Serialize by Router on ens-notes1/ENS-LSH(Release 5.0.10 |March 22, 2002) at 05/12/2003 20:11:00, Serialize complete at 05/12/2003 20:11:00 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII X-Loop: caml-list@inria.fr X-Spam: no; 0.00; damien:01 damien:01 ens-lyon:01 qa':99 qa':99 int:01 int:01 rec:01 rec:01 complexity:02 match:02 library:03 let:04 let:04 acc:07 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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 , 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