From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <fernando@cc.gatech.edu>
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 discorde.inria.fr (discorde.inria.fr [192.93.2.38])
	by yquem.inria.fr (Postfix) with ESMTP id E74DFBC69
	for <caml-list@yquem.inria.fr>; Wed, 21 Feb 2007 14:46:41 +0100 (CET)
Received: from sark4.cc.gatech.edu (sark4.cc.gatech.edu [130.207.7.19])
	by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l1LDkeAd014516
	for <caml-list@yquem.inria.fr>; Wed, 21 Feb 2007 14:46:41 +0100
Received: from gaia.cc.gatech.edu (gaia.cc.gatech.edu [130.207.3.8])
	by sark4.cc.gatech.edu (8.13.6/8.12.8) with ESMTP id l1LDkaMJ026801;
	Wed, 21 Feb 2007 08:46:36 -0500 (EST)
Received: (from fernando@localhost)
	by gaia.cc.gatech.edu (8.13.6/8.12.8) id l1LDkZv0003696;
	Wed, 21 Feb 2007 08:46:35 -0500 (EST)
Date: Wed, 21 Feb 2007 08:46:35 -0500
From: Fernando Alegre <fernando@cc.gatech.edu>
To: Erik de Castro Lopo <mle+ocaml@mega-nerd.com>
Cc: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Combinatorics in a functional way
Message-ID: <20070221134635.GA28981@gaia.cc.gatech.edu>
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>
User-Agent: Mutt/1.4.2.1i
X-Miltered: at discorde with ID 45DC4D40.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)!
X-Spam: no; 0.00; permutations:01 wrote:01 rec:01 rec:01 caml-list:01 bounds:02 bounds:02 match:02 match:02 functional:02 arg:03 arg:03 let:03 let:03 erik:04 


Hi,

This is what I would do:

let get i (i0,i1,i2,i3,i4,i5,i6,i7) = match i with
  | 0 -> i0 | 1 -> i1 | 2 -> i2 | 3 -> i3 | 4 -> i4 | 5 -> i5 | 6 -> i6
  | 7 -> i7 | _ -> invalid_arg "get"

let set i (i0,i1,i2,i3,i4,i5,i6,i7) x = match i with
  | 0 -> (x,i1,i2,i3,i4,i5,i6,i7) | 1 -> (i0,x,i2,i3,i4,i5,i6,i7)
  | 2 -> (i0,i1,x,i3,i4,i5,i6,i7) | 3 -> (i0,i1,i2,x,i4,i5,i6,i7)
  | 4 -> (i0,i1,i2,i3,x,i5,i6,i7) | 5 -> (i0,i1,i2,i3,i4,x,i6,i7)
  | 6 -> (i0,i1,i2,i3,i4,i5,x,i7) | 7 -> (i0,i1,i2,i3,i4,i5,i6,x)
  | _ -> invalid_arg "set"

let next bounds index =
  let rec loop i index =
    if i = 8 then index else
      let x = get i index in
        if x < get i bounds then set i index (x+1)
        else loop (i+1) (set i index 0)
  in
    loop 0 index

let fold f acc bounds =
  let rec next i index =
    if i = 7 then index
    else if index < get i bounds then set i (index+1)
    else next (i+1) (set i index 0)
  and loop a index =
    if i = 8 then acc else loop (f a index) (next bounds index)
  in
    loop 0 (0,0,0,0,0,0,0)

let find_combi ((p0,p1,p2,p3,p4,p5,p6,p7) as bounds) =
  fold (fun l x -> x :: l) [] bounds

Fernando

On Wed, Feb 21, 2007 at 08:36:03PM +1100, Erik de Castro Lopo wrote:
> Hi all,
> 
> 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: