Permutazione di un elenco - Haskell

Question

Voglio fare tutte le possibili combinazioni di sottogruppi con 2 elenchi. Ecco una funzione che fa proprio questo:

getCombinations :: [a] -> [[a]] 
getCombinations na = do 
    a <- na 
    b <- na 
    [[a,b]] 

Se passate "abc" per questa funzione, restituisce questo:

["aa","ab","ac","ba","bb","bc","ca","cb","cc"] 

una semplice modifica dello stesso metodo potrebbe tornare combinazioni di 3 liste invece di due.

getCombinations :: [a] -> [[a]] 
getCombinations na = do 
    a <- na 
    b <- na 
    c <- na 
    [[a,b,c]] 

Risultato di passaggio "abc" come argomento:

["aaa","aab","aac","aba","abb","abc","aca","acb","acc", 
"baa","bab","bac","bba","bbb","bbc","bca","bcb","bcc", 
"caa","cab","cac","cba","cbb","cbc","cca","ccb","ccc"] 

Qual è il modo più semplice per farlo scalare a un numero arbitrario di liste? Ecco ciò che la dichiarazione del tipo dovrebbe assomigliare:

getCombinations :: Int -> [a] -> [[a]] 

Answer 1

Quello che vuoi è replicateM:

replicateM :: Int -> m a -> m [a] 

La definizione è semplice come:

replicateM n = sequence . replicate n 

quindi è sequence sulla lista Monade sta facendo il vero lavoro qui.

Answer 2

Per coloro venire qui per la funzione combination, un k -complessi di un insieme S è un sottoinsieme di k elementi distinti di S , si noti che l'ordine non importa.

Scegliere k elementi n elementi equals scegliere k - 1 elementi n - 1 elementi oltre a scegliere gli elementi da kn - 1 elementi.

utilizzare questa definizione ricorsiva, possiamo scrivere: domanda

combinations :: Int -> [a] -> [[a]] 
combinations k xs = combinations' (length xs) k xs 
    where combinations' n k' l@(y:ys) 
      | k' == 0 = [[]] 
      | k' >= n = [l] 
      | null l = [] 
      | otherwise = map (y :) (combinations' (n - 1) (k' - 1) ys) ++ combinations' (n - 1) k' ys 


ghci> combinations 5 "abcdef" 
["abcde","abcdf","abcef","abdef","acdef","bcdef"] 

del op è una ripetuti permutazioni, che qualcuno ha già dato una risposta. Per permutazione non ripetuta, utilizzare permutations da Data.List.