# Combinatorics / assignment problem

**URL:** <https://discuss.ocaml.org/t/combinatorics-assignment-problem/15648>\
**Category:** Learning\
**Created:** [November 21, 2024, 3:39pm UTC](https://discuss.ocaml.org/t/combinatorics-assignment-problem/15648 "2024-11-21T15:39:43Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![UnixJunkie](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/unixjunkie/32/638_2.png) [@UnixJunkie](https://discuss.ocaml.org/u/UnixJunkie)\
**Post date:** [November 21, 2024, 3:39pm UTC](https://discuss.ocaml.org/t/combinatorics-assignment-problem/15648/1 "2024-11-21T15:39:43Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![nojb](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/nojb/32/519_2.png) [@nojb](https://discuss.ocaml.org/u/nojb)\
**Post date:** [November 21, 2024, 4:19pm UTC](https://discuss.ocaml.org/t/combinatorics-assignment-problem/15648/2 "2024-11-21T16:19:12Z")

</div>

I think something like this should work:

```ocaml
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

---

<div class="post-metadata">

**Author:** ![UnixJunkie](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/unixjunkie/32/638_2.png) [@UnixJunkie](https://discuss.ocaml.org/u/UnixJunkie)\
**Post date:** [November 25, 2024, 11:01am UTC](https://discuss.ocaml.org/t/combinatorics-assignment-problem/15648/3 "2024-11-25T11:01:09Z")

</div>

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.