perms([]) -> [[]]; perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].I have entire post about this terse little gem, including the Java equivalent (rather less terse!); see Erlang: so awesome it makes my brain bleed.
It seemed rather reasonable to try this in Scala. It's a functional programming language with list comprehensions so surely it will be pretty terse! My first draft as a Scala newb:
def perms[T](L: List[T]):List[List[T]] = L match { //permutations of a single element is simply a list containing a list with that element case head :: Nil => List(List(head)) case head :: tail => { //not quite sure how to dodge use of the result var to accumulate results :( var result = List[List[T]]() for (head <- L; tail <- perms(L-head)) result = (head :: tail) :: result result } case Nil => List[List[T]]() }Much nicer than the Java version but it doesn't hold a candle to Erlang for terse! It does however have the marked benefit of being vastly easier to read and comprehend ;) I wish I knew how to get rid of the result var :(
For reference, the Java equivalent (written to clearly express what is happening more than to be as lean as possible):
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Perms { public static void main(String[] argv) { System.out.println(perms(Arrays.asList("A", "B", "C"))); } public static List<List<String>> perms(List<String> input) { List<List<String>> output = new ArrayList<List<String>>(); for (String H : input) { //L--[H] List<String> LminusH = new ArrayList<String>(input); LminusH.remove(H); if (LminusH.isEmpty()) { //[H|T] when T is empty output.add(new ArrayList<String>(Arrays.asList(H))); } else { for (List<String> T : perms(LminusH)) { //a list made up of [H|T] List<String> HT = new ArrayList<String>(); HT.add(H); HT.addAll(T); output.add(HT); } } } return output; } }
3 comments:
I'm just learning Erlang and I've just written a concurrent version of perms which although longer and less elegant seems much faster. Try it with a 10 element list. I get the feeling it's linear (provided we have enough processes). Try:
perms:start([a,b,c,d,e,f,g,h,i,j]). with the following program:
-module(perms).
-export([perms/2,addAll/2,start/1,printAll/0,f/2]).
start(L) ->
Pid1=spawn(perms,printAll,[]),
perms(L,Pid1).
perms([],Pid) -> Pid![];
perms([H|T],Pid) ->
Pid1 = spawn(perms,f,[H,Pid]),
perms(T,Pid1).
f(H,Pid) -> receive
L -> g(H,L,Pid),
f(H,Pid)
end.
g(H,[],Pid) -> Pid![H];
g(X,[H|T],Pid) ->
Pid![X|[H|T]],
Pid1=spawn(perms,addAll,[H,Pid]),
g(X,T,Pid1).
addAll(H,Pid) ->
receive
L ->Pid![H|L],
addAll(H,Pid)
end.
printAll()->
receive
L -> io:format("~w.~n",[L]),
printAll()
end.
Scala can give you a version pretty close to Erlang's see : http://stackoverflow.com/questions/5056790/scala-permutation-of-factorials
I strongly disagree with "vastly easier to read and comprehend" with respect to Scala.
The only key difference I notice the Scala and Erlang snippets is that Erlang employs fewer glyphs than Scala to express the same logic. I find this much easier to read and comprehend and, with respect to language constructs, I question anyone's reasoning why a verbose expression (and even a wall of text) is easier to comprehend than a terse one.
Maybe this is just how my brain works, but the more glyphs per atomic unit of information or reasoning, the harder I find it to read and comprehend what's going on.
Perhaps I should set Scala aside and learn Erlang, it looks to be incredibly succinct at what it does.
Post a Comment