[Haskell] [Oz] Function that computes the permutation of a list

Mozart Oz Programming Language

declare
fun {Permutation L}
   case L
   of nil then [nil]
   [] H|T then
      {FoldR
       {Map
 {Permutation T}
 fun {$ X}
    % Inser H into all position
    IntFrom in
    fun lazy {IntFrom K} K|{IntFrom K+1} end
    {Map {List.take {IntFrom 0} {List.length X}+1}
     fun {$ Pos}
        {FoldR X (fun {$ J K}
       case K of nil then nil
       [] S#I then
          if I \= Pos-1 then
      {Append [J] S}#(1+I)
          else
      {Append [H J] S}#(1+I)
          end
       end
    end) ({List.drop [H] Pos}#0)
        }.1
     end}
 end
       }
       fun {$ X Y}
   {Append X Y}
       end nil
      }
   end
end

%{Browse {Permutation [a]}} % shows [[a]]
%{Browse {Permutation nil}} % shows [nil]
{Browse {Permutation [a b c]}} % shows [[c b a] [c a b] [a c b]
                                       % [b c a] [b a c] [a b c]]

Haskell Programming Language

-- function that computes the permutations of a list
-- permutation ["a","b","c"]
permutation            :: [a] -> [[a]]
permutation xs0        =  xs0 : perms xs0 []
  where
    perms []     _  = []
    perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutation is)
      where interleave    xs     r = let (_,zs) = interleave' id xs r in zs
            interleave' _ []     r = (ts, r)
            interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
                                     in  (y:us, f (t:y:us) : zs)

Comments

Popular posts from this blog

225019099301.apps.googleusercontent.com

Backup MySQL to Azure Storage in 30 Seconds

Generate GoDaddy SSL Certificate (.crt) for Azure Websites (.pfx)