Реализация метода факторизации в Haskell - PullRequest
Новая
       13

Реализация метода факторизации в Haskell

1 голос
/ 06 декабря 2009

Я делаю вопрос 266 в Project Euler и после небольшого поиска нашел этот метод быстрого поиска факторов числа. Что вы делаете, так это находите все перестановки простых факторов числа: это его факторы.

У меня уже есть модуль, чтобы найти основные коэффициенты мощности числа, например: 

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

Это в основном показывает, что: 2^2 * 7^2 == 196. Отсюда я хочу найти все сочетания этих сил, чтобы таким образом вычислить факторы 196:

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

Я придумал следующее: 

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)

Но моя проблема в том, что factors не работает должным образом. Я хочу, чтобы он переставил все возможные значения показателя степени для каждого простого множителя, а затем нашел произведение, чтобы дать множитель. Как его можно изменить, чтобы получить только факторы n ?

Ответы [ 2 ]

2 голосов
/ 07 декабря 2009

для некоторого гольф-кода я написал хорошую функцию набора мощности, которая довольно проста. 

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

Недостатком этого алгоритма является то, что он не включает в себя оригинальный набор, однако он идеально подходит для вас, поскольку он не выглядит так, как вы этого хотите.

в сочетании с возможностью конвертировать primePowerFactors n в список целых чисел, скажем, 

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

с использованием этих помощников, список факторов из числа n генерируется с 

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

Этот вид алгоритма, вероятно, немного сложнее выразить в терминах понимания списка.

1 голос
/ 06 декабря 2009

Прежде всего, facs - это функция идентификации: 

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

y связан в сопоставлении с образцом с левой стороны, в то время как вы, вероятно, предполагали, что это будет y из списка. Имена переменных, связанные в понимании списка, являются локальными по отношению к этому пониманию и не могут использоваться в другом объеме, например, в предложении where.

Кроме того, y в понимании списка вычисляется только из последнего показателя факторов: 

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

Для каждого фактора следует учитывать его собственный показатель, а не только показатель последнего.

Более фундаментальная проблема заключается в том, что тип возвращаемого значения функции factors не соответствует ее намерению: 

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

Возвращает список степеней простых факторов, в то время как должен генерировать список этих конструкций, например: 

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

Необходима простая факторизация всех возможных факторов, но функция, кажется, возвращает только одну простую факторизацию.

...