module Powerset where
{- Expand muliplies of two list of numbers.
For example:
mult_expand [1, 2, 4] [1, 5]
Produces:
[[1,5],[2,10],[4,20]]
-}
mult_expand p [] = p:[]
mult_expand p lst =
map (\x -> map (*x) lst) p
{- expand the powers of x from 0 to exp -}
pows x exp = map (\e -> x^e) [0..exp]
{- expand the powers the first item in a pair
from 0 to the second item in the pair.
-}
powerlst p = pows (fst p) (snd p)
{- One stage of a merge sort -}
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) = if x <= y
then x : merge xs (y:ys)
else y : merge (x:xs) ys
{- Do multiple merges to get an ordered list. -}
bigmerge lsts =
foldl merge [] lsts
{- The complete power set of a list of factor/exponent pairs. For example:
powerset [(2,3),(5,1)]
Produces:
[1,2,4,5,8,10,20,40]
-}
powerset [] = []
powerset (x:xs) =
bigmerge (mult_expand (powerlst x) (powerset xs))
{- Helper function for factor_sqrt.
Finds the last list value less than or equal to the
given limit.
-}
fsqrt lim lastgood [] = lastgood
fsqrt lim lastgood (x:xs) =
if (x > lim) then lastgood
else fsqrt lim x xs
{- Find the last divisor less than the square root,
given the number and its factors
-}
factor_sqrt n factors =
fsqrt (sqrt n) 0 (powerset factors)