{"id":4047,"date":"2018-01-30T12:18:03","date_gmt":"2018-01-30T12:18:03","guid":{"rendered":"http:\/\/www.dyalog.com\/blog\/?p=4047"},"modified":"2018-01-30T14:56:21","modified_gmt":"2018-01-30T14:56:21","slug":"permuting-internal-letters","status":"publish","type":"post","link":"https:\/\/www.dyalog.com\/blog\/2018\/01\/permuting-internal-letters\/","title":{"rendered":"Permuting Internal Letters"},"content":{"rendered":"<h2>Friday Afternoon<\/h2>\n<p>It&#8217;s something of a custom in Dyalog to send a &#8220;fun&#8221; e-mail to the group on Friday afternoons. My gambit for this past Friday was:<\/p>\n<pre><code class=\" language-apl\">   x \u2190' according to research it doesn''t matter'\r\n   x,\u2190' what order the letters in a word are'\r\n   x,\u2190' the human mind can still read it'\r\n   x,\u2190' the only important thing is that'\r\n   x,\u2190' the first and the last letters are in the right place'\r\n\r\n   \u220a ' ',\u00a8 {(1\u2191\u2375),({\u2375[?\u2368\u2262\u2375]}1\u2193\u00af1\u2193\u2375),(-1&lt;\u2262\u2375)\u2191\u2375}\u00a8 (' '\u2218\u2260 \u2286 \u22a2) x\r\n aroidnccg to reasrech it dneso't mttear waht order the ltreets \r\n      in a wrod are the hmaun mnid can sltil read it the olny \r\n      imartpnot tihng is that the fsrit and the lsat lterets \r\n      are in the rhigt palce<\/code><\/pre>\n<p>(The research: <a href=\"http:\/\/www.mrc-cbu.cam.ac.uk\/people\/matt.davis\/Cmabrigde\/rawlinson\/\" target=\"_blank\">http:\/\/www.mrc-cbu.cam.ac.uk\/people\/matt.davis\/Cmabrigde\/rawlinson\/<\/a>)<\/p>\n<h2>Code Golfing<\/h2>\n<p>The code golfers were not long in responding:<\/p>\n<pre><code class=\" language-apl\">   \u220a{' ',\u2375[1,(1+?\u23680\u2308\u00af2+n),n\/\u23681&lt;n\u2190\u2262\u2375]}\u00a8(' '\u2218\u2260\u2286\u22a2)x     \u235d fa\r\n   \u220a{' ',\u2375[\u222a1,{\u2375,\u2368?\u2368\u2375-1}\u2262\u2375]}\u00a8(' '\u2218\u2260\u2286\u22a2)x              \u235d fb\r\n   '\\S+'\u2395r{{\u2375[\u222a1,{\u2375,\u2368?\u2368\u2375-1}\u2262\u2375]}\u2375.Match}x             \u235d fc\r\n   \u220a{' ',\u2375[n\u21911,(1+?\u23680\u2308\u00af2+n),n\u2190\u2262\u2375]}\u00a8(' '\u2218\u2260\u2286\u22a2)x        \u235d fd\r\n<\/code><\/pre>\n<p>In defense of the original expression, it can be said that it follows the pattern:<\/p>\n<ul>\n<li>cut into words <code class=\" language-apl\">\u00a0\u00a0 \u00a0 \u00a0 \u00a0\u00a0\u00a0 (' '\u2218\u2260 \u2286 \u22a2) x\u00a0<\/code> also<code class=\" language-apl\">\u00a0' '(\u2260\u2286\u22a2)x<\/code><\/li>\n<li>permute each word<code class=\" language-apl\">\u00a0\u00a0\u00a0\u00a0\u00a0 {(1\u2191\u2375),({\u2375[?\u2368\u2262\u2375]}1\u2193\u00af1\u2193\u2375),(-1&lt;\u2262\u2375)\u2191\u2375}\u00a8<\/code><\/li>\n<li>undo the cut<code class=\" language-apl\">\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u220a ' ',\u00a8<\/code><\/li>\n<\/ul>\n<p>That is, the pattern is &#8220;permute <em>under<\/em> cut&#8221;. Moving the <code class=\" language-apl\">' ',<\/code> into the permuting function, while shortening the overall expression, obscures this pattern.<\/p>\n<h2>Golfing for Speed<\/h2>\n<p>One of the code golfers was undaunted by the highfalutin&#8217; functional programming argument. Changing tack, he claimed to be golfing for speed (while himself travelling at 900 kph):<\/p>\n<pre><code class=\" language-apl\">fe\u2190{\r\n  p\u21901+0,\u2378\u2375=' '           \u235d start of each word\r\n  n\u21900\u2308\u00af3+\u00af2-\/p,2+\u2262\u2375      \u235d sizes of windows to be shuffled\r\n  \u2375[\u220ap+?\u2368\u00a8n]@((\u2373\u00af1+\u2262\u2375)~p\u2218.-0 1 2)\u22a2\u2375\r\n}\r\n\r\n   cmpx 'fe x' 'fb x' 'fc x' 'fd x'\r\n  fe x \u2192 4.27E\u00af5 |    0% \u2395\u2395\u2395\u2395\r\n* fb x \u2192 1.05E\u00af4 | +145% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\r\n* fc x \u2192 3.39E\u00af4 | +692% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\r\n* fd x \u2192 1.11E\u00af4 | +159% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\r\n<\/code><\/pre>\n<p>The question was then posed whether the algorithm can be &#8220;flattened&#8221; further; that is, whether the expression <code class=\" language-apl\">\u220ap+?\u2368\u00a8n<\/code> in function <code class=\" language-apl\">fe<\/code> can be done without <em>each<\/em>. The answer is of course yes (else I wouldn&#8217;t be writing this blog post :-). Flattening, or avoiding the creation of nested arrays, has the potential to reduce memory consumption and increase efficiency, because there is more potential for the interpreter to perform optimized sequential or even parallel operations.<\/p>\n<h2>Partitioned Random Permutations<\/h2>\n<p>In the old days, before general arrays, before the <em>each<\/em> and <em>rank<\/em> operators, ingenious techniques were devised for working with &#8220;partitioned&#8221; arrays: A boolean vector with a leading 1 specifies a partition on a corresponding array with the same length, basically what we can now do with <code class=\" language-apl\">\u2282<\/code> or similar facility. A detailed description can be found in Bob Smith&#8217;s APL79 paper <a href=\"http:\/\/www.sudleyplace.com\/APL\/boolean.pdf\" target=\"_blank\"><em>A Programming Technique for Non-Rectangular Data<\/em><\/a>.<\/p>\n<pre><code class=\" language-apl\">   p\u21901 0 0 1 1 0 0 0 0 0\r\n   v\u21903 1 4 1 5 9 2 6 53 58\r\n\r\n   p\u2282v\r\n\u250c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2510\r\n\u25023 1 4\u25021\u25025 9 2 6 53 58\u2502\r\n\u2514\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2518\r\n\r\n   +\/\u00a8 p\u2282v\r\n8 1 133\r\n   t-\u00af1\u21930,t\u2190(1\u233dp)\/+\\v\r\n8 1 133\r\n\r\n   \u220a +\\\u00a8 p\u2282v\r\n3 4 8 1 5 14 16 22 75 133\r\n   s-(t-\u00af1\u21930,t\u2190(1\u233dp)\/\u2373\u2374p)\/\u00af1\u21930,(1\u233dp)\/s\u2190+\\v\r\n3 4 8 1 5 14 16 22 75 133\r\n<\/code><\/pre>\n<p>The last two sets of expressions illustrate how &#8220;partitioned plus reduce&#8221; and &#8220;partitioned plus scan&#8221; can be computed, without use of general arrays and without <em>each<\/em>.<\/p>\n<p>At issue is how to do &#8220;partitioned random permute&#8221;. Answer: <code class=\" language-apl\">\u234b(n?n)+n\u00d7+\\p \u22a3 n\u2190\u2262p<\/code>.<\/p>\n<pre><code class=\" language-apl\">p                1  0  0    1    1  0  0  0  0  0\r\nn?n              5  4 10    6    2  9  8  1  3  7\r\nn\u00d7+\\p           10 10 10   20   30 30 30 30 30 30\r\n(n?n)+n\u00d7+\\p     15 14 20   26   32 39 38 31 33 37\r\n\u234b(n?n)+n\u00d7+\\p     2  1  3    4    8  5  9 10  7  6<\/code><\/pre>\n<p>Therefore:<\/p>\n<pre><code class=\" language-apl\">ff\u2190{\r\n  b\u2190~(\u22a2 \u2228 1\u2218\u233d \u2228 \u00af1\u2218\u233d)' '=\u2375  \u235d internal letters\r\n  n\u2190\u2262p\u2190b\/b&gt;\u00af1\u233db             \u235d partition vector for groups of same\r\n  (b\/\u2375)[\u234b(n?n)+n\u00d7+\\p]@{b}\u2375\r\n}\r\n\r\n   cmpx 'ff x' 'fe x'\r\n  ff x \u2192 1.46E\u00af5 |    0% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\r\n* fe x \u2192 4.19E\u00af5 | +187% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\r\n\r\n   x6\u21901e6\u2374x\r\n\r\n   cmpx 'ff x6' 'fe x6'\r\n  ff x6 \u2192 5.16E\u00af2 |    0% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\r\n* fe x6 \u2192 1.77E\u00af1 | +243% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\r\n<\/code><\/pre>\n<p>There is a puzzle from 1980 which similarly involved randomly permuting items within groups. See <a href=\"http:\/\/www.jsoftware.com\/papers\/50\" target=\"_blank\"><em>A History of APL in 50 Functions<\/em><\/a>, Chapter 47, Pyramigram. The puzzle solution is amusing also for that fact that it used <code class=\" language-apl\">-\\<\/code>.<\/p>\n<h2>Afterword<\/h2>\n<p>Plobssiy, a txet wshoe words are ilivuddinaly ptemrued is rdeaable mnaliy bseacue in odirrany txet many wrods, eelpclsaiy iptnroamt wrods, are sorht. A curops wtih long and ufnmiailar wdors wuold lkiely be hard to raed atfer scuh pittarmoeun. For eapxmle:<\/p>\n<pre><code class=\" language-apl\">   ff t\r\n eyonelsmeary dpihnoeissopt siiuqpeedlasan pniormoasaac oopimoentaoa\r\n   ff t\r\n emlresaneyoy dnpepoihissot seilesiqaadupn poimrnaaasoc oaioomtpneoa\r\n   ff t\r\n erloymneseay dhsiepopiosnt seildspqiauean praisoaaonmc oomatneiopoa\r\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Friday Afternoon It&#8217;s something of a custom in Dyalog to send a &#8220;fun&#8221; e-mail to the group on Friday afternoons. My gambit for this past Friday was: x \u2190&#8217; according to research it doesn&#8221;t matter&#8217; x,\u2190&#8217; what order the letters &hellip; <a href=\"https:\/\/www.dyalog.com\/blog\/2018\/01\/permuting-internal-letters\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":13,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23,24],"tags":[],"class_list":["post-4047","post","type-post","status-publish","format-standard","hentry","category-musings","category-recreational"],"_links":{"self":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/4047","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/users\/13"}],"replies":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/comments?post=4047"}],"version-history":[{"count":7,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/4047\/revisions"}],"predecessor-version":[{"id":4991,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/4047\/revisions\/4991"}],"wp:attachment":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/media?parent=4047"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/categories?post=4047"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/tags?post=4047"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}