Implementare un procedimento fattorizzazione in Haskell
-
13-09-2019 - |
Domanda
domanda 266 a Project Euler e dopo un po 'di la ricerca, ha trovato questo metodo individuazione dei rapidamente i fattori di un numero. Quello che fate è trovare tutte le permutazioni dei fattori primi di un numero:. Questi sono i suoi fattori
Ho già un modulo per trovare i fattori di potenza primi di un numero, ad esempio:
Main> primePowerFactors 196
[(2,2),(7,2)]
Questo è fondamentalmente dimostrando che: 2^2 * 7^2 == 196
. Da qui voglio trovare tutte le permutazioni di tali competenze, a dare i fattori di 196 nel seguente modo:
- (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
Sono venuto con la seguente:
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)
Ma il mio problema è che factors
non funziona correttamente. Voglio che per permutare attraverso tutti i possibili valori di esponente per ogni fattore primo e poi trovare il prodotto per dare il fattore. Come può essere modificato per restituire i giusti fattori di n
Soluzione
per un po 'di golf codice che ho scritto un bel funzione set potere che è piuttosto semplice.
powerSet [] = []
powerSet (x:xs) = xs : map (x:) (powerSet xs) ++ (powerSet xs)
Una carenza di questo algoritmo è che non include la serie originale, tuttavia, che è perfetto per voi in quanto non guardare come si desidera.
combinare questo con un modo per convertire il vostro primePowerFactors n
in una lista di interi, diciamo
ppfToList = concatMap (\(x,y)->replicate y x)
utilizzando questi aiutanti, un elenco di fattori da un numero n è generato con
factors n = nub . map product . powerSet . ppfToList . primePowerFactors $ n
-- will be out of order, you can add a call to `sort` to fix that
Questo tipo di algoritmo è probabilmente un po 'più difficile da esprimere in termini di una lista di comprensione.
Altri suggerimenti
Prima di tutto, facs
è la funzione identità:
facs (x,y) = (x,y)
Il y
è legato nel match modello sul lato sinistro, mentre probabilmente si voleva che fosse il y
dalla lista comprensione. I nomi delle variabili legate in una list comprehension sono locali a quella comprensione e non possono essere utilizzate in un ambito diverso, come la clausola where
.
Inoltre, il y
nella lista di comprensione viene calcolata solo dal ultimi fattori dell'esponente:
y <- [0..(snd $ last $ primePowerFactors n)]
Per ogni fattore è proprio esponente deve essere considerata, non solo sempre l'esponente del ultimo fattore.
Un problema più fondamentale è che il tipo di ritorno della funzione factors
non sembra corrispondere è intenzione:
*Euler> :t factors
factors :: Integer -> [(Integer, Int)]
Questo restituisce un elenco di potenze di fattori primi mentre dovrebbe produrre un elenco di questi costrutti, in questo modo:
[
[(2,0), (7,0)],
[(2,1), (7,0)],
[(2,2), (7,0)],
[(2,0), (7,1)],
[(2,1), (7,1)],
...
]
È necessaria la scomposizione in fattori primi di tutti i possibili fattori, ma la funzione sembra tornare solo una fattorizzazione in numeri primi.