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=0.8 required=5.0 tests=AWL,SPF_SOFTFAIL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id A8D5CBC6B for ; Wed, 21 Feb 2007 12:01:46 +0100 (CET) Received: from mail.rsise.anu.edu.au (mail.rsise.anu.edu.au [150.203.208.4]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l1LB1ekl017969 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Wed, 21 Feb 2007 12:01:45 +0100 Received: from localhost (localhost [127.0.0.1]) by mail.rsise.anu.edu.au (Postfix) with ESMTP id 61E4F53F03 for ; Wed, 21 Feb 2007 22:01:30 +1100 (EST) Received: from mail.rsise.anu.edu.au ([150.203.208.4]) by localhost (mail [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 23053-05 for ; Wed, 21 Feb 2007 22:01:30 +1100 (EST) Received: from pulp.rsise.anu.edu.au (pulp.rsise.anu.edu.au [150.203.208.49]) by mail.rsise.anu.edu.au (Postfix) with ESMTP id 4597553EFB for ; Wed, 21 Feb 2007 22:01:30 +1100 (EST) Received: by pulp.rsise.anu.edu.au (Postfix, from userid 1560) id 055EDA0AFC7; Wed, 21 Feb 2007 22:06:07 +1100 (EST) Date: Wed, 21 Feb 2007 22:06:07 +1100 From: Pietro Abate To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Combinatorics in a functional way Message-ID: <20070221110607.GB15796@pulp.rsise.anu.edu.au> References: <20070221203603.e222647a.mle+ocaml@mega-nerd.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20070221203603.e222647a.mle+ocaml@mega-nerd.com> X-Operating-System: GNU/Linux X-Organization: Research School of Information Science and Engineering (Australian National University) User-Agent: Mutt/1.5.13 (2006-08-11) X-Virus-Scanned: by amavisd-new-20030616-p10 (Debian) at mail.rsise.anu.edu.au X-Miltered: at discorde with ID 45DC2694.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; permutations:01 seq:01 seq:01 struct:01 flatten:01 val:01 blog:98 blog:98 wrote:01 rec:01 caml-list:01 int:01 int:01 modules:02 lazy:02 On Wed, Feb 21, 2007 at 08:36:03PM +1100, Erik de Castro Lopo wrote: > I'm currently working on something where I need to to generate a > set of permutations that fit a set of rules. Currently I am doing > something like: I'm not sure this is exactly what you want... but I think it's a good starting point to look at for this kind of problems. Making it lazy is just a matter of changing the definition of the modules Seq. module Seq = struct let mzero = [] let return a = [a] let bind m f = List.flatten (List.map f m) let mplus = List.append let guard b = if b then return () else mzero end ;; let range n = let rec aux i l = if i = 0 then l else i::(aux (i-1) l) in List.rev ( aux n [] ) ;; let test _ _ _ = true ;; let find_comb p0 p1 = Seq.bind (range p0) (fun i0 -> Seq.bind (range p0) (fun i1 -> Seq.bind (range p1) (fun i2 -> Seq.bind (Seq.guard (test i0 i1 i2)) (fun _ -> Seq.return (i0,i1,i2) ) ) ) ) ;; # let a = find_comb 4 2 ;; val a : (int * int * int) list = [(1, 1, 1); (1, 1, 2); (1, 2, 1); (1, 2, 2); (1, 3, 1); (1, 3, 2); (1, 4, 1); (1, 4, 2); (2, 1, 1); (2, 1, 2); (2, 2, 1); (2, 2, 2); (2, 3, 1); (2, 3, 2); (2, 4, 1); (2, 4, 2); (3, 1, 1); (3, 1, 2); (3, 2, 1); (3, 2, 2); (3, 3, 1); (3, 3, 2); (3, 4, 1); (3, 4, 2); (4, 1, 1); (4, 1, 2); (4, 2, 1); (4, 2, 2); (4, 3, 1); (4, 3, 2); (4, 4, 1); (4, 4, 2)] # pietro -- ++ Blog: http://blog.rsise.anu.edu.au/?q=pietro ++ ++ "All great truths begin as blasphemies." -George Bernard Shaw ++ Please avoid sending me Word or PowerPoint attachments. See http://www.fsf.org/philosophy/no-word-attachments.html