From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <fvdp@decis.be>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled 
	version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39])
	by yquem.inria.fr (Postfix) with ESMTP id 18217BC69
	for <caml-list@yquem.inria.fr>; Wed, 21 Feb 2007 13:18:09 +0100 (CET)
Received: from decis.be (157.219-78-194.adsl-static.isp.belgacom.be [194.78.219.157])
	by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l1LCI8WR031346
	for <caml-list@yquem.inria.fr>; Wed, 21 Feb 2007 13:18:08 +0100
Received: from [192.168.0.30] by decis.be
	(MDaemon.PRO.v8.1.3.R)
	with ESMTP id md50000631978.msg
	for <caml-list@yquem.inria.fr>; Wed, 21 Feb 2007 13:17:54 +0100
Message-ID: <45DC386E.9030403@decis.be>
Date: Wed, 21 Feb 2007 13:17:50 +0100
From: =?ISO-8859-1?Q?Fr=E9d=E9ric_van_der_Plancke?= <fvdp@decis.be>
User-Agent: Thunderbird 1.5.0.9 (Windows/20061207)
MIME-Version: 1.0
To: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Combinatorics in a functional way
References: <20070221203603.e222647a.mle+ocaml@mega-nerd.com> <53c655920702210236k66c75c37r3a83a0d0c0748de@mail.gmail.com>
In-Reply-To: <53c655920702210236k66c75c37r3a83a0d0c0748de@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
X-Authenticated-Sender: fplancke@decis.be
X-MDRemoteIP: 192.168.0.30
X-Return-Path: fvdp@decis.be
X-MDaemon-Deliver-To: caml-list@yquem.inria.fr
Reply-To: fvdp@decis.be
X-Miltered: at concorde with ID 45DC3880.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)!
X-Spam: no; 0.00; plancke:01 iterator:01 permutations:01 incrementing:01 iter:01 iter:01 permutations:01 wrote:01 rec:01 rec:01 recursively:01 exception:01 caml-list:01 assert:01 tail:01 

David Baelde wrote:
> 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 -> ()

You can also define iter_combi recursively in terms of itself:

(* Iterates [f] over all lists of [len] digits between [min] and [max]. *)
let rec iter_combi min max len f =
    assert (len >= 0);
    if len = 0 then (f [])
    else iter_combi min max (len - 1) (fun tail ->
        for x = min to max do
            f (x :: tail)
        done)

(if you want the lists be passed to f in lexicographical order, write f 
(List.rev (x::tail)) instead of f(x::tail).)

Frédéric
>
> 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.