How to efficiently generate all lists of length `n ^ 2` containing` n` copies of each `x <n`?

Question

Given an integer n, how can I build a list containing all length lists n^2containing exactly ncopies of each integer x < n? For example, for n = 2we have:

[0,0,1,1], [0,1,0,1], [1,0,0,1], [0,1,1,0], [1,0,1,0], [1,1,0,0]

This can be easily done by combining permutationsand nub:

f :: Int -> [[Int]]
f n = nub . permutations $ concatMap (replicate n) [0..n-1]

But it is too inefficient. Is there an easy way to code an efficient / direct algorithm?

Answer 1

Of course, this is not too difficult. We will start with a list of ncopies of each number less than n, and reselect one to begin our result. Firstly, the function of selecting an item from the list:

zippers :: [a] -> [([a], a, [a])]
zippers = go [] where
    go l (h:r) = (l,h,r) : go (h:l) r
    go _ [] = []

, . , [a] ; , . , , , ?

interleavings :: [[a]] -> [[a]]
interleavings = go . filter (not . null) where
    go [] = [[]]
    go xss = do
        (xssl, x:xs, xssr) <- zippers xss
        (x:) <$> interleavings ([xs | not (null xs)] ++ xssl ++ xssr)

. , , .

f :: Int -> [[Int]]
f n = interleavings (replicate n <$> [1..n])

ghci:

> f 2
[[1,1,2,2],[1,2,2,1],[1,2,1,2],[2,2,1,1],[2,1,1,2],[2,1,2,1]]