## APL Hacking: Project Euler (#24)

Problem #24:

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.

∇R←PETWENTYFOUR;N;A;I ⍝ Compute the 1,000,000th Lexicographic Permutation of ⍝ 0 through 9. N←10 →(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 I←3 LP:→(N<I←I+1)/XT A←+⍀(⍳I)⍪1,(I-1 1)⍴I↑-1 R←A[;⎕IO,1+R] →LP XT:R←(((!N),N)⍴R)[1000000;]-⎕IO ∇

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.