<div dir="ltr">Hello, Ivan.<div><br></div><div>I could not figure out what part don't you understand, so I'll try to explain from ground up.</div><div><br></div><div>First, you call perms(L). The comprehension does following:</div>
<div> 1. Take each element of given list and bind it as H for later steps</div><div> 2. For each H from step 1 construct list of all other elements L -- [H]</div><div> 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.</div>
<div style> 4. For each element of permutation list we got in step 3, we bind it (permutation) as T</div><div style> 5. Prepend H to T and take next permutation from step 4</div><div style><br></div><div style>So, in case of [1,2,3] above steps expand to following:</div>
<div style> (1) H = 1</div><div style> - (2) other elements list is [2,3]</div><div style> - - (3) perms([2,3]) is list of possible permutations, e.g. [ [2,3], [3,2] ], so there will be two steps "4"</div><div style>
- - - (4) T = [2,3]</div><div style> - - - - (5) emit [1|[2,3]] = [1,2,3]</div><div style> - - - (4) T = [3,2] which is second element in result of applying perms([2,3])<br> - - - - (5) emit [1,3,2]</div><div style> (1,2) H = 2, L -- [H] = [1,3]</div>
<div style> - - (3) perms([1,3]) is [ [1,3], [3,1] ]</div><div style> - - - (4,5) emit [2,1,3]</div><div style> - - - (4,5) emit [2,3,1]</div><div style> (1,2) H = 3, L -- [H] = [1,2]</div><div style> - - (3,4,5) emit [3,1,2], [3,2,1]</div>
</div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/3/4 Ivan Carmenates García <span dir="ltr"><<a href="mailto:co7eb@frcuba.co.cu" target="_blank">co7eb@frcuba.co.cu</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div lang="ES" link="blue" vlink="purple"><div><p class="MsoNormal"><span lang="EN-US">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.<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US"><u></u> <u></u></span></p><p class="MsoNormal" style="text-autospace:none"><span style="font-size:10.0pt;font-family:"Courier New"">perms([]) -> [[]];<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:14.5pt;font-family:CMTT12"><u></u> <u></u></span></p>
<p class="MsoNormal"><span lang="EN-US">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.<u></u><u></u></span></p><p class="MsoNormal">
<span lang="EN-US">First, the function is called using [1,2,3] list so <u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">[[1|T] || H <- L, T <- perms([1,2,3]--[1] = [2,3])]<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">[[1|[2|T]] || H <- L, T <- perms([2,3]--[2] = [3])]<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">[[1|[2|[3|T]]] || H <- L, T <- perms([3]--[3] = [])]<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">[[1|[2|[3|[]]]] || H <- L, T <- [])]<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New""><u></u> <u></u></span></p>
<p class="MsoNormal"><span lang="EN-US">And now what! What’s the next step?<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US"><u></u> <u></u></span></p><p class="MsoNormal"><span lang="EN-US">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.<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US">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], …]<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US"><u></u> <u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">perms([]) -> [[]];<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">perms(L) -><u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New""> io:format("L = ~p~n", [L]),<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New""> [[{H,io:format("H = ~p - ", [H])}| {T, io:format("T = ~p~n", [T])}] || H <- L, T <- perms(L--[H])].<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US"><u></u> <u></u></span></p><p class="MsoNormal"><span lang="EN-US">This is the exit<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New""><u></u> <u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">74> test:perms([1,2,3]).<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">L = [1,2,3]<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">L = [2,3]<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">L = [3]<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 3 - T = []<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 2 - T = [{3,ok}|{[],ok}]<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">L = [2]<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 2 - T = []<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 3 - T = [{2,ok}|{[],ok}]<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 1 - T = [{2,ok}|{[{3,ok}|{[],ok}],ok}]<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 1 - T = [{3,ok}|{[{2,ok}|{[],ok}],ok}]<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">L = [1,3]<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">L = [3]<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 3 - T = []<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 1 - T = [{3,ok}|{[],ok}]<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">L = [1]<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 1 - T = []<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 3 - T = [{1,ok}|{[],ok}]<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 2 - T = [{1,ok}|{[{3,ok}|{[],ok}],ok}]<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 2 - T = [{3,ok}|{[{1,ok}|{[],ok}],ok}]<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">L = [1,2]<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">L = [2]<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 2 - T = []<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 1 - T = [{2,ok}|{[],ok}]<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">L = [1]<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 1 - T = []<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 2 - T = [{1,ok}|{[],ok}]<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 3 - T = [{1,ok}|{[{2,ok}|{[],ok}],ok}]<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">H = 3 - T = [{2,ok}|{[{1,ok}|{[],ok}],ok}]<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New"">[[{1,ok}|{[{2,ok}|{[{3,ok}|{[],ok}],ok}],ok}],<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New""> [{1,ok}|{[{3,ok}|{[{2,ok}|{[],ok}],ok}],ok}],<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New""> [{2,ok}|{[{1,ok}|{[{3,ok}|{[],ok}],ok}],ok}],<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New""> [{2,ok}|{[{3,ok}|{[{1,ok}|{[],ok}],ok}],ok}],<u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New""> [{3,ok}|{[{1,ok}|{[{2,ok}|{[],ok}],ok}],ok}],<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:"Courier New""> [{3,ok}|{[{2,ok}|{[{1,ok}|{[],ok}],ok}],ok}]]<u></u><u></u></span></p></div></div><br>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br><font face="'courier new', monospace">---------------------------------------------</font><div><font face="'courier new', monospace">Данил Загоскин | +7 906 064 20 47 | <a href="mailto:z@gosk.in" target="_blank">z@gosk.in</a></font></div>
</div>