Combinatorics / assignment problem

Learning
1

Hello,

I have a funny problem, which gives me trouble solving (I am not in my best day it seems):

I have two lists:

let’s say [1; 2; 3] is the “left hand side” (LHS) and [-1; 4; 5; 6] is the “right hand side” (RHS).

I am interested in all possible assignments of [1; 2; 3] to [-1; 4; 5; 6].
Several numbers from the left hand side can be assigned to -1 at the same time.
I.e. this is a valid assignment:
[(1, -1); (2, -1); (3, -1)]

However, other numbers from [4;5;6] can be used only once in an assignment.
I.e. this assignment is invalid:
[(1, -1); (2, 4); (3, 4)]

I would like to enumerate all the possible valid assignments.
I.e. list of pairs of length the length of the LHS.

Thanks a lot,
F.

1 Like
2

I think something like this should work:

let rec enumerate lhs rhs =
  match lhs with
  | [] -> [[]]
  | x :: xs ->
    List.concat_map
      (fun y ->
         let rhs = if y = -1 then rhs else List.filter ((<>) y) rhs in
         List.map (fun ass -> (x, y) :: ass) (enumerate xs rhs)
      ) rhs

Cheers,
Nicolas

2 Likes
3

Thanks a lot, I am amazed.
I was really stucked after having tried many things.
Maybe I should have tried to solve the problem w/o the -1 case first.