A implementação de um método factorisation em Haskell
-
13-09-2019 - |
Pergunta
Estou fazendo questão 266 no Projeto Euler e depois de um pouco de busca, encontrou este método de encontrar rapidamente os fatores de um número. O que você faz é encontrar todas as permutações dos fatores primos de um número:. Estas são seus fatores
Eu já tenho um módulo de encontrar os fatores de potência primos de um número, por exemplo:
Main> primePowerFactors 196
[(2,2),(7,2)]
Este é basicamente mostrando que: 2^2 * 7^2 == 196
. A partir daqui eu quero encontrar todas as permutações de tais poderes, para dar os fatores de 196 assim:
- (2 ^ 0) (7 ^ 0) = 1
- (2 ^ 1) (7 ^ 0) = 2
- (2 ^ 2) (7 ^ 0) = 4
- (2 ^ 0) (7 ^ 1) = 7
- (2 ^ 1) (7 ^ 1) = 14
- (2 ^ 2) (7 ^ 1) = 28
- (2 ^ 0) (7 ^ 2) = 49
- (2 ^ 1) (7 ^ 2) = 98
Eu vim com o seguinte:
factors n = [a|a<-map facs (primePowerFactors n), y <- [0..(snd $ last $ primePowerFactors n)]]
where
facs (x,y) = (x,y)
rSq n = toInteger $ round $ sqrt (fromInteger n)
psr n = last $ dropWhile (<= rSq n) $ factors n
p = foldl' (*) 1 $ takeWhile (< 190) primes
answer = (psr p) `mod` (10^16)
Mas o meu problema é que factors
não funciona corretamente. Eu quero que ele permutar através de todos os possíveis valores do expoente para cada fator primordial e, em seguida, encontrar o produto para dar o fator. Como ele pode ser modificado para retornar os apenas os fatores de n ?
Solução
para alguns golf código que eu escrevi uma função bom conjunto de energia que é bastante simples.
powerSet [] = []
powerSet (x:xs) = xs : map (x:) (powerSet xs) ++ (powerSet xs)
A deficiência deste algoritmo é que ele não inclui o conjunto original, no entanto, que é perfeito para você, uma vez que não se parece com você quer.
combinar isso com uma maneira de converter o seu primePowerFactors n
em uma lista de inteiros, digamos
ppfToList = concatMap (\(x,y)->replicate y x)
usando esses ajudantes, uma lista de fatores de um número n é gerado com
factors n = nub . map product . powerSet . ppfToList . primePowerFactors $ n
-- will be out of order, you can add a call to `sort` to fix that
Este tipo de algoritmo é provavelmente um pouco mais difícil de expressar em termos de uma compreensão da lista.
Outras dicas
Em primeiro lugar, facs
é a função identidade:
facs (x,y) = (x,y)
O y
está ligada ao jogo padrão no lado esquerdo, enquanto você provavelmente pretendia que fosse o y
da lista compreensão. Os nomes das variáveis ??ligadas em uma compreensão da lista são locais para essa compreensão e não pode ser usado em um escopo diferente, como a cláusula where
.
Além disso, o y
na lista compreensão só é calculado a partir do último fatores expoente:
y <- [0..(snd $ last $ primePowerFactors n)]
Para cada fator é própria expoente deve ser considerado, não só sempre o expoente do último fator.
Um problema mais fundamental é que o tipo de retorno da função factors
não parece corresponder a sua intenção:
*Euler> :t factors
factors :: Integer -> [(Integer, Int)]
Este retorna uma lista de poderes de fatores primos enquanto ele deve produzir uma lista dessas construções, como este:
[
[(2,0), (7,0)],
[(2,1), (7,0)],
[(2,2), (7,0)],
[(2,0), (7,1)],
[(2,1), (7,1)],
...
]
É necessária a fatoração nobre de todos os fatores possíveis, mas a função parece retornar apenas um nobre fatoração.