Die Implementierung eines Verfahrens Faktorisierung in Haskell

Question

Ich tue Frage 266 bei Project Euler und nach ein bisschen suchen, gefunden dieser Methode zu finden schnell die Faktoren einer Zahl. Was Sie tun, ist es, alle Permutationen der Primfaktoren einer Zahl finden. Dies sind seine Faktoren

Ich habe bereits ein Modul die Primärenergiefaktoren eine Zahl zu finden, zum Beispiel:

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

Dies zeigt im Grunde, dass: 2^2 * 7^2 == 196. Von hier aus möchte ich alle Permutationen dieser Befugnisse zu finden, die Faktoren von 196 thusly zu geben:

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

ich kam mit dem folgenden:

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)

Aber mein Problem ist, dass factors nicht richtig funktioniert. Ich will es durch alle möglichen Werte des Exponenten für jeden Primfaktor permutieren und dann das Produkt zu finden, den Faktor zu geben. Wie kann es die nur die Faktoren von n

zurückzukehren modifizierenden

Answer 1

für einige Codes Golf i schrieb eine nette Potenzmenge Funktion, die recht einfach ist.

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

Ein Mangel dieses Algorithmus ist, dass es nicht den ursprünglichen Satz jedoch nicht enthalten, die für Sie perfekt ist, da es sieht nicht, wie Sie es möchten.

kombiniert dies mit einer Art und Weise Ihre primePowerFactors n in eine Liste von ints zu konvertieren, kann sagen,

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

diese Helfer verwenden, eine Liste von Faktoren, die von einer Anzahl n wird mit

erzeugt

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

Diese Art von Algorithmus ist wahrscheinlich ein bisschen härter in Bezug auf eine Liste Verständnis zum Ausdruck bringen.

Answer 2

Zu allererst facs ist die Identitätsfunktion:

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

Die y in der Mustererkennung auf der linken Seite gebunden, während Sie wahrscheinlich beabsichtigt, die y aus der Liste Verständnis zu sein. Variablennamen in einer Liste Verständnis gebunden sind lokal für dieses Verständnis und können nicht in einem anderen Bereich wie die where Klausel verwendet werden.

Auch wird der y in der Liste Verständnis nur aus den letzten Faktoren Exponenten berechnet:

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

Für jeden Faktor einer eigener Exponent ist in Betracht gezogen werden sollte, nicht nur immer der Exponent des letzten Faktors.

Ein grundlegenderes Problem ist, dass der Rückgabetyp der factors Funktion nicht übereinstimmen scheint es ist Absicht:

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

Dies gibt eine Liste der Zuständigkeiten von Primfaktoren, während er eine Liste dieser Konstrukte produzieren sollte, wie folgt aus:

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

Die Primfaktorzerlegung aller möglichen Faktoren benötigt wird, aber die Funktion scheint nur eine Primfaktorzerlegung zurückzukehren.