Combinatorics in a functional way
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Frédéric_van_der_Plancke <fvdp@d...> 
Subject:  Re: [Camllist] Combinatorics in a functional way 
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 (n1)) > > 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.