Algorithm all possible combinations

Learning
1

Hello, I wrote the function “main” which is passed as an argument to two positive integers “a” “b” and returns “k list list” which is a list of all possible lists where the length of “k list” is “a” and the sum of its elements is "b ", (Win - 3, Draw - 1, Loose - 0).
example:
main 3 4;;

  • : k list list =
    [[Loose; Draw; Win]; [Loose; Win; Draw]; [Win; Draw; Loose];
    [Draw; Win; Loose]; [Draw; Loose; Win]; [Win; Loose; Draw]]
    I’m afraid the “create” function might not work because of the Random.int function.
    Can you offer me a more optimal solution or help me to fix that problem.
    here is my code:
    type k = Win | Draw | Loose
    let rec sum n = match n with [] → 0 | h::t → h + sum t;;
    let rec create n = let k = Random.int 4 in if k != 2&&n > 0 then k::create (n-1) else if k = 2&&n > 0 then create n else [];;
    let rec convert l = match l with [] → [] | h::t → if h = 3 then Win::convert t else if h = 1 then Draw::convert t else Loose::convert t;;
    let rec pow a = function | 0 → 1 | 1 → a | n → let b = pow a (n / 2) in b * b * (if n mod 2 = 0 then 1 else a);;
    let rec calculate a b acc = match acc with 0 → [] | acc → let k = create a in if sum (k) = b then (convert (k))::calculate a b (acc - 1) else calculate a b (acc - 1);;
    let f acc x = if List.mem x acc = false then x::acc else acc@[];;
    let rec similar l = List.fold_left f [] l;;
    let main a b = similar (calculate a b 580000);;
2

You should format your code with

```ocaml
(*your code here*)
`​``

But yes, using rejection sampling to enumerate all possible combinations is never efficient. You should enumerate then directly with a recursive function combination len sum.

1 Like