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=1.0 required=5.0 tests=AWL,SPF_FAIL 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 96F7ABC69 for ; Mon, 5 Mar 2007 15:42:19 +0100 (CET) Received: from ciao.gmane.org (main.gmane.org [80.91.229.2]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l25EgI83008103 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO) for ; Mon, 5 Mar 2007 15:42:19 +0100 Received: from list by ciao.gmane.org with local (Exim 4.43) id 1HOENv-0004ny-S8 for caml-list@inria.fr; Mon, 05 Mar 2007 15:41:55 +0100 Received: from ivr94-8-88-162-26-239.fbx.proxad.net ([88.162.26.239]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Mon, 05 Mar 2007 15:41:55 +0100 Received: from li by ivr94-8-88-162-26-239.fbx.proxad.net with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Mon, 05 Mar 2007 15:41:55 +0100 X-Injected-Via-Gmane: http://gmane.org/ To: caml-list@inria.fr From: Zheng Li Subject: Re: to merge list of lists Date: Mon, 05 Mar 2007 15:42:41 +0100 Message-ID: <87wt1vwy3i.fsf@pps.jussieu.fr> References: <20070305061050.GA21256@pulp.rsise.anu.edu.au> <87abysxbrb.fsf@pps.jussieu.fr> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Complaints-To: usenet@sea.gmane.org Cc: Erik de Castro Lopo X-Gmane-NNTP-Posting-Host: ivr94-8-88-162-26-239.fbx.proxad.net User-Agent: Gnus/5.110006 (No Gnus v0.6) Emacs/22.0.95 (gnu/linux) Cancel-Lock: sha1:Kyk0rqXVyuaJ3M/OzESBTG+/ers= Sender: news X-Miltered: at discorde with ID 45EC2C4A.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; iteration:01 iteration:01 recursion:01 recursion:01 iter:01 haskell:01 computed:01 ocaml:01 iter:01 parser:01 printf:01 printf:01 parser:01 ocaml:01 toplevel:01 hi, > A few weeks ago, someone else asked the permute question [1] in this > list. There are instructive followups you may want to read. I'll also post my > answer here sometime later. This is not a direct response to you question, but it could be related to the problem you want to solve. The original version of this post was posted at a FP forum several years ago. I recently read [1] which is almost identical, and now your question which is closely related, so here I re-post it for your reference. [1] http://caml.inria.fr/pub/ml-archives/caml-list/2007/02/cf0ae15f6f6e18ebf71c79c127d41a74.en.html The permute question raised in [1], and also in many other situation, is just solving the 8-queen problem in another form (in OP, n = 8, whereas the n could be any). There are typically two ways to solve such kind of problem: combination and iteration. The former first combinatrially *generate* all the configurations then filter (or other op) them according to some condition; the later does not generate configurations, instead it iterates over them. Almost any book I read would suggest to use iteration instead of combination for such problems. But in case you're not solving the n-queen like problem and really need to generate it by combination, here we investigate both of them. By Combination -------------- You probably won't be able to write such a function on the fly, especially when taking functional, tail-recursion and row-major all into consideration. This is due to the fact that there are usually 3 nested layers of recursion you need to deal with here (if you really walk through them all by recursion): - the arbitrary dimension $n$ - the range in each dimension (min, max) - and any underlying operation over a list (e.g. prefix all elements of a list with sth etc.) Anyway, here is a possible version. We use (int * int) list, other than int list * int list, to represent range pairs in each dimension to ensure we always have the same number of lower/upper bounds. ------------------------------------------------------------------------- open List let permute : (int * int) list -> int list list = let rec aux res tmp = function | [] -> res | (a,b) :: t when a <= b -> let tmp' = fold_left (fun l x -> (a :: x) :: l) tmp res in aux res tmp' ((a + 1, b) :: t) | _ :: t -> aux (rev tmp) [] t in function [] -> [] | l -> aux [[]] [] (rev l) ------------------------------------------------------------------------- test it: (given min <= max ) ------------------------------------------------------------------------- # permute [];; - : int list list = [] # permute [1,4];; - : int list list = [[1]; [2]; [3]; [4]] permute [(1,4); (12,15); (5,6); (21,22)];; - : int list list = [[1; 12; 5; 21]; [1; 12; 5; 22]; [1; 12; 6; 21]; [1; 12; 6; 22]; [1; 13; 5; 21]; [1; 13; 5; 22]; [1; 13; 6; 21]; [1; 13; 6; 22]; [1; 14; 5; 21]; [1; 14; 5; 22]; [1; 14; 6; 21]; [1; 14; 6; 22]; [1; 15; 5; 21]; [1; 15; 5; 22]; [1; 15; 6; 21]; [1; 15; 6; 22]; [2; 12; 5; 21]; [2; 12; 5; 22]; [2; 12; 6; 21]; [2; 12; 6; ...]; ...] -------------------------------------------------------------------------- Though, doing such kind of job with combination is really bad: - It's difficult to write, esp. fully functional, tail-recursive, row-major etc. - It generates and hold *all* the configurations in *memory*, which is unnecessary in most cases when you just want to iter (esp. filter) them. It has serious problem with huge data. - It generates all the result at last -- at the final step, but nothing before that. Think about the situation if data is huge and take months to permute before you can see a single result, and after that you found something is initially wrong with your algorithm. You definitely want to see the frontal configurations coming out without waiting for the latter, but the combination way doesn't work like that. One should aware the many points above don't apply to lazy language like haskell, as the configurations are not really computed and hold in memory unless required. By Iteration ------------ So as in any book, in most case you should use iteration, I won't repeat them. It can be done functionally in OCaml without doubt. I give a version written in stream, you won't have any problem in rewrite it with list if you want. -------------------------------------------------------------------------------- let rec next = function | h::t, min::min_t, max::max_t -> if h < max then h + 1 :: t else min :: next (t, min_t, max_t) | _ -> raise (Invalid_argument "next") let permute l = let min, max = List.split (rev l) in let rec gen x = [< 'rev x; if x = max then [<>] else gen (next (x,min,max)) >] in gen min;; --------------------------------------------------------------------------------- Then you just use Stream.iter, Stream.next or parser to do whatever you want with it, including store it globally to get the same reult as the combination method if you really need. e.g let s = permute [(1,4); (12,17); (5,6)] in Stream.iter (fun l -> List.iter (Printf.printf "%d ") l; print_newline ()) s There is another stream version which doesn't use the "next" function above, instead recursion over the dimensions and ranges, similar to the combination way but can produce result lazily. ------------------------------------------------------------------------------- let rec map f = parser [<'x ; rest>] -> [<'f x; map f rest>] | [< >] -> [< >] let rec permute = function | (a, b) :: t when a <= b -> [< (match t with [] -> [<'[a]>] | _ -> map (fun x -> a :: x) (permute t)); permute ((a + 1, b) :: t) >] | _ -> [< >];; ------------------------------------------------------------------------------ HTH. -- Zheng Li http://www.pps.jussieu.fr/~li/software (OcamlP3l, STM for OCaml, Enhanced toplevel etc.)