[erlang-questions] Joe

[Joe Armstrong]

Hi Ivan,

This algorithm is not particular obvious. It works as follows.

Suppose I want to compute all permutations of "1234"

Suppose I had a program that could compute all perms of
three elements I could call it like this:

> perms("234"),
["234", "243", "324", "342", "423", "432"].

Now stick a one on the front

     ["1234", "1243", "1324", "1342", "1423", "1432"].

That's almost right. I've now generated a quarter of what I need

Instead of taking out the "1" I could do the same with the "2"

> perms("134").
["134", "143", "314", "341", "413", "431"]

and put the 2 at the front

["2134", "2143", "2314", "2341", "2413", "2431"]

This what the list comprehension does:

  H <- L says take H from L in all possible ways
  T <- perms(L -- [H]) says take T from the set of permutations of L with H
removed

  [ [H|T] || ...]

  means build the list [H|T] with H and T as above

  But how did I compute all permutations of three elements?

  "Suppose I had a function that could compute all permutations of
two elements ..."

Cheers

/Joe

On Mon, Mar 4, 2013 at 8:05 PM, Ivan Carmenates García
<co7eb@REDACTED>wrote:

> Hi all, I’m reading the Making Reliable Distributed Systems in the
> Presence of Software Errors by Joe Armstrong Thesis of 2003 and I found
> this little algorithm using list of compression and there is no way I can
> understand how internally it work.****
>
> ** **
>
> perms([]) -> [[]];****
>
> perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].****
>
> ** **
>
> I did figure out that the recursion does first I mean the call to the
> function T <- perms(L--[H]) but step by step I can not follow.****
>
> First, the function is called using [1,2,3] list so ****
>
> [[1|T] || H <- L, T <- perms([1,2,3]--[1] = [2,3])]****
>
> [[1|[2|T]] || H <- L, T <- perms([2,3]--[2] = [3])]****
>
> [[1|[2|[3|T]]] || H <- L, T <- perms([3]--[3] = [])]****
>
> [[1|[2|[3|[]]]] || H <- L, T <- [])]****
>
> ** **
>
> And now what! What’s the next step?****
>
> ** **
>
> I changed the code in order to print the steps so I can understand but
> even with that the debug is so confuse. Because the order changes, maybe
> because of the recursive thing.****
>
> But I don’t understand why in the head the value 1 is repeated to yield
> the next value [[1,2,3), [1,3,2], …]****
>
> ** **
>
> perms([]) -> [[]];****
>
> perms(L) ->****
>
>       io:format("L = ~p~n", [L]),****
>
>       [[{H,io:format("H = ~p - ", [H])}| {T, io:format("T = ~p~n", [T])}]
> || H <- L, T <- perms(L--[H])].****
>
> ** **
>
> This is the exit****
>
> ** **
>
> 74> test:perms([1,2,3]).****
>
> L = [1,2,3]****
>
> L = [2,3]****
>
> L = [3]****
>
> H = 3 - T = []****
>
> H = 2 - T = [{3,ok}|{[],ok}]****
>
> L = [2]****
>
> H = 2 - T = []****
>
> H = 3 - T = [{2,ok}|{[],ok}]****
>
> H = 1 - T = [{2,ok}|{[{3,ok}|{[],ok}],ok}]****
>
> H = 1 - T = [{3,ok}|{[{2,ok}|{[],ok}],ok}]****
>
> L = [1,3]****
>
> L = [3]****
>
> H = 3 - T = []****
>
> H = 1 - T = [{3,ok}|{[],ok}]****
>
> L = [1]****
>
> H = 1 - T = []****
>
> H = 3 - T = [{1,ok}|{[],ok}]****
>
> H = 2 - T = [{1,ok}|{[{3,ok}|{[],ok}],ok}]****
>
> H = 2 - T = [{3,ok}|{[{1,ok}|{[],ok}],ok}]****
>
> L = [1,2]****
>
> L = [2]****
>
> H = 2 - T = []****
>
> H = 1 - T = [{2,ok}|{[],ok}]****
>
> L = [1]****
>
> H = 1 - T = []****
>
> H = 2 - T = [{1,ok}|{[],ok}]****
>
> H = 3 - T = [{1,ok}|{[{2,ok}|{[],ok}],ok}]****
>
> H = 3 - T = [{2,ok}|{[{1,ok}|{[],ok}],ok}]****
>
> [[{1,ok}|{[{2,ok}|{[{3,ok}|{[],ok}],ok}],ok}],****
>
> [{1,ok}|{[{3,ok}|{[{2,ok}|{[],ok}],ok}],ok}],****
>
> [{2,ok}|{[{1,ok}|{[{3,ok}|{[],ok}],ok}],ok}],****
>
> [{2,ok}|{[{3,ok}|{[{1,ok}|{[],ok}],ok}],ok}],****
>
> [{3,ok}|{[{1,ok}|{[{2,ok}|{[],ok}],ok}],ok}],****
>
> [{3,ok}|{[{2,ok}|{[{1,ok}|{[],ok}],ok}],ok}]]****
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20130304/f4581ce4/attachment.htm>