2 files changed, 11 insertions, 0 deletions
diff --git a/lib/util.ml b/lib/util.ml
index a1c011ce1b..590d649931 100644
--- a/lib/util.ml
+++ b/lib/util.ml
@@ -445,6 +445,14 @@ let list_fold_map' f l e =
 
 let list_map_assoc f = List.map (fun (x,a) -> (x,f a))
 
+(* list_combinations [[a;b];[c;d]] gives [[a;c];[a;d];[b;c];[b;d]] *)
+
+let rec list_combinations = function 
+  | [] -> [[]]
+  | l::ll -> 
+      let res = list_combinations ll in 
+      list_map_append (fun x -> List.map (fun l -> x::l) res) l
+
 (* Arrays *)
 
 let array_exists f v = 
diff --git a/lib/util.mli b/lib/util.mli
index 5c59708211..c315ecd0ac 100644
--- a/lib/util.mli
+++ b/lib/util.mli
@@ -138,6 +138,9 @@ val list_join_map : ('a -> 'b list) -> 'a list -> 'b list
 val list_fold_map : ('a -> 'b -> 'a * 'c) -> 'a -> 'b list -> 'a * 'c list
 val list_fold_map' : ('b -> 'a -> 'c * 'a) -> 'b list -> 'a -> 'c list * 'a
 val list_map_assoc : ('a -> 'b) -> ('c * 'a) list -> ('c * 'b) list
+(* list_combinations [[a;b];[c;d]] gives [[a;c];[a;d];[b;c];[b;d]] *)
+val list_combinations : 'a list list -> 'a list list
+
 
 (*s Arrays. *)