A implementação de um método factorisation em Haskell

Question

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 ?

Answer 1

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.

Answer 2

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.