CODEWITHSUNDEEP
ocaml
Clément Joly
Clément Joly

Reputation: 983

Generate all list of a given length between two values (OCaml or other languages)

I am new to ocaml and trying to write some code to generate all lists of number between two value.

For example, if I call this function generate, I want to obtain something like this :

let generate ~min ~max ~length (* Maybe other arguments *) =
    (* The code *)
;;

generate ~min:0 ~max:3 ~length:4;;

Should return

[
[0;0;0];
[1;0;0];
[2;0;0];
[3;0;0];
[0;1;0];

And so on, to

[3;2;3];
[0;3;3];
[1;3;3];
[2;3;3];
[3;3;3];
]

I already tried code like this :

open Core.Std;;

type next_list =
    | Complete of int list
    | Partial of int list
    | Result of (int array) list
;;

let rec next ~r ~min ~max ~l =
    let detox = function | Partial a -> a | _ -> assert false in
    match l with
    | Partial (hd :: tl) when hd <= max -> Partial (hd + 1 :: tl)
    | Partial (hd :: tl) when hd = max + 1 -> next ~r ~min ~max
    ~l:(Partial (min :: (detox (next ~r ~min ~max ~l:(Partial tl))) ))
    | Complete (hd :: tl) when hd <= max -> next ~r:([l] :: r) ~min ~max
    ~l:(Complete (hd + 1 :: tl))
    | Complete (hd :: tl) when hd = max + 1 -> next ~r ~min ~max
    ~l:(Complete (min :: (detox (next ~r ~min ~max ~l:(Partial tl)))))
    (*| Partial [] -> next ~r ~min ~max ~l:(Result r)*)
    | Result a -> Result a

It may be spread around several functions if necessary, that is not a problem.
I am also interested by non ocaml code or idea.

Thanks for your help.

This is my first question on Stackoverflow, do not hesitate to say if my question is unclear.

Upvotes: 3

Views: 679

Answers (2)

Pierre G.
Pierre G.

Reputation: 4431

here some solution : First, let's define that takes 2 lists l1 & l2 as input and that produces a list of list, where each element is l2 augmented by 1 element of l1 :

 let enumerate l ll = List.fold ~init:[] ~f:(fun op x -> (x::ll)::op) l;;

enumerate [0;1;2;3] [4;5;6];; - : int list list = [[3; 4; 5; 6]; [2; 4; 5; 6]; [1; 4; 5; 6]; [0; 4; 5; 6]]

Now generate :

   let rec generate length ll =
     if length=1 then List.fold ~init:[] ~f:(fun op x -> [x]::op) ll
     else 
       let result = generate (length-1) ll in
       List.fold ~init:[] ~f:(fun op x -> (enumerate ll x)@op) result;;

and usage is as follows :

generate 2 [1;2;3];; (* instead of generate ~min:1 ~max:3 ~length:2 *)

Some explanation : List.fold ~init:[] ~f:(fun op x -> [x]::op) ll => this creates the initial list of list (singleton)

And the second : takes each of the list of length -1 and performs the enumeration.

Upvotes: 1

gsg
gsg

Reputation: 9377

Here's a hint: 

let count_prefix low high lists =
  ???

let generate min max length =
  let rec recur low high len =
    if len = 0 then []
    else count_prefix low high (recur low high (len - 1)) in
  recur min max length

count_prefix should return a list that is the elements of lists prefixed with the numbers low to high. If lists is empty, it should return a list of lists containing the numbers low to high. That is:

count_prefix 0 3 [] => [[0]; [1]; [2]]
count_prefix 0 3 [[10];[20]] => [[0; 10]; [0; 20]; [1; 10]; [1; 20]; [2; 10]; [2; 20]]

Fill in the definition of count_prefix.

Upvotes: 0

Related Questions