From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=2.0 required=5.0 tests=AWL,DNS_FROM_RFC_POST, SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 239C5BBAF for ; Thu, 30 Jul 2009 20:47:03 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AsoBAPuHcUrRVdK0kWdsb2JhbACZVD8BAQEBCQkMBxGoPgqBFZAuAQMCBIQTBYFJhgs X-IronPort-AV: E=Sophos;i="4.43,296,1246831200"; d="scan'208";a="31910574" Received: from mail-yx0-f180.google.com ([209.85.210.180]) by mail3-smtp-sop.national.inria.fr with ESMTP; 30 Jul 2009 20:46:52 +0200 Received: by yxe10 with SMTP id 10so2709930yxe.15 for ; Thu, 30 Jul 2009 11:46:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:from:reply-to:to:subject:date :user-agent:cc:references:in-reply-to:content-type :content-transfer-encoding:content-disposition:message-id; bh=nHmigUUtFP3vd+z8HQ/sojBbcTxfmeX9m066L4qI2RU=; b=cV8CmiTqz+J9KOe2nBXfvtZLfn5LCqRNJv+6Bf34Tn9jzooM0s//I9chSphoKjYH5U uetcNJYwhOLn8O5eQnyEO7Kl4VYUVl3ww0x3TFB6TMRVM/rPsip2p/rF2JkFSWEomtie Y5dbhXb5ZwKFGTp7ivWszwJRoM46QIEz6KYq0= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=from:reply-to:to:subject:date:user-agent:cc:references:in-reply-to :content-type:content-transfer-encoding:content-disposition :message-id; b=osDZXpdcIarRMqKdcHyw+8uxl6voYpp/c6V91uhhhp/gR9GUZIyKT03UDSuoo2+HTB zqmfVwBrGb0y8gDQoOOeyxPTXKHYu2k4nMId1tnF8h7RuKK3vz8TwIMAG8enWrN4ieuJ ho2bbH9/hjd2JttqXicqt2dQEh5DFnLRieNlc= Received: by 10.100.112.8 with SMTP id k8mr1990048anc.174.1248979610633; Thu, 30 Jul 2009 11:46:50 -0700 (PDT) Received: from lawn-143-215-206-56.lawn.gatech.edu (lawn-143-215-206-56.lawn.gatech.edu [143.215.206.56]) by mx.google.com with ESMTPS id 22sm24720ywh.4.2009.07.30.11.46.49 (version=TLSv1/SSLv3 cipher=RC4-MD5); Thu, 30 Jul 2009 11:46:49 -0700 (PDT) From: Peng Zang Reply-To: peng.zang@gmail.com To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Cartesian product Date: Thu, 30 Jul 2009 14:46:41 -0400 User-Agent: KMail/1.9.9 Cc: Ligia Nistor References: <8401c38a0907301056x470687aah94b2b1295c6d1068@mail.gmail.com> In-Reply-To: <8401c38a0907301056x470687aah94b2b1295c6d1068@mail.gmail.com> Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200907301446.47427.peng.zang@gmail.com> X-Spam: no; 0.00; hash:01 enum:01 decr:01 decr:01 ocaml:01 peng:98 peng:98 2009:98 wrote:01 rec:01 rec:01 assert:01 caml-list:01 defined:02 implemented:02 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Not that I know of. But you can use this general implementation. It assumes you have Enum (from Batteries, and ExtLib before). The (~~) prefix operator is "Obj.magic". Peng (* makes the cross product of the given array of enumerations *) let crossproductM enums initcount = let numenums = Array.length enums in let clean = Array.map clone enums in let initstate = enums in let rec cpmk cur curcount = let reseti i = cur.(i) <- clone clean.(i) in let tick () = let rec tick_aux place = if place >= numenums then () else let ple = cur.(place) in ignore (get ple); if is_empty ple then ( reseti place; tick_aux (place + 1) ) in tick_aux 0; decr curcount in let get () = Array.init numenums (fun i -> Option.get (peek cur.(i))) in let nx () = match !curcount with | 0 -> raise No_more_elements | 1 -> decr curcount; get () | x -> assert (x >= 0); let ans = get () in tick (); ans in let ct () = !curcount in let cl () = cpmk (Array.init numenums (fun i -> clone cur.(i))) (ref !curcount) in make nx ct cl in ( if initcount == 0 then empty () else cpmk initstate (ref initcount) ) let crossproduct enums = let copy = Array.copy enums in let initcount = Array.fold_left (fun acc e -> count e * acc) 1 copy in crossproductM copy initcount let cross2 (t1:'a t) (t2:'b t) : ('a * 'b) t = ~~(crossproduct [|~~t1; ~~t2|]) let cross3 (t1:'a t) (t2:'b t) (t3:'c t) : ('a * 'b * 'c) t = ~~(crossproduct [|~~t1; ~~t2; ~~t3|]) On Thursday 30 July 2009 01:56:50 pm Ligia Nistor wrote: > Hi, > > Is there an already implemented way of doing the Cartesian product of 2 > sets in OCaml? My sets are of type Set.Make(Types), where Types is a module > I have defined. > > Thanks, > > Ligia -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.7 (GNU/Linux) iD8DBQFKceqXfIRcEFL/JewRAnM5AKC3dnxh9uWl7kdRBKW68koS1f3dhACgxau4 ubBf3OXzaxkMeU3Cb848lJY= =XZ4Q -----END PGP SIGNATURE-----