<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/lexicographic-permutations-euler-problem-24/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://r.prevos.net/euler-problem-24/"> The Devil is in the Data</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p>Euler Problem 24 asks to develop <a rel="nofollow" href="https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order" target="_blank">lexicographic permutations</a> which are ordered arrangements of objects in lexicographic order. Tushar Roy of <em>Coding Made Simple</em> has shared a great introduction on how to generate lexicographic permutations.</p>
<p><iframe allowfullscreen="true" src="https://www.youtube.com/embed/nYFd7VHKyWQ?version=3&rel=1&fs=1&autohide=2&showsearch=0&showinfo=1&iv_load_policy=1&wmode=transparent" width="450" type="text/html"></iframe></p>
<h2>Euler Problem 24 Definition</h2>
<p>A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:</p>
<p>012 021 102 120 201 210</p>
<p>What is the <a rel="nofollow" href="https://projecteuler.net/problem=24" target="_blank">millionth lexicographic permutation</a> of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?</p>
<h2>Brute Force Solution</h2>
<p>The digits 0 to 9 have <img alt="10! = 3628800" title="10! = 3628800" src="http://s0.wp.com/latex.php?latex=10%21+%3D%C2%A03628800&bg=ffffff&fg=000&s=0" class="latex"> permutations (including combinations that start with 0). Most of these permutations are, however, not in lexicographic order. A brute-force way to solve the problem is to determine the next lexicographic permutation of a number string and repeat this one million times.</p>
<pre>
nextPerm &lt;- function(a) {
    # Find longest non-increasing suffix
    i &lt;- length(a) while (i > 1 &amp;&amp; a[i - 1] >= a[i])
        i &lt;- i - 1
    # i is the head index of the suffix
    # Are we at the last permutation?
    if (i &lt;= 1) return (NA)
    # a[i - 1] is the pivot
    # Find rightmost element that exceeds the pivot
    j &lt;- length(a)
    while (a[j] &lt;= a[i - 1]) 
        j &lt;- j - 1
    # Swap pivot with j
    temp &lt;- a[i - 1]
    a[i - 1] &lt;- a[j]
    a[j] &lt;- temp
    # Reverse the suffix
    a[i:length(a)] &lt;- rev(a[i:length(a)])
    return(a)
    }

numbers &lt;- 0:9
for (i in 1:(1E6 - 1)) numbers &lt;- nextPerm(numbers)
answer &lt;- numbers
print(answer)
</pre>
<p>This code takes the following <a rel="nofollow" href="https://www.nayuki.io/page/next-lexicographical-permutation-algorithm" target="_blank">steps</a>:</p>
<ol>
<li>Find largest index <img alt="i" title="i" src="http://s0.wp.com/latex.php?latex=i&bg=ffffff&fg=000&s=0" class="latex"> such that <img alt="a_{i-1} &lt; a_i" title="a_{i-1} &lt; a_i" src="http://s0.wp.com/latex.php?latex=a_%7Bi-1%7D+%3C+a_i&bg=ffffff&fg=000&s=0" class="latex">.
<ol>
<li>If no such index exists, then this is already the last permutation.</li>
</ol>
</li>
<li>Find largest index <img alt="j" title="j" src="http://s0.wp.com/latex.php?latex=j&bg=ffffff&fg=000&s=0" class="latex"> such that <img alt="j geq i" title="j geq i" src="http://s0.wp.com/latex.php?latex=j+%5Cgeq+i&bg=ffffff&fg=000&s=0" class="latex"> and <img alt="a_j &gt; a_{i-1}" title="a_j &gt; a_{i-1}" src="http://s0.wp.com/latex.php?latex=a_j+%3E+a_%7Bi-1%7D&bg=ffffff&fg=000&s=0" class="latex">.</li>
<li>Swap <img alt="a_j" title="a_j" src="http://s0.wp.com/latex.php?latex=a_j&bg=ffffff&fg=000&s=0" class="latex"> and <img alt="a_{i-1}" title="a_{i-1}" src="http://s0.wp.com/latex.php?latex=a_%7Bi-1%7D&bg=ffffff&fg=000&s=0" class="latex">.</li>
<li>Reverse the suffix starting at <img alt="a_i" title="a_i" src="http://s0.wp.com/latex.php?latex=a_i&bg=ffffff&fg=000&s=0" class="latex">.</li>
</ol>
<h2>Combinatorics</h2>
<p>A more efficient solution is to use combinatorics, thanks to <a rel="nofollow" href="http://www.mathblog.dk/project-euler-24-millionth-lexicographic-permutation/" target="_blank">MathBlog</a>. The last nine digits can be ordered in <img alt="9! = 362880" title="9! = 362880" src="http://s0.wp.com/latex.php?latex=9%21+%3D+362880&bg=ffffff&fg=000&s=0" class="latex"> ways. So the first <img alt="9!" title="9!" src="http://s0.wp.com/latex.php?latex=9%21&bg=ffffff&fg=000&s=0" class="latex"> permutations start with a 0. By extending this thought, it follows that the millionth permutation must start with a 2.</p>
<p><img alt="lfloor (1000000 - 1) / 9! rfloor  = 2" title="lfloor (1000000 - 1) / 9! rfloor  = 2" src="http://s0.wp.com/latex.php?latex=%5Clfloor+%281000000+-+1%29+%2F+9%21+%5Crfloor+%C2%A0%3D+2&bg=ffffff&fg=000&s=0" class="latex"></p>
<p>From this rule, it follows that the 725761<sup>st</sup> permutation is 2013456789. We now need 274239 more lexicographic permutations:</p>
<p><img alt="(1000000 - 1) - (2 times 9!) = 274239" title="(1000000 - 1) - (2 times 9!) = 274239" src="http://s0.wp.com/latex.php?latex=%281000000+-+1%29+-+%282+%5Ctimes+9%21%29+%3D+274239&bg=ffffff&fg=000&s=0" class="latex"></p>
<p>We can repeat this logic to find the next digit. The last 8 digits can be ordered in 40320 ways. The second digit is the 6th digit in the remaining numbers, which is 7 (2013456789).</p>
<p><img alt="lfloor 274239 / 8! rfloor  = 6" title="lfloor 274239 / 8! rfloor  = 6" src="http://s0.wp.com/latex.php?latex=%5Clfloor+274239+%2F+8%21+%5Crfloor+%C2%A0%3D+6&bg=ffffff&fg=000&s=0" class="latex"></p>
<p><img alt="274239 - (6 times 7!) = 32319" title="274239 - (6 times 7!) = 32319" src="http://s0.wp.com/latex.php?latex=274239+-+%286+%5Ctimes+7%21%29+%3D+32319&bg=ffffff&fg=000&s=0" class="latex"></p>
<p>This process is repeated until all digits have been used.</p>
<pre>
numbers &lt;- 0:9
n &lt;- length(numbers)
answer &lt;- vector(length = 10)
remain &lt;- 1E6 - 1
for (i in 1:n) {
    j &lt;- floor(remain / factorial(n - i))
    answer[i] &lt;- numbers[j + 1]
    remain &lt;- remain %% factorial(n - i)
    numbers &lt;- numbers[-(j + 1)]
}
answer &lt;- paste(answer, collapse = &quot;&quot;)
print(answer)
</pre>
<p>R blogger <a rel="nofollow" href="https://www.r-bloggers.com/project-euler-problem-24/" target="_blank">Tony’s Bubble Universe</a> created a generalised function to solve this problem a few years ago.</p>
<p>The post <a rel="nofollow" href="http://r.prevos.net/euler-problem-24/" target="_blank">Lexicographic Permutations: Euler Problem 24</a> appeared first on <a rel="nofollow" href="http://r.prevos.net/" target="_blank">The Devil is in the Data</a>.</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="http://r.prevos.net/euler-problem-24/"> The Devil is in the Data</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 width="1" alt="" src="http://feeds.feedburner.com/~r/RBloggers/~4/vI_lrzt_Cks" height="1"></a></div>