Her `x <n` nin` n` kopyalarını içeren n '2` uzunluklarının tüm listelerini verimli bir şekilde nasıl üretilir?

Question

Bir tam sayı n verildiğinde, tüm uzunluklarının tümünü içeren listeyi, her bir tam sayı x < n tam n kopyasını içeren şekilde nasıl oluşturabilirim?

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

Bu

kolayca permutations ve nub birleştirerek yapılabilir:

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

Ama bu yol çok verimsiz Örneğin, n = 2 için, ettik. Verimli/doğrudan algoritmayı kodlamanın basit bir yolu var mı?

Answer 1

Elbette, bu çok zor değil. n'dan daha küçük her bir sayının n kopyasının bir listesiyle başlayacağız ve sonucumuzu başlatmak için tekrar tekrar birini seçin. İlk olarak bir listeden bir öğe seçmek için bir fonksiyon:

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

Şimdi bazı girdi listelerinin tüm olası interleavings üreten bir fonksiyon yazacağım. Dahili olarak, her bir [a]'un boş olmadığını; bu yüzden tekrarlamaya başlamadan önce bu değişmezi kurmak zorundayız. Aslında bu, bu işlevi çağırmak istediğimiz şekilde boşa harcanacaktır, ancak iyi bir soyutlama için tüm girdileri doğru bir şekilde ele alabiliriz, değil mi?

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) 

Ve şimdi temelde bitti. Tek yapmamız gereken uygun bir başlangıç ​​listesinde beslenmek.

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

GHCi bunu deneyin:

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

Ben hemen bir yöntem düşünebiliriz