Indeks Permutasi Spiral Diratakan

8

Konteks

Pertimbangkan matriks persegi dengan nkolom dan baris yang berisi bilangan bulat positif pertama n^2(yaitu nkuadrat), di mana nganjil. Elemen-elemen dari matriks disusun sedemikian rupa sehingga bilangan bulat 1melalui n^2ditempatkan secara berurutan dalam spiral berlawanan arah jarum jam mulai di tengah dan awalnya bergerak ke kiri. Sebut matriks iniM(n)

Untuk n=1ini cukup berikan satu elemen matriks M(1)=[[1]].

M(3) adalah matriks

9 8 7
2 1 6
3 4 5

M(5) adalah matriks

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

dan M(7)merupakan matriks

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

Sekarang pertimbangkan untuk meratakan matriks ini ke dalam daftar / larik dengan menggabungkan barisnya mulai dari atas dan bergerak ke bawah. Panggil daftar ini L(n). L(3), L(5)dan L(7)diwakili di bawah ini, dengan elemen-elemennya dibatasi oleh spasi.

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)

Kita dapat menemukan indeks i(n)dari L(n)dalam daftar leksikografi diurutkan permutasi dari L(n). Dalam Jelly, Œ¿atom memberikan indeks ini untuk daftar kerjanya.

Tantangan

Tantangan Anda adalah mengambil bilangan bulat ganjil positif nsebagai input dan output indeks i(n).

Beberapa nilai pertama adalah

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

Perhatikan bahwa i(n)~ = (n^2)!. Ini bukan pada OEIS.

Ini adalah kode golf per bahasa, jadi capai ini dalam byte sesedikit mungkin.

Posting kotak pasir .

dylnan
sumber

Jawaban:

3

Jelly , 21 19 byte

-;,N$ṁx"RFḣNṙ-+\ỤŒ¿

Cobalah online!

Berdasarkan metode dari artikel J tentang volute .

Penjelasan

-;,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.
mil
sumber
2

J, 48 38 Bytes

-10 byte terima kasih kepada @miles!

[:A.@/:_1+/\@|.(2#1+i.)#&}:+:$_1,],1,-

Tua:

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

Perhatikan bahwa hasilnya 0-diindeks, jadi i(1) = 0dani(5) = 15511208759089364438087640

Penjelasan (lama):

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
       (                    )@                   | Monadic Hook:
             (          )@{.                     | To the first row, apply...
                      {:                         | The last and largest item
                     +                           | Added to...
              >:@i.@#                            | The list 1, 2, ..., n; where n is the row length
          |.@                                    | Reverse
        ,~                                       | Append to the top of the array
      ,                                          | Ravel
    A.                                           | Permutation index

Membuat spiral bisa lebih cepat, tetapi orientasinya akan kacau.

Saya tidak tahu bagaimana J mengoptimalkan ini, tetapi hanya perlu beberapa 0.000414detik untuk menghitung n=7(pada sesi konsol J baru).

Bolce Bussiere
sumber
Mungkin J melakukan sesuatu yang mirip dengan bagaimana saya membuat Jelly melakukannya ( kode )?
Jonathan Allan
Saya mengubah metode Anda menjadi 39 byte [:A.@,,.@*0&((,~(#\.+{:)@{.)@|:|.)~2*<:. Saya juga bermain golf versi metode dalam artikel volute hingga 38 byte [:A.@/:_1+/\@|.(2#1+i.)#&}:+:$_1,],1,-.
mil
1

MATL , 16 15 14 byte

lYL!PletY@wXmf

Gagal untuk kasus uji yang lebih besar daripada 3karena ketidaktepatan titik-mengambang dan keterbatasan memori.

Cobalah online!

Penjelasan

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
Luis Mendo
sumber
Apakah MATL memiliki built-in untuk spiral?
Erik the Outgolfer
@EriktheOutgolfer Mungkin punya satu
Luis Mendo
Penjelasan ditambahkan
Luis Mendo