Generating all combinations of 6 Xs with 3 Qs in Haskell

Question

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?

Answer 1

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))