1 min read

APL Hacking: Project Euler (#24)

Problem #24:

⍝ Compute the 1,000,000th Lexicographic Permutation of
⍝ 0 through 9.
→(N≥3 2 1)/C3,C2,C1
R←1 0⍴0 ⋄ →0
C1:R←1 1⍴⎕IO ⋄ →0
C2:R←2 2⍴⎕IO+0 1 1 0 ⋄ →0
C3:R←6 3⍴⎕IO+0 1 2 0 2 1 1 0 2 1 2 0 2 0 1 2 1 0
A←+⍀(⍳I)⍪1,(I-1 1)⍴I↑-1

I hope that someone is impressed by this one. I am impressed. I didn't really come up with this technique. I did some searching around to try to understand how I might do permutations, and lo, and behold, this one came up on usenet on comp.lang.apl some years ago. What I find really clever about this is the iterative refinement of the permutations. If I understand how things are working right, the A matrix forms a sort of index into the arrangement, where each of the rows provides a sort of mapping to the next enlargement of the permutation set so that the old permutations can be reused in the new set with one additional selection being possible. I still don't think I can explain the whole thing perfectly, but I am getting a feel for how it does its work.