प्रत्येक `x <n` की` n` प्रतियों वाली लंबाई 'n^2` की सभी सूचियों को कुशलतापूर्वक कैसे उत्पन्न करें?

Question

एक पूर्णांक n दिया गया, मैं लंबाई n^2 की सभी सूचियों वाली सूची कैसे बना सकता हूं जिसमें प्रत्येक पूर्णांक x < n की 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

निश्चित रूप से, यह बहुत कठिन नहीं है। हम nn से कम प्रत्येक संख्या की प्रतियों की एक सूची के साथ शुरू करेंगे, और बार-बार हमारे परिणाम को शुरू करने के लिए चुनते हैं। सबसे पहले, एक सूची से एक तत्व को चुनने के लिए एक समारोह:

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

अब हम एक समारोह है कि कुछ इनपुट सूचियों के सभी संभव interleavings पैदा करता लिखेंगे। आंतरिक रूप से हम इनवेरिएंट को बनाए रखेंगे कि प्रत्येक [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]]