views:

711

answers:

16

For example, if the input is 825 the output expected is (0 1 2 0 1). What this means is: 0 two's, 1 three's, 2 five's, 0 seven's and 1 eleven.

Doing this imperatively was quite easy for me. Functional, not so much. Could you please guide me how to go about solving the above problem in a functional way?

Note: Fold/reduce ways will be preferred over explicit recursion. :)

EDIT:

I'd appreciate the direct Haskell/Clojure code instead of a vague description.

+1  A: 

Define a function factor that does exactly two things:

  1. Find a factor of the input number.
  2. Call factor with the result of dividing the input number by the found factor.

You will have to add something to step 1 in case there are no factors (i.e. the number is prime).

You can add another parameter to this function to represent the vector form that your output requires. Start with an empty list, and every time you find a factor, call factor recursively with a new list updated to represent the new factor you just found.

Greg Hewgill
This answer doesn't tell me anything that I already didn't know.
one-zero-zero-one
@Cheryl: Your question doesn't state what you already know, so how are we supposed to know what you know?
Greg Hewgill
@Greg: Well give me direct code if possible. Implementation is where I am stuck.
one-zero-zero-one
Sorry, not sure I can help there. The intersection of my functional languages and your functional languages is the empty set.
Greg Hewgill
@Greg: Use any language you know. It'd be fine.
one-zero-zero-one
@Greg: I said you can use any language you know - you still didn't reply. That means you didn't actually know the answer to this question; you just wrote some vague crap for grabbing reputation points.
one-zero-zero-one
A: 

Code in Ruby.

@arr = []
def factorize(n)
  2.upto(n){|x| (@arr << x; factorize(n/x); return) if n%x == 0}
end
def is_prime(n)
  return false if n <= 1
  2.upto(Math.sqrt(n).to_i){|x| return false if n%x == 0}
  true
end
factorize(245)
1.upto(@arr.max){|each_num| puts @arr.count(each_num) if is_prime(each_num)}

# OUTPUTS 0 0 1 2, meaning ONE 5s and TWO 7s
Bragboy
This is an imperative code. I want a functional algorithm/code, one that doesn't use mutable objects.
one-zero-zero-one
Maybe you don't understand what functional programming means. This link might help: http://en.wikipedia.org/wiki/Functional_programming
one-zero-zero-one
@Cheryl: This IS functional programming.
Clark Gaebel
@Clark: No, it isn't. Did you miss `@arr` in his code?
one-zero-zero-one
Immutability is not a constraint of functionalty. It's absolutely trivial to modify this process to remove the mutable array.
Stefan Kendall
+1  A: 

Here's how I factored it, not sure if its what you're looking for...

factor :: Integer -> [Integer]
factor x = (filter (isFactor x) [1 .. (div x 2)]) ++ [x]
    where
        isFactor num possibleFactor = mod num possibleFactor == 0
Clark Gaebel
Prime factors, yes.
one-zero-zero-one
+1  A: 

Here's a recursive solution in Python. Note, it needs a precomputed array of known primes <= sqrt(number).

def factor(number, primes):
    def divide(num,prime):
        if num%prime:
            return 0
        else:
            return 1+divide(num/prime,prime)

    if number==0 or len(primes)==0 or number<primes[0]:
        return []
    elif number%primes[0]:
        return [0]+factor(number,primes[1:])
    else:
        times=divide(number,primes[0])
        return [times]+factor(number/(primes[0]**times),primes[1:])

if __name__=='__main__':
    print factor(825,[2,3,5,7,11,13,17])
MAK
+2  A: 

Here's some Erlang code that does what you want.

I'm new to Erlang myself, so this probably isn't the BEST way to do it (in fact, I'd appreciate feedback from others).

-module(factor).
-export([factor/1]).

num_times_divides(A, B) ->
    num_times_divides(A, B, 0, 1).

num_times_divides(A, B, Count, Power) ->
    if
        (A rem B) == 0 -> num_times_divides(A div B, B, Count + 1, Power * B);
        true -> {Count, Power}
    end.

factor(N) ->
    factor(N, [], 2).
factor(1, Factor_List, _) ->
    Factor_List;
factor(N, Factor_List, F) ->
    {Count, Quotient} = num_times_divides(N, F),
    factor(N div Quotient, [Count | Factor_List], F + 1).
Seth
+5  A: 

I assume from your question you can produce a lazy list of primes. This is a direct clojure code, with recursion, though. It could also be made more efficient.

(defn div-times
  "How many times can n divideded by d"
  [n d]
    (loop [n n
           d d
           times 0]
      (if (= 0 (mod n d))
        (recur (/ n d) d (inc times))
        [n times])))

(defn factorize
  [n]
    (loop [n n
           factors []
           primes (primes)]
      (if (<= (first primes) n)
        (let [[n times] (div-times n (first primes))]
          (recur n (conj factors times) (next primes)))
        factors))))
Adam Schmideg
+3  A: 

Here is my own Haskell trial. I'm still a Haskell newbie myself (but not really a newbie as a functional programmer), hence there is probably many possible improvements. I could probably find some myself thinking harder, but it works as expected and I see no obvious algorithmic slowness.

The code includes a primes number generator as one was necessary for a complete answer. OP could have provided his one primes generator as he said he know how to do it, it would have avoided including it in answers.

I don't see much difference between what I wrote functionaly using Haskell and what I could have wrote iteratively. The main difficulty was probably the strange expected format of the result.

module Primes
where

isPrime :: Integer -> Bool
isPrime a = isPrimeHelper a primes

isPrimeHelper a (p:ps)
 | p*p > a = True
 | a `mod` p == 0 = False
 | otherwise = isPrimeHelper a ps

-- List of prime numbers
primes :: [Integer]
primes = 2 : filter isPrime [3..]

countFactor x p
 | x `mod` p == 0 = 1 + countFactor (x `div` p) p
 | otherwise = 0

cleanFactor x p
 | x `mod` p == 0 = cleanFactor (x `div` p) p
 | otherwise = x

nbFactors x (p:ps)
 | x == 1 = []
 | x `mod` p == 0 = (countFactor x p) : (nbFactors (cleanFactor x p) ps)
 | otherwise = 0 : (nbFactors x ps)

-- List of number of times each prime number divides x
-- (tricky because the result is supposed to put 0 for non dividers primes,
-- but only for those smaller than larger prime divider...)
factor :: Integer -> [Integer]
factor x = nbFactors x primes

Unit tests are included below. As I use TDD I had to write them anyway.

module Main
where

import Test.HUnit
import Primes

test1 = True  ~=? (isPrime 2)
test2 = True  ~=? (isPrime 3)
test3 = False ~=? (isPrime 4)
test4 = True  ~=? (isPrime 5)

test5 = 2 ~=? (primes !! 0)
test6 = 7 ~=? (primes !! 3)

test7 = 2 ~=? (countFactor 825 5)
test8 = 0 ~=? (countFactor 825 17)
test9 = 33 ~=? (cleanFactor 825 5)

test10 = [0, 1, 2, 0, 1] ~=? (factor 825)

tests = TestList [ test1, test2, test3, test4,
                   test5, test6,
                   test7, test8, test9,
                   test10
                 ]

main = do runTestTT tests

Below is a better version suggested by yatima2975 that needs less calls to mod and div (that can be quite costly whith large numbers).

module Primes
where

isPrime :: Integer -> Bool
isPrime = isPrimeHelper primes

isPrimeHelper (p:ps) a
 | p*p > a = True
 | a `mod` p == 0 = False
 | otherwise = isPrimeHelper ps a

-- List of prime numbers
primes :: [Integer]
primes = 2 : filter isPrime [3..]

countClean = countCleanHelper 0
countCleanHelper e x p = case divMod x p of
    (x',0) -> countCleanHelper (e+1) x' p
    _ -> (e,x)

nbFactors _ 1 = []
nbFactors (p:ps) x = let (exponent, rest) = countClean x p 
    in exponent : nbFactors ps rest


-- List of number of times each prime number divides x
-- (tricky because the result is supposed to put 0 for non dividers primes,
-- but only for those smaller than larger prime divider...)
factor :: Integer -> [Integer]
factor = nbFactors primes

And the updated tests

module Main
where

import Test.HUnit
import Primes

test1 = True  ~=? (isPrime 2)
test2 = True  ~=? (isPrime 3)
test3 = False ~=? (isPrime 4)
test4 = True  ~=? (isPrime 5)

test5 = 2 ~=? (primes !! 0)
test6 = 7 ~=? (primes !! 3)

test7 = (2,33) ~=? (countClean 825 5)
test8 = (0,825) ~=? (countClean 825 17)

test10 = [0, 1, 2, 0, 1] ~=? (factor 825)

tests = TestList [ test1, test2, test3, test4,
                   test5, test6,
                   test7, test8,
                   test10
                 ]

main = do runTestTT tests
kriss
That's a fine solution for a newbie! The only thing I can come up with to improve it further is cutting down on the number of times `x mod p` is computed since that can get pretty expensive for larger numbers. Here's what I came up with (code in comments is ugly and short variable names due to comment size restriction, sorry!):`nbFactors 1 _ = []`/`nbFactors x (p:ps) = exponent : nbFactors rest ps where`/` (exponent,rest) = countClean 0 x`/` countClean e y = case divMod y p of`/` (y',0) -> countClean (e+1) y`/` _ -> (e,y)`
yatima2975
Okay, here a pastebin for easier reading: http://pastebin.com/a6btEb2q
yatima2975
@yatima2975: Thanks for the enhancement. The only thing I do not really like is passing current prime divider p to countClean through the closure. It's a bit too hidden for my taste, so I slightly changed your proposal using explicit intermediate helper functions.
kriss
@yatima2975: also removed some syntaxic noise using partial functions, that the kind of tricks I love with Haskell :-)
kriss
Why the downvote ? Just wondering.
kriss
+1  A: 

My take (in Scala):

object PrimeFactors {

  // Generates infinite prime numbers' sequence using Eratosthenes' Seieve
  lazy val primes = {
    def sieve(s: Stream[Int]): Stream[Int] = s match {
      case x #:: xs => x #:: sieve(xs.filter(_ % x != 0))
    }
    sieve(Stream from 2)
  }

  // Divides a by b until the division gives a non-integral number.
  // Returns number of times division was carried out followed by the 
  // number obtained on final division.
  // For example, dividex(45, 3) gives (2, 5).
  def dividex(a: Double, b: Double) = {
    val s = Stream.iterate(a)(_ / b)
    val i = s.indexWhere(x => x.toInt != x) - 1
    (i, s(i).toInt)
  }

  def factorsOf(n: Int) = {
    def factors(i: Int, n: Int): List[Int] = {
      val (freq, n0) = dividex(n, primes(i))
      if(n0 > 1)
        freq :: factors(i + 1, n0)
      else
        freq :: Nil
    }
    factors(0, n).mkString("(", " ", ")")
  }

  def main(args: Array[String]) {
    val n = readInt()
    println(factorsOf(n))
  }
}
missingfaktor
Another great example of how badly StackOverflow's syntax highlighting sucks. \*Sigh!*
missingfaktor
+2  A: 

A Clojure solution that uses recursion to define a good abstraction

(defn map-state
  "Return a lazy seq of the state machine f's output when given the input in
coll and a initial state.  f must be defined so that (f state input) returns a
seq of the output and the next state."
  [f initial coll]
  (lazy-seq
   (if (seq coll)
     (let [[out state] (f initial (first coll))]
       (cons out (map-state f state (next coll)))))))

(def primes [2 3 5 7 11 13 17 19])

(defn factor
  "Return a seq of the exponents of the prime powers of n"
  [n]
  (letfn [(get-count [n prime]
        (if (= n 1)
          [:end 1]
          (let [divs (iterate #(/ % prime) n)
            [zeros rest] (split-with #(zero? (mod % prime)) divs)]
        [(count zeros) (first rest)])))]
    (take-while #(not= % :end) (map-state get-count n primes))))
Brian
+3  A: 

How about:

(defn factors [n]
  (if (= n 1) '()
      (loop [i 2]
        (if (= 0 (mod n i)) (cons i (factors (/ n i)))
            (recur (inc i))))))

Use it like:

(factors 1000) -> (2 2 2 5 5 5)
John Lawrence Aspden
+1  A: 

A fully tail recursive version

(defn factors [n]
  (loop [acc [] i 2 n n]
    (cond (= n 1)         acc
          (= 0 (mod n i)) (recur (conj acc i),      i , (/ n i) )
          :else           (recur         acc , (inc i),      n  ))))

Try:

(factors 1000) -> [2 2 2 5 5 5]
John Lawrence Aspden
+1  A: 

Slightly more complicated than it needs to be, but goes much faster:

(defn factors [n]
  (loop [acc '() i 2 n n]
    (cond (= n 1)         acc
          (< n (* i i))   (cons n acc)
          (= 0 (mod n i)) (recur (cons i acc) i (/ n i) )
          :else           (recur acc     (inc i)     n  ))))

Try:

(time (factors 123456789012345678901234567890)) ;;7 msec
John Lawrence Aspden
A: 

Haskell version that gives the actual factors, where primes is an infinite lazy list of primes:

primefactors :: Integer -> [Integer]
primefactors 1 = []
primefactors x = [factor] ++ (primefactors (x `quot` factor))
  where factor = (head [n | n <- primes, (x `mod` n) == 0])

Usage:

*Main> primefactors 65535
[3,5,17,257]
You
+1  A: 

a C# implementation

public void Test()
{
    var factors = Factorize(825)
        .GroupBy(x => x)
        .ToDictionary(x => x.Key, x => x.Count());

    var outputs = Primes()
        .TakeWhile(x => x <= factors.Max(y => y.Key))
        .Select(x => factors.ContainsKey(x) ? factors[x] : 0)
        .Select(x => x.ToString())
        .ToArray();

    Console.WriteLine(String.Join(", ", outputs));
}

public IEnumerable<int> Factorize(int input)
{
    int first = Primes()
        .TakeWhile(x => x <= Math.Sqrt(input))
        .FirstOrDefault(x => input % x == 0);
    return first == 0
            ? new[] { input }
            : new[] { first }.Concat(Factorize(input / first));
}

public IEnumerable<int> Primes()
{
    var ints = Enumerable.Range(2, Int32.MaxValue - 1);
    return ints.Where(x => !ints
                                .TakeWhile(y => y <= Math.Sqrt(x))
                                .Any(y => x % y == 0));
}

output:

0, 1, 2, 0, 1
Handcraftsman
+2  A: 

A must shorter Haskell solution that uses unfoldr. The list of exponents is lazy and never has any trailing zeros. The list Data.Numbers.Primes.primes is built lazily and the space is not released, I think you can use (wheelSieve 6) instead of "primes" if this is a space leak for you.

import Data.Numbers.Primes -- cabal install primes
import Data.List(unfoldr)

countFactors n = unfoldr iter (n,primes) where
  iter (x,p:ps) | x < p = Nothing
                | otherwise = let countP y acc = case quotRem y p of
                                                   (y2,0) -> countP y2 $! succ acc
                                                   _ -> (acc,(y,ps))
                              in Just (countP x 0)
Chris Kuklewicz
A: 

In Factor:

USING: assocs kernel math.primes math.primes.factors sequences ;
: count-factors ( n -- seq )
    group-factors [ [ first ] map supremum primes-upto ] keep
    [ at 0 or ] curry map ;

Demo:

825 count-factors .
V{ 0 1 2 0 1 }
Samuel Tardieu