如何有效地生成所有长度为'n ^ 2`的列表,其中包含每个`x <n`的`n`副本？

Question

给定一个整数n,我如何构建包含所有长度列表的列表,n^2其中包含n每个整数的完全副本x < n？例如,因为n = 2,我们有:

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

这可以轻松完成合并permutations和nub:

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

但这太低效了.有没有简单的方法来编码高效/直接算法？

Answer 1

当然,这不是太难.我们将从n每个数字的副本列表开始n,并重复选择一个以开始我们的结果.首先,从列表中选择元素的函数:

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