Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Generating all combinations of 6 Xs with 3 Qs in Haskell

I am trying to generate a list of all strings that consist of 6 Xs and 3 Qs.

A subset of the list I am trying to generate is as follows:

["XXXXXXQQQ", "XQXXQXXQX", "QXQXQXXXX",...

What is a good way to go about this?

like image 582
sschilli Avatar asked Mar 12 '23 13:03

sschilli


1 Answers

Here is a dynamic programming solution using Data.Array. mem just stores memoized values.

import Data.Array

strings :: Int -> Int -> [String]
strings n m = strings' n m
  where
    mem :: Array (Int,Int) [String]
    mem = array ((0,0),(n,m)) [ ((i,j), strings' i j) | i <- [0..n], j <- [0..m] ]

    strings' 0 m = [replicate m 'X']
    strings' n 0 = [replicate n 'Q']
    strings' n m = (('Q':) <$> mem ! (n-1,m)) ++ (('X':) <$> mem ! (n,m-1))
like image 196
Alec Avatar answered Mar 19 '23 02:03

Alec