# Flattened Spiral Permutation Index

## Context

Consider square matrices with n columns and rows containing the first n^2 (i.e. n squared) positive integers, where n is odd. The elements of the matrices are arranged such that the integers 1 through n^2 are placed sequentially in a counterclockwise spiral starting at the center and initially moving to the left. Call these matrices M(n)

For n=1 this simply gives the one element matrix M(1)=[[1]].

M(3) is the matrix

9 8 7
2 1 6
3 4 5


M(5) is the matrix

25 24 23 22 21
10  9  8  7 20
11  2  1  6 19
12  3  4  5 18
13 14 15 16 17


and M(7) is the matrix

49 48 47 46 45 44 43
26 25 24 23 22 21 42
27 10  9  8  7 20 41
28 11  2  1  6 19 40
29 12  3  4  5 18 39
30 13 14 15 16 17 38
31 32 33 34 35 36 37


Now consider flattening this matrix into a list/array by concatenating its rows starting from the top and moving down. Call these lists L(n). L(3), L(5) and L(7) are represented below, with their elements delimited by spaces.

9 8 7 2 1 6 3 4 5     (n=3)
25 24 23 22 21 10 9 8 7 20 11 2 1 6 19 12 3 4 5 18 13 14 15 16 17    (n=5)
49 48 47 46 45 44 43 26 25 24 23 22 21 42 27 10 9 8 7 20 41 28 11 2 1 6 19 40 29 12 3 4 5 18 39 30 13 14 15 16 17 38 31 32 33 34 35 36 37    (n=7)


We can find the index i(n) of L(n) in a lexicographically sorted list of permutations of L(n). In Jelly, the Œ¿ atom gives this index for the list it acts on.

## Challenge

Your challenge is to take an positive odd integer n as input and output the index i(n).

The first few values are

n  i(n)
-------
1  1
3  362299
5  15511208759089364438087641
7  608281864033718930841258106553056047013696596030153750700912081


Note that i(n) ~= (n^2)!. This is not on OEIS.

This is code golf per language, so achieve this in the fewest bytes possible.

# Jelly, 21 19 bytes

-;,N$ṁx"RFḣNṙ-+\ỤŒ¿  Try it online! Based on the method from a J article on volutes. ## Explanation -;,N$ṁx"RFḣNṙ-+\ỤŒ¿  Main link. Input: integer n
-;                   Prepend -1. [-1, n]
,N$Pair with its negated value. [[-1, n], [1, -n]] ṁ Mold it to length n. R Range. [1, 2, ..., n] x" Vectorized copy each value that many times. F Flatten N Negate n ḣ Head. Select all but the last n values. ṙ- Rotate left by -1 (right by 1). +\ Cumulative sum. Ụ Grade up. Œ¿ Permutation index.  # J, 48 38 Bytes -10 bytes thanks to @miles ! [:A.@/:_1+/\@|.(2#1+i.)#&}:+:$_1,],1,-


Old:

3 :'A.,(,~|.@(>:@i.@#+{:)@{.)@|:@|.^:(+:<:y),.1'


Note that the result is 0-indexed, so i(1) = 0 and i(5) = 15511208759089364438087640

### Explanation (old):

3 :'                                           ' | Explicit verb definition
,.1  | Make 1 into a 2d array
(+:<:y)     | 4*n, where y = 2*n + 1
^:            | Repeat 4*n times
|:@|.              | Clockwise rotation
(          )@{.                     | To the first row, apply...
{:                         | The last and largest item
>:@i.@#                            | The list 1, 2, ..., n; where n is the row length
|.@                                    | Reverse
,~                                       | Append to the top of the array
,                                          | Ravel
A.                                           | Permutation index


Making the spiral could be quicker, but the orientation would get messed up.

I don't know how J is optimizing this, but it only takes 0.000414 seconds to calculate for n=7 (on a fresh J console session).

• Maybe J does something similar to how I made Jelly do it (code)? – Jonathan Allan Feb 9 '18 at 20:25
• I golfed your method to 39 bytes [:A.@,,.@*0&((,~(#\.+{:)@{.)@|:|.)~2*<:. I also golfed a version of the method in the volute article to 38 bytes [:A.@/:_1+/\@|.(2#1+i.)#&}:+:$_1,],1,-. – miles Feb 10 '18 at 14:11 # Jelly, 27 bytes ZUðẎṀ+ṚW;⁸µJ 1WÇẎ⁸²¤ḟ$\$¿ẎŒ¿


Try it online!

# MATL, 1615 14 bytes

lYL!PletY@wXmf


Fails for test cases larger than 3 due to both floating-point inaccuracies and memory limitations.

Try it online!

### Explanation

lYL    % Implicit input n. Spiral matrix of that side length
!P     % Transpose, flip vertically. This is needed to match the orientation
% of columns in the spiral with that of rows in the challenge text
le     % Convert to a row, reading in column-major order (down, then across)
t      % Duplicate
Y@     % All permutations, arranged as rows of a matrix, in lexicographical
% order
w      % Swap
Xm     % Row membership: gives a column vector containing true / false,
% where true indicates that the corresponding row in the first input
% matches a row from the second output. In this case the second input
% consists of a single row
f      % Find: gives indices of nonzeros. Implicit display

• Does MATL have built-ins for spirals? – Erik the Outgolfer Feb 8 '18 at 21:55
• @EriktheOutgolfer It may have one – Luis Mendo Feb 8 '18 at 22:19
• Explanation added – Luis Mendo Feb 8 '18 at 22:25