From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <david.baelde@gmail.com>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: *
X-Spam-Status: No, score=1.0 required=5.0 tests=AWL,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 discorde.inria.fr (discorde.inria.fr [192.93.2.38])
	by yquem.inria.fr (Postfix) with ESMTP id DFA69BC6B
	for <caml-list@yquem.inria.fr>; Wed, 21 Feb 2007 11:36:04 +0100 (CET)
Received: from ug-out-1314.google.com (ug-out-1314.google.com [66.249.92.174])
	by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l1LAa4V4012742
	for <caml-list@yquem.inria.fr>; Wed, 21 Feb 2007 11:36:04 +0100
Received: by ug-out-1314.google.com with SMTP id q2so1052090uge
        for <caml-list@yquem.inria.fr>; Wed, 21 Feb 2007 02:36:04 -0800 (PST)
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=beta;
        h=received:message-id:date:from:reply-to:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        b=hkNGsmqJ4lfk/YejK5IIHB8+Mm7SIL0BdVoMHLvfgm27zeT1QxuaktMwTvyGpQU1xd5fp9asgXs2t2Ex9xMFBItw5QfNPbiNKzosrSKQ7K93t2mka9ooiK1zUa9dDPKt+59SSM7H1R4cD7C4kbxhvSD4SCcx9UwYmJG9OxJB3rQ=
Received: by 10.82.178.11 with SMTP id a11mr14032852buf.1172054163894;
        Wed, 21 Feb 2007 02:36:03 -0800 (PST)
Received: by 10.82.140.13 with HTTP; Wed, 21 Feb 2007 02:36:03 -0800 (PST)
Message-ID: <53c655920702210236k66c75c37r3a83a0d0c0748de@mail.gmail.com>
Date: Wed, 21 Feb 2007 11:36:03 +0100
From: "David Baelde" <david.baelde@gmail.com>
Reply-To: david.baelde@ens-lyon.org
To: "Erik de Castro Lopo" <mle+ocaml@mega-nerd.com>
Subject: Re: [Caml-list] Combinatorics in a functional way
Cc: caml-list@yquem.inria.fr
In-Reply-To: <20070221203603.e222647a.mle+ocaml@mega-nerd.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
References: <20070221203603.e222647a.mle+ocaml@mega-nerd.com>
X-j-chkmail-Score: MSGID : 45DC2094.000 on discorde : j-chkmail score : X : 0/20 1 0.000 -> 1
X-Miltered: at discorde with ID 45DC2094.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)!
X-Spam: no; 0.00; iterator:01 permutations:01 incrementing:01 iter:01 iter:01 permutations:01 rec:01 rec:01 exception:01 caml-list:01 int:01 newline:02 lazy:02 append:02 bounds:02 

Hi,

Here's a possibility. It certainly feels more functional, and also
consumes less memory, but I'm not sure that it fits your needs.
Basically the idea is to build an iterator over permutations, using a
function computing the next permutation from a given one -- this is
basically incrementing a list of digits seen as a number.

I'm lazy so I didn't pass min/max as parameters everywhere. My
solution doesn't use different upper bounds for digits like you (p0
for i0 to i2; p1 for i3 to i7) but it could be adapted.

let min = 2
let max = 4

exception Last

let rec init n = if n=0 then [] else min::(init (n-1))

let rec next acc = function
  | [] -> raise Last
  | x::l ->
      if x<max then List.rev_append acc ((x+1)::l) else next (min::acc) l

(* Iterates [f] over all lists of [len] digits between [min] and [max]. *)
let iter_combi len f =
  let rec iter cur =
    f cur ;
    iter (next [] cur)
  in
    try iter (init len) with Last -> ()

let _ =
  iter_combi 3
    (fun c ->
       print_string (String.concat " " (List.map string_of_int c)) ;
       print_newline ())

By the way, I started using this thing when coding in C to avoid the
memory cost of generating the list of permutations, not because it
felt more functional.

Hope that helps.
-- 
David