Jak skutecznie generować wszystkie listy o długości `n^2` zawierające` n` kopie każdego `x <n`?

Question

Podając liczbę całkowitą n, w jaki sposób mogę utworzyć listę zawierającą wszystkie listy o długości n^2 zawierające dokładnie n kopii każdej liczby całkowitej x < n? Na przykład, dla n = 2, mamy:

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

Można to łatwo zrobić łącząc permutations i nub:

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

Ale to jest zbyt nieefektywne. Czy istnieje prosty sposób kodowania efektywnego/bezpośredniego algorytmu?

Answer 1

Oczywiście, nie jest to zbyt trudne. Zaczniemy od listy n kopii każdego numeru mniejszej niż n i wielokrotnie wybieramy jedną, aby rozpocząć nasz wynik. Po pierwsze, funkcja wyboru elementu z listy:

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

Teraz napiszemy funkcję, która generuje wszystkie możliwe interleavings z niektórych list wejściowych. Wewnętrznie zachowamy niezmienność, że każdy [a] nie jest pusty; dlatego będziemy musieli ustanowić tę niezmienną, zanim zaczniemy powtarzać. W rzeczywistości będzie to zmarnowana praca w sposób, w jaki zamierzamy nazwać tę funkcję, ale dla dobrej abstrakcji równie dobrze moglibyśmy poprawnie obsłużyć wszystkie dane wejściowe, prawda?

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) 

A teraz jesteśmy w zasadzie gotowi. Wszystko, co musimy zrobić, to podać odpowiednią listę początkową.

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

Spróbuj w 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]]