algorithm - Big O-Notation on my permutation function coded scala -

below code implementation of permuting elements in list, coded scala

def permute(list:list[int]):list[list[int]] =   if(list.isempty) {     nil   } else {     var result: list[list[int]] = nil      def recursion(plist: list[int], rlist: list[int]): unit = {       if (rlist.isempty)         result ++= plist :: nil        if (plist != list.reverse)         (i <- rlist.indices) {           val x = rlist(i)           val xdropped = drop(x, rlist)           val newplist = plist ++ (x :: nil)           recursion(plist ++ (x :: nil), xdropped)         }     }      recursion(nil, list)     result   }  def drop(x:int, list:list[int]) = list.filter(_ != x) val result = permute(xs) result.foreach(println) println(result.length) 

and console show below.

console result concern big-o notation on function, , how calculate it?

i'd hope show detail description of method results big-o notation

thanks, have nice day.

well, algorithm far complicated because of lot of suboptimal steps. scala api overwhelming if first @ , come imperative language, understandable, makes algorithm hard analyse.

what clear problem, is, algorithm has exponential because enumerates exponentially many permutations.

the dominating factor complexity recursive call each element in input list 1 element smaller. recursion depth number of elements in input , number of recursive calls in each step number. complexity therefore o(n^n) = o(2^(n*ld(n)))

now complexity if returned results in optimal way, using result ++= plist :: nil. first, not functional style, which, without reason, should avoided. if it, should use mutable structure (e.g. listbuffer) or @ least prepend list. here, append list linear in length. whole thing quadratic in number of elements append list exponential. complexity in fact

o((2^(n*ld(n)))^2) = o(2^(2*n*ld(n)))

and constants in exponent make difference in o-notation.

replacing result ++= plist :: nil result = plist :: result gives algorithm optimal asymptotic complexity , makes considerably faster.

there few other issues algorithm not influence asymptotic complexity:

• there no need iterate on indices i <- rlist.indices, can directly iterate on elements x <- rlist. faster index-base access list takes linear time.
• your method drop filters list remove 1 element. can achieved simpler , faster if use set instead of list can directly , efficiently remove elements.
• you append plist appending list: plist ++ (x :: nil) prepend list, less convoluted , faster: x :: plist. also, there :+ operator appends 1 element. not have put element list append it.

here cleaned-up version of code:

def permute(list:list[int]):list[list[int]] =   if(list.isempty) {     nil   } else {     var result: list[list[int]] = nil      def recursion(plist: list[int], rlist: list[int]): unit = {       if (rlist.isempty)         result = plist :: result        if (plist != list.reverse)         (x <- rlist) {           val xdropped = drop(x, rlist)           val newplist = x :: plist           recursion(newplist, xdropped)         }     }      recursion(nil, list)     result   } 

this quite fast.

without thinking performance have done this:

def perm[t](elements: set[t]): list[list[t]] =   if(elements.isempty)     list(nil)   else     {       element <- elements.tolist       rest <- perm(elements - element)     } yield       element :: rest 

this cleaner , simpler , fast optimized version of code. actually, surprised cleaned-up version faster, there 2 reasons: firstly, have iterate on elements on set anyway, being able remove single element not of advantage, , iteration on list faster on set. secondly, algorithm iterates on result set , transforms elements, seems slower building complete results.

this version fast or little bit faster cleaned-up version:

def perm[t](elements: list[t], result: list[t]): list[list[t]] =   if(elements.isempty)     list(result)   else     {       element <- elements       res <- perm(elements.filter(_!=element), element :: result)     } yield res def perm[t](elements: list[t]): list[list[t]] = perm(elements, nil) 

probably there faster, imperative way it, should "good enough". version in standard library of scala seems lot slower this.

and there of course faster , shorter functional version using insert operation on lists:

def insert[t](elem: t, list: list[t]) =   (0 list.size).map{      pos => list.take(pos) ++ (elem :: list.drop(pos))   } 

so can this:

def perm[t](elements: list[t]) =   elements.foldleft(list(list[t]())){     (results, element) => results.flatmap{insert(element,_)}   } 

so following direct approach "permute n elements permuting n-1 , inserting next element @ every position" turns out shortest , fastest...