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 have no words for this great post such a awe-some information i got gathered. Thanks to Author.
html5 player| html5 video player
Post a Comment