<div>Hi Ivan,</div><div><br></div><div>This algorithm is not particular obvious. It works as follows.</div><div><br></div><div>Suppose I want to compute all permutations of "1234"</div><div><br></div><div>Suppose I had a program that could compute all perms of</div>
<div>three elements I could call it like this:</div><div><br></div><div>> perms("234"),</div><div>["234", "243", "324", "342", "423", "432"].</div><div>
<br></div><div>Now stick a one on the front</div><div><br></div><div> ["1234", "1243", "1324", "1342", "1423", "1432"].</div><div><br></div><div>That's almost right. I've now generated a quarter of what I need </div>
<div><br></div><div>Instead of taking out the "1" I could do the same with the "2"</div><div><br></div><div>> perms("134").</div><div>["134", "143", "314", "341", "413", "431"]</div>
<div><br></div><div>and put the 2 at the front</div><div><br></div><div>["2134", "2143", "2314", "2341", "2413", "2431"]</div><div><br></div><div>This what the list comprehension does:</div>
<div><br></div><div> H <- L says take H from L in all possible ways</div><div> T <- perms(L -- [H]) says take T from the set of permutations of L with H removed</div><div><br></div><div> [ [H|T] || ...]</div><div>
<br></div><div> means build the list [H|T] with H and T as above</div><div><br></div><div> But how did I compute all permutations of three elements?</div><div> </div><div> "Suppose I had a function that could compute all permutations of</div>
<div>two elements ..."</div><div><br></div><div>Cheers</div><div><br></div><div>/Joe</div><br><div class="gmail_quote">On Mon, Mar 4, 2013 at 8:05 PM, Ivan Carmenates García <span dir="ltr"><<a href="mailto:co7eb@frcuba.co.cu" target="_blank">co7eb@frcuba.co.cu</a>></span> wrote:<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>