combination/permutations combinators #503

Open
c-cube opened this Issue Jan 7, 2014 · 12 comments

Comments

Projects
None yet
4 participants
Member

c-cube commented Jan 7, 2014

Someone on IRC asked whether some OCaml library provided functions to generate permutations or combinations of a bunch of elements. I didn't see any in Batteries (although I may have missed them in some module); they seem very useful for many algorithms and are not trivial to implement, so I think it may be a good idea to add at least BatList.combinations and BatList.permutations. An in-place generator for arrays is also doable (see C++'s STL).

Member

UnixJunkie commented Jan 8, 2014

I think it might be useful for people programming maths things.

Owner

gasche commented Jan 10, 2014

It would also be interesting to have Enum (or any lazy sequence) versions because the algorithms for strict and lazy production are rather different -- for lazy structures, you use counting scheme such as factorial basis numbers.

Chimrod commented Jan 19, 2014

Hello, I have written a module for combination with the following signature :

type t

val combinaison : ?repetions:bool -> int -> int -> t
(** Create a combinaison from a given n and k *)

val length : t -> int
(** @return the numer of elements in the combinaison *)

val get_order : int -> int list -> int
(** @return the indice of the given combinaison in the given order *)

val order_to_comb : t -> int -> int list

val remove_repetions : int list -> int list
(** Convert the given list to an equivalent list without repetions inside the
    combinaison *)

val enum : t -> int list BatEnum.t
(** @return a lazy enumeration over the combinaisons *)
open Batteries

(**
 The type t is a tuple composed of :
     the cardinal of the combinaison
     the number of elements
 *)
type t = (int * int * bool)

let combinaison ?(repetions=false) n k =
    if repetions then
      (n + k -1, k, repetions)
    else
      (n, k, repetions)

let binomial n p =
  let binom n p =
      if p < 0 || n < 0 || p > n then 0
      else (
        let a = ref 1 in
        for i = 1 to p  do
            a := !a * (n + 1 - i) / i
        done;
        !a
      )
  and comp = n - p
  in if (comp < p) then
    binom n comp
  else
    binom n p

let length (n, p, repetions) = binomial n p

let get_order max elems =
  let f (prev, p, rang) a =
    let new_rang = ref rang in
    for x = prev + 1 to a - 1 do
      new_rang := !new_rang + binomial (x-1) (p -1)
    done;
    (a, p + 1, !new_rang)
  in let res = List.fold_left f (0, 0, 0) elems
  in let _, _, b = f res (max + 1)
  in b

let remove_repetions =
  let rec conv range acc = function
  | []    -> List.rev acc
  | h::tl -> conv (range + 1) ((h + range) :: acc) tl
  in conv 0 []

let add_repetitions =
  let rec conv range acc = function
  | []    -> acc
  | h::tl -> conv (range + 1) ((h - range) :: acc) tl
  in conv 0 []

let order_to_comb (n, p, repetions) ord =
  let rec get_comb n p ord acc =
    if n <= 0 || p <= 0 || ord < 0 then acc
    else (
      let b = binomial (n -1) (p - 1)
      in
        if ord < b then
            get_comb (n - 1) (p - 1) ord (n::acc)
        else
            get_comb (n - 1) p (ord - b) acc
    )
  in let result = get_comb n p ord []

  in if repetions then
     add_repetitions result
  else
     result

let enum t =
  let length = length t
  in let rec make index =
    Enum.make
      ~next:(fun () ->
        if !index = length then
          raise Enum.No_more_elements
        else
          let next = order_to_comb t !index 
          in incr index; next
      )
      ~count:(fun () -> length - !index)
      ~clone:(fun () -> make (ref !index))
  in make (ref 0)

The module generate int combinations but has the benefits to give index for each of combination and lazy enumeration… I used it with association list for convert the int combination to t combination

If you are interested, I can make a proper pull request with the module and some tests.

Member

c-cube commented Jan 19, 2014

That's interesting, but I think that in Batteries it would be better to have combinations and permutations over polymorphic containers. A specialized function for [1,...,n] integer permutations (returning an int list Enum.t) would still be useful, of course.

Chimrod commented Jan 20, 2014

On dim. 19 janv. 2014 22:32:36 CET, Simon Cruanes notifications@github.com wrote:

That's interesting, but I think that in Batteries it would be better to
have combinations and permutations over polymorphic containers. A
specialized function for [1,...,n] integer permutations (returning an
int list Enum.t) would still be useful, of course.

There is no way to do that directly. If you want an effective way for iterate over combinaition, you have to work this int.

I gave you the code 'as is' for discussion, there is no difficulty to wrap this algorithm with an association function for make it work with polymorphic list.

Member

UnixJunkie commented Jan 21, 2014

All code should be in proper English:
"combinaison" is combination I guess.
"repetitions" could be repeat maybe.

UnixJunkie closed this Jan 21, 2014

UnixJunkie reopened this Jan 21, 2014

Member

UnixJunkie commented Jan 21, 2014

Sorry, the close was a miss-click, I reopened the issue.

Owner

gasche commented Jan 21, 2014

I'm not fond of having "repetitions" as a parameter. I think we could use different functions for combinations (without repetitions) and selections/multicombinations (with repetitions). We could even use different types, with either two modules with the same interface, or a phantom type to distinguish them but have repeatability-polymorphic operations.

Chimrod commented Jan 21, 2014

I think this only make sense if you want to add a full math module in batteries. If you just need to get utilities for generate enum, you don't need to add more complexity.

The commit I've made does not add any new type; only a new function for enum creation. It's come from the code shown above, but cleaned in order to integrate with Batteries easily

Member

UnixJunkie commented Feb 19, 2014

this feature is related to #513

Owner

gasche commented Apr 20, 2016

Where are we on this? @c-cube recalled us that this PR is undecided (thanks!), but it's not clear to me what the best move is. The code as proposed by @Chimrod is not mergeable as-is (because of the french wordings), and there is a debate on the interface.

I wouldn't mind adding a BatCombinatorics module with a more polished version of @Chimrod code, but given the absence of dependencies on anything else in Batteries I also think that it would be served just as well as an independent package available on opam, that non-Batteries users may have less qualms including. (There already is backtracing/combine, but it seems more about constraint resolution than arithmetic enumerations.)

Member

c-cube commented Apr 20, 2016 edited

Side note: there is also

val Gen.permutations : 'a gen -> 'a list gen 
val Gen.permutations_heap : 'a gen -> 'a array gen
val Gen.combinations : int -> 'a gen -> 'a list gen
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment