[erlang-questions] Joe

[Danil Zagoskin]

Hello, Ivan.

I could not figure out what part don't you understand, so I'll try to
explain from ground up.

First, you call perms(L). The comprehension does following:
 1. Take each element of given list and bind it as H for later steps
 2. For each H from step 1 construct list of all other elements L -- [H]
 3. Apply self on list from step 2 to get all permutations of other
elements. To understand this step you need to remember mathematical
induction. We provide simple true result for empty list, so for every list
which is longer than [] we can refer to result of running function on
shorter list. So, in this step we get list of all possible permutations of
elements in L which are not H.
 4. For each element of permutation list we got in step 3, we bind it
(permutation) as T
 5. Prepend H to T and take next permutation from step 4

So, in case of [1,2,3] above steps expand to following:
 (1) H = 1
 - (2) other elements list is [2,3]
 - - (3) perms([2,3]) is list of possible permutations, e.g. [ [2,3], [3,2]
], so there will be two steps "4"
 - - - (4) T = [2,3]
 - - - - (5) emit [1|[2,3]] = [1,2,3]
 - - - (4) T = [3,2] which is second element in result of applying
perms([2,3])
 - - - - (5) emit [1,3,2]
 (1,2) H = 2, L -- [H] = [1,3]
 - - (3) perms([1,3]) is [ [1,3], [3,1] ]
 - - - (4,5) emit [2,1,3]
 - - - (4,5) emit [2,3,1]
 (1,2) H = 3, L -- [H] = [1,2]
 - - (3,4,5) emit [3,1,2], [3,2,1]


2013/3/4 Ivan Carmenates García <co7eb@REDACTED>

> 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
>
>


-- 
---------------------------------------------
Данил Загоскин | +7 906 064 20 47 | z@REDACTED
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20130305/ff31704a/attachment.htm>