Catatan: Ini adalah upaya mendaur ulang pertanyaan permutasi guest271314

Ada pola menarik yang terbentuk ketika Anda menemukan perbedaan antara permutasi yang diurutkan secara leksografis dari angka-angka dasar 10 dengan angka unik yang naik. Misalnya, 123memiliki permutasi:

123 132 213 231 312 321

Ketika Anda menemukan perbedaan di antara ini, Anda mendapatkan urutannya

9 81 18 81 9

Yang semuanya habis dibagi sembilan (karena jumlah digit dari basis 10 angka), serta menjadi palindromic.

Khususnya, jika kita menggunakan nomor berikutnya 1234,, kita mendapatkan urutannya

9 81 18 81 9 702 9 171 27 72 18 693 18 72 27 171 9 702 9 81 18 81 9

Yang memperpanjang urutan sebelumnya sambil tetap palindrom di sekitar $693$ . Pola ini selalu berlaku, bahkan ketika Anda mulai menggunakan lebih banyak 10angka itu, meskipun panjang urutannya adalah $n!-1$ untuk $n$ angka. Perhatikan bahwa untuk menggunakan angka di atas 0 to 9, kami tidak mengubah ke basis yang berbeda, kami hanya mengalikan angka dengan $10^x$ , misalnya $[1,12,11]_{10} = 1*10^2 + 12*10^1 + 11*10^0 = 231$ .

Tujuan Anda adalah menerapkan urutan ini, dengan mengembalikan setiap elemen sebagai kelipatan dari sembilan. Misalnya, 23 elemen pertama dari urutan ini adalah:

1 9 2 9 1 78 1 19 3 8 2 77 2 8 3 19 1 78 1 9 2 9 1

Beberapa test case lainnya (0 diindeks):

23     => 657
119    => 5336
719    => 41015
5039   => 286694
40319  => 1632373
362879 => 3978052
100    => 1
1000   => 4
10000  => 3
100000 => 3

Aturan:

• Pengajuan dapat berupa:
  • Program / fungsi yang mengambil angka dan mengembalikan angka pada indeks itu, baik 0 atau 1 diindeks.
  • Program / fungsi yang mengambil angka $n$ dan mengembalikan ke indeks ke- $n$ , baik yang diindeks 0 atau 1.
  • Program / fungsi yang menampilkan / mengembalikan urutan tanpa batas.
• Program harus mampu menangani secara teoritis hingga $11!-1$ Elemen ke- 1 dan seterusnya, meskipun saya mengerti jika batasan waktu / memori membuat ini gagal. Secara khusus, ini berarti Anda tidak dapat menggabungkan angka dan mengevaluasi sebagai basis 10, karena sesuatu seperti $012345678910$ akan salah.
• Ini adalah kode-golf , jadi implementasi tersingkat untuk setiap bahasa menang!

Catatan:

• Ini adalah OEIS A217626
• Saya menawarkan hadiah 500 untuk solusi yang menghitung elemen secara langsung tanpa menghitung permutasi yang sebenarnya.
• Urutan ini berfungsi untuk setiap digit yang berdekatan. Sebagai contoh, perbedaan antara permutasi $[1,2,3,4]_{10}$ sama dengan untuk $[-4,-3,-2,-1]_{10}$ .

Jelly , 9 byte

,‘œ?ŻḌI÷9

Cobalah online! (cetak elemen ke-n)

Cobalah online! (20 elemen pertama)

Penjelasan:

      I÷9      Compute the difference divided by 9 between
 ‘             the (n+1)th
  œ?           permutation
,              and
               the (n)th
  œ?           permutation
    Ż          of [0,1,2,...n]
     Ḍ         converted to decimal.

(Jelly memiliki builtin œ?yang menghitung npermutasi daftar dalam waktu sekitar linier. Cukup berguna.)

Arang , 71 byte

≔⟦Ｎ⊕θ⟧ηＷ⌈η≧÷Ｌ⊞ＯυＥη﹪κ⊕Ｌυη≔⁰δＦ²«≔Ｅυλζ≔⟦⟧ηＦ⮌Ｅυ§κι«⊞η§ζκ≔Φζ⁻μκζ»≦⁻↨ηχδ»Ｉ÷δ⁹

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan:

≔⟦Ｎ⊕θ⟧η

Dapatkan daftar yang berisi input dan satu lagi dari input.

Ｗ⌈η

Ulangi sampai kedua nilai tersebut nol.

≧÷Ｌ⊞ＯυＥη﹪κ⊕Ｌυη

Lakukan konversi basis faktorial pada kedua nilai. Ini adalah pertama kalinya saya benar-benar menggunakan ≧daftar!

≔⁰δ

Kosongkan hasilnya.

Ｆ²«

Ulangi setiap nomor basis faktorial.

≔Ｅυλζ

Buat daftar digit dari 0 hingga panjang - 1.

≔⟦⟧η

Inisialisasi hasilnya ke daftar kosong.

Ｆ⮌Ｅυ§κι«

Lingkari angka-angka dari nomor basis faktorial.

⊞η§ζκ

Tambahkan digit permutasi berikutnya ke hasilnya.

≔Φζ⁻μκζ»

Hapus angka itu dari daftar.

≦⁻↨ηχδ»

Konversikan permutasi sebagai angka dasar 10 dan kurangi hasilnya sejauh itu.

Ｉ÷δ⁹

Bagi hasil akhir dengan 9 dan dilemparkan ke string.

Perl 6 , 82 byte

-2 byte terima kasih kepada Jo King

->\n{([-] map {$/=[^n];:10[map {|splice $/,$_,1},[R,] .polymod(1..n-2)]},n+1,n)/9}

Cobalah online!

Diindeks 0. Tidak menghitung semua permutasi. Secara teoritis harus bekerja untuk semua n, tetapi menebus untuk n> 65536 dengan "Terlalu banyak argumen dalam susunan rata".

Versi 80 byte berikut ini berfungsi untuk n hingga 98! -2 dan jauh lebih cepat:

{([-] map {$/=[^99];:10[map {|splice $/,$_,1},[R,] .polymod(1..97)]},$_+1,$_)/9}

Cobalah online!

Versi 53 byte berikut secara teoritis akan bekerja untuk semua n, tetapi menebus untuk n> = 20 dengan "menolak untuk permutasi lebih dari 20 elemen".

{[-](map {:10[$_]},permutations(1..$_+1)[$_,$_-1])/9}

Cobalah online!

JavaScript (Node.js) , 134 byte

n=>(F=_=>f>n?((G=(n,z=0,x=f,y=l,b=[...a])=>y?G(n%(x/=y),+b.splice(n/x,1)+z*10,x,y-1,b):z)(n--)-G(n))/9:F(a.push(++l),f*=l))(a=[l=f=1])

Cobalah online!

1-diindeks.

Pendapat @ guest271314 benar. Perhitungan permutasi langsung lebih pendek ...

Penjelasan

n=>(                           // Function -
 F=_=>                         //  Helper func to calculate length needed
 f>n?                          //   If f > n (meaning the length is enough) -
  (
   (
    G=(                        //    Helper func to calculate permutation value -
     n,
     z=0,                      //     Initial values
     x=f,                      //     Made as copies because we need to alter
     y=l,                      //     these values and the function will be
     b=[...a]                  //     called twice
    )=>
    y?                         //     If still elements remaining -
     G(
      n%(x/=y),                //      Get next element
      +b.splice(n/x,1)+z*10,   //      And add to the temporary result
      x,
      y-1,                     //      Reduce length
      b                        //      Remaining elements
     )
    :z                         //     Otherwise return the permutation value
   )(n--)-G(n)                 //    Calculate G(n) - G(n - 1)
  )/9                          //    ... the whole divided by 9 
 :F(
  a.push(++l),                 //   Otherwise l = l + 1, push l into the array
  f*=l                         //   ... and calculate l!
 )
)(
 a=[l=f=1]                     //  Initial values
)

Solusi asli (159 byte)

n=>(x=l=t=0n,P=(a,b=[])=>n?""+a?a.map(z=>P(a.filter(y=>y-z),[...b,z])):(v=b.reduce((u,y)=>u=u*10n+y),x?--n?0:t=v-x:0,x=v):0)([...Array(n+1))].map(_=>++l))&&t/9n

Cobalah online!

Tautan ke versi yang lebih panjang dibuat untuk kinerja. Array(n+1)menjadiArray(Math.min(n+1,15)) untuk membuat karya demo. Secara teoritis bekerja hingga tak terbatas (hingga batas stack dalam praktek).

Penjelasan

Maksud saya ada terlalu banyak untuk dijelaskan.

n=>(                             // Function
 x=l=t=0n,                       // Initialization
 P=(                             // Function to determine the permutation -
  a,                             //  remaining items
  b=[]                           //  storage
 )=>
 n?                              //  if we haven't reached the required permutation yet - 
  ""+a?                          //   if we haven't the last layer of loop - 
   a.map(                        //    loop over the entries -
    z=>      
    P(                           //     recurse -
     a.filter(y=>y-z),           //      pick out the selected number
     [...b,z]                    //      append to next 
    )
   )
  :(                             //   if we are at the last layer -
   v=b.reduce((u,y)=>u=u*10n+y), //    calculate the value of the permutation
   x?                            //    if not the first number -
    --n?                         //     if not the last -
     0                           //      do nothing
    :t=v-x                       //     else calculate difference
   :0,                           //    else do nothing
   x=v                           //    record ot anyway
  )
 :0                              //   else do nothing
)
(
 [...Array(n+1)].map(_=>++l)     // the list of numbers to permute
)&&t/9n                          // last difference divided by 9

Pyth, 15 14 byte

.+m/i.PdSQT9,h

Mengembalikan istilah ke-n. Coba di sini .

.+                     Find the differences between adjacent elements of
   m                   mapping lambda d:
      .PdSQ                the dth permutation of input,
     i     T               converted to base 10
    /       9              divided by 9
             ,         over [Q+1,Q]
               h Q
               Q

J , 44 , 41 byte

(9%~[:(2-~/\])i.(10#.1+A.)[:i.@>.!inv)@>:

Cobalah online!

Catatan: berfungsi bahkan untuk 10! test case, tetapi kehilangan beberapa presisi di sana ...

penjelasan asli

(9 %~ [: (2 -~&(10&#.)/\ ]) 1 + i. A. i.@>.@(!inv))@>:
(                                                 )@>: NB. add one to input
                                                       NB. since n-1 deltas
                                                       NB. gives n results
                                                       NB. call that "n"
(                               i.                )    NB. take the first n
(                                  A.             )    NB. lexicographically
                                                       NB. sorted items of
(                                     i.@         )    NB. 0 up to...
(                                        >.@      )    NB. the ceil of...
(                                           (!inv))    NB. the inverse of 
                                                       NB. the factorial
(                           1 +                   )    NB. add 1 so our
                                                       NB. lists start at 1
                                                       NB. instead of 0
(     [: (                )                       )    NB. apply what's in 
                                                       NB. parens to that
                                                       NB. list of lists
(        (2 -~        /\ ])                       )    NB. take successive
                                                       NB. differences BUT
(        (    &(10&#.)    )                       )    NB. convert each list
                                                       NB. to a base 10
                                                       NB. number first
(9 %~                                             )    NB. and divide every
                                                       NB. items of the
                                                       NB. result by 9

JavaScript (ES6), 112 byte

Sangat mirip dengan algoritma Shieru Asakoto .

n=>(g=N=>(h=a=>k>n?(F=r=>--i?F(+a.splice(N/(k/=i),1)+r*10,N%=k):r/9)``:h([i+1,...a],k*=i++))([i=k=1]))(n++)-g(n)

Cobalah online!