<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/le-monde-puzzle-1051/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://xianblog.wordpress.com/2018/05/18/le-monde-puzzle-1051/"> R – Xi'an's Og</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<blockquote>
<p><strong><a rel="nofollow" href="https://xianblog.files.wordpress.com/2018/03/sieglemond.jpg" target="_blank"><img data-orig-file="https://xianblog.files.wordpress.com/2018/03/sieglemond.jpg" data-orig-size="660,281" data-medium-file="https://xianblog.files.wordpress.com/2018/03/sieglemond.jpg?w=300" data-attachment-id="35577" data-image-meta="{" data-image-description="" src="https://xianblog.files.wordpress.com/2018/03/sieglemond.jpg?w=450&h=192&fit=450%2C192&resize=450%2C192" data-permalink="https://xianblog.wordpress.com/2018/03/12/le-monde-puzzle-1044/sieglemond/" data-large-file="https://xianblog.files.wordpress.com/2018/03/sieglemond.jpg?w=450&amp;h=192&amp;fit=450%2C192&amp;resize=450%2C192" alt="" data-image-title="sieglemond" sizes="(max-width: 450px) 100vw, 450px" width="450" data-comments-opened="1" class="wp-image-35577" data-recalc-dims="1" height="192"></a>A</strong> combinatoric <a rel="nofollow" href="https://xianblog.wordpress.com/2011/09/03/le-monde-puzzle-website/" title="Le Monde puzzle [website]" target="_blank">Le Monde mathematical puzzle</a> of limited size:<br>
<a rel="nofollow" href="https://xianblog.files.wordpress.com/2018/05/lemonde1051.png" target="_blank"><img data-orig-file="https://xianblog.files.wordpress.com/2018/05/lemonde1051.png" data-orig-size="834,126" data-medium-file="https://xianblog.files.wordpress.com/2018/05/lemonde1051.png?w=300" data-attachment-id="36115" data-image-meta="{" data-image-description="" src="https://xianblog.files.wordpress.com/2018/05/lemonde1051.png?w=450&h=68&fit=450%2C68&resize=450%2C68" data-permalink="https://xianblog.wordpress.com/2018/05/18/le-monde-puzzle-1051/lemonde1051/" data-large-file="https://xianblog.files.wordpress.com/2018/05/lemonde1051.png?w=450&amp;h=68&amp;fit=450%2C68&amp;resize=450%2C68" alt="" data-image-title="lemonde1051" sizes="(max-width: 450px) 100vw, 450px" width="450" data-comments-opened="1" class="wp-image-36115" data-recalc-dims="1" height="68"></a><em>When the only allowed move is to switch two balls from adjacent boxes, what is the minimal number of moves to return all balls in the above picture to their respective boxes? Same question with six boxes and 12 balls.</em></p>
</blockquote>
<p><strong>T</strong>he question is rather interesting to code as I decided to use recursion (as usual!) but wanted to gain time by storing the number of steps needed by any configuration to reach its ordered recombination. Meaning I had to update an external vector within the recursive function for each new configuration I met. With help from Julien Stoehr, who presented me with the following code, a simplification of a common<a rel="nofollow" href="https://stat.ethz.ch/pipermail/r-help/2005-April/070629.html" target="_blank"> R function</a></p>
<pre>v.assign &lt;- function (i,value,...) {
  temp &lt;- get(i, pos = 1)
  temp[...] &lt;- value
  assign(i, temp, pos = 1)}
</pre>
<p>which assigns one or several entries to the external vector i. I thus used this trick in the following R code, where cosz is a vector of size 5¹⁰, much larger than the <a rel="nofollow" href="https://stackoverflow.com/q/14212030/1154578" target="_blank">less than 10! values</a> I need <a rel="nofollow" href="https://math.stackexchange.com/q/328071/14893" target="_blank">but easier to code</a>. While n≤5.</p>
<pre>n=5;tn=2*n
baz=n^(0:(tn-1))
cosz=rep(-1,n^tn)
swee &lt;- function(balz){
  indz &lt;- sum((balz-1)*baz)
  if (cosz[indz]==-1){ 
  if (min(diff(balz))==0){ #ordered
     v.assign(&quot;cosz&quot;,indz,value=1)}else{
       val &lt;- n^tn
       for (i in 2:n)
       for (j in (2*i-1):(2*i))
       for (k in (2*i-3):(2*i-2)){
         calz &lt;- balz
         calz[k] &lt;- balz[j];calz[j] &lt;- balz[k]
         if (max(balz[k]-calz[k],calz[j]-balz[j])>0) 
           val &lt;- min(val,1+swee(calz))}
     v.assign(&quot;cosz&quot;,indz,value=val)
  }}
 return(cosz[indz])}
</pre>
<p>which returns 2 for n=2, 6 for n=3, 11 for n=4, 15 for n=5. In the case n=6, I need a much better coding of the permutations of interest. Which is akin to ranking all words within a dictionary with letters (1,1,…,6,6). After some thinking (!) and <a rel="nofollow" href="https://stackoverflow.com/a/14374455/1154578" target="_blank">searching</a>, I came up with a new version, defining</p>
<pre>parclass=rep(2,n)
rankum=function(confg){
    n=length(confg);permdex=1
    for (i in 1:(n-1)){
      x=confg[i]
      if (x>1){
        for (j in 1:(x-1)){
            if(parclass[j]>0){
                parclass[j]=parclass[j]-1
                permdex=permdex+ritpermz(n-i,parclass)
                parclass[j]=parclass[j]+1}}}
        parclass[x]=parclass[x]-1}
    return(permdex)}

ritpermz=function(n,parclass){
    return(factorial(n)/prod(factorial(parclass)))}
</pre>
<p>for finding the index of a given permutation, between 1 and (2n)!/2!..2!, and then calling the initial swee(p) with this modified allocation. The R code is still running…</p>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="https://xianblog.wordpress.com/2018/05/18/le-monde-puzzle-1051/"> R – Xi'an's Og</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/AG-pTtXmIt4" height="1"></a></div>