La mise en oeuvre d'un procédé de factorisation en Haskell

Question

Je suis en train de faire question 266 au projet Euler et après un peu de la recherche, a trouvé cette méthode de trouver rapidement les facteurs d'un nombre. Ce que vous faites est de trouver toutes les permutations des facteurs premiers d'un nombre. Ce sont ses facteurs

Je possède déjà un module pour trouver les facteurs de puissance d'un certain nombre, par exemple:

Main> primePowerFactors 196
[(2,2),(7,2)]

Cette montre essentiellement que: 2^2 * 7^2 == 196. De là, je veux trouver toutes les permutations de ces pouvoirs, pour donner les facteurs de 196 ainsi:

• (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

Je suis venu avec ce qui suit:

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)

Mais mon problème est que factors ne fonctionne pas correctement. Je veux qu'il permute à travers toutes les valeurs possibles de l'exposant pour chaque facteur premier, puis trouver le produit pour donner le facteur. Comment peut-il être modifié pour retourner les justes les facteurs de n

Answer 1

pour une partie de golf de code i a écrit une belle fonction de jeu de puissance qui est assez simple.

powerSet [] = []
powerSet (x:xs) = xs : map (x:) (powerSet xs) ++ (powerSet xs)

Une carence de cet algorithme est qu'il ne comprend pas le jeu original, mais qui est parfait pour vous car il ne ressemble pas à vous le voulez.

combiner avec un moyen de convertir votre primePowerFactors n en une liste de ints, permet de dire

ppfToList = concatMap (\(x,y)->replicate y x)

à l'aide de ces aides, une liste de facteurs d'un nombre n est généré avec

factors n = nub . map product . powerSet . ppfToList . primePowerFactors $ n
-- will be out of order, you can add a call to `sort` to fix that

Ce type d'algorithme est probablement un peu plus difficile à exprimer en termes de compréhension de la liste.

Answer 2

Tout d'abord, facs est la fonction d'identité:

facs (x,y) = (x,y)

Le y est lié dans le match de motif sur le côté gauche alors que vous avez probablement l'intention à la y de la compréhension de la liste. Les noms de variables liées à une compréhension de la liste locale de cette compréhension et ne peuvent être utilisés dans un cadre différent, comme la clause where.

En outre, le y dans la compréhension de la liste n'est calculée à partir du dernier facteurs exposant:

y <- [0..(snd $ last $ primePowerFactors n)]

Pour doit être considéré comme chaque facteur, il est propre exposant, non seulement toujours l'exposant du dernier facteur.

Un problème plus fondamental est que le type de retour de la fonction factors ne semble pas correspondre son intention:

*Euler> :t factors
factors :: Integer -> [(Integer, Int)]

Ceci retourne une liste des pouvoirs des facteurs premiers alors qu'il devrait établir une liste de ces constructions, comme ceci:

[
   [(2,0), (7,0)],
   [(2,1), (7,0)],
   [(2,2), (7,0)],
   [(2,0), (7,1)],
   [(2,1), (7,1)],
   ...
]

Le premier factorisation de tous les facteurs possibles est nécessaire, mais la fonction semble revenir juste une factorisation.