すべての `x <n 'の` n`個のコピーを含む長さ `n^2`のリストを効率的に生成する方法はありますか？

Question

与えられた整数nは、正確にn各整数のコピーを含む長さn^2のすべてのリストを含むリストを作成できますx < n？例えば、n = 2のために、私たちはしている：

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

しかし、それはあまりにも非効率的である：

[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を組み合わせて行うことができます。効率的な/直接的なアルゴリズムを簡単にエンコードする方法はありますか？

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