Ferramentas de Utilizador

Ferramentas de Site


dev_geral:haskell:permutacao

Permutações

Este código tem com o intuito a geração de todas as permutações possíveis de uma dada sequência. Este código baseia-se numa thread que surgiu no quadro de Python e foi transcrito para Haskell dando uso a listas por compreensão.

A função perm devolve todas as permutações de uma dada sequência. Mas nos casos que a sequência contêm elementos repetidos, em termos de lógica serão considerados como elementos diferentes. Para garantir a unicidade de permutações existe para isso a função perm'.

import Data.List (delete, nub)
 
perm :: Eq a => [a] -> [[a]]
perm [] = [[]]
perm l = [ c:r | c <- l, r <- perm (delete c l)]
 
perm' :: Eq a => [a] -> [[a]]
perm' = nub . perm

Utilização

Para utilizar basta indicar a sequência que se quer permutar.

perm "123"
-- irá devolver ["123","132","213","231","312","321"]
 
perm [1, 2, 3]
-- irá devolver [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 
perm "aabb"
-- irá devolver ["aabb","aabb","abab","abba","abab","abba", ... ,"baab","baba","bbaa","bbaa"]
 
perm' "aabb"
-- irá devolver ["aabb","abab","abba","baab","baba","bbaa"]
dev_geral/haskell/permutacao.txt · Esta página foi modificada pela última vez em: 2018/05/14 21:37 (Edição externa)