Tantangan

Mengingat jumlah item, ndalam daftar yang tidak kosong, diurutkan, akan menghasilkan indeks, i(n)di mana
" Permutasi Kembali-Ke-Depan "
akan berada dalam daftar semua permutasi jika permutasi tersebut diurutkan secara leksikografis.

Hasil mungkin berbasis 0 atau 1, cukup katakan yang mana (artinya i, tidak n).

Permutasi Kembali-Ke-Depan

... adalah hasil membangun daftar item dengan berulang kali mengambil bagian belakang (kanan) lalu depan (kiri) dari daftar yang disortir ke depan (kiri-ke-kanan) sampai semua item dipindahkan ke daftar baru, seperti :

Input being consumed     Output being built
----------------------+----------------------
[1,2,3,4,5,6,7]       |   []
[1,2,3,4,5,6]         |   [7]
  [2,3,4,5,6]         |   [7,1]
  [2,3,4,5]           |   [7,1,6]
    [3,4,5]           |   [7,1,6,2]
    [3,4]             |   [7,1,6,2,5]
      [4]             |   [7,1,6,2,5,3]
       []             |   [7,1,6,2,5,3,4]
----------------------+----------------------
                Result:   [7,1,6,2,5,3,4]

Indeks Permutasi

Jika nadalah 7(seperti di atas Kembali-Untuk-Front misalnya) ada 7! = 5040kemungkinan permutasi dari (berbeda) item.

Item pertama (atau nol jika Anda suka) dalam daftar yang diurutkan secara leksikografis dari semua permutasi itu adalah [1,2,3,4,5,6,7]dirinya sendiri.
Item kedua adalah [1,2,3,4,5,7,6].
Item kedua dari belakang akan menjadi [7,6,5,4,3,1,2].
Item terakhir adalah [7,6,5,4,3,2,1].

Di suatu tempat dalam daftar adalah [7,1,6,2,5,3,4]- permutasi Kembali-Ke-Depan.
Bahkan ia berada di indeks 4421 (atau berbasis 4420, 0).

100 syarat pertama dari rangkaian pernyataan (berbasis 1) i(n)dengan n=1adalah:

[1, 2, 5, 20, 101, 620, 4421, 35900, 326981, 3301820, 36614981, 442386620, 5784634181, 81393657020, 1226280710981, 19696509177020, 335990918918981, 6066382786809020, 115578717622022981, 2317323290554617020, 48773618881154822981, 1075227108896452857020, 24776789629988523782981, 595671612103250915577020, 14915538431227735068422981, 388375922695377900515577020, 10500493527722974260252422981, 294387851083990886241251577020, 8547374142655711068302364422981, 256705485669535347568006115577020, 7966133168508387470157556764422981, 255164703765185142697060455395577020, 8428152915046701352821133945884422981, 286804646124557439494797475697635577020, 10046343320261587490171853861825564422981, 361946983469639629977827594289009635577020, 13401806107756705416338151987291892764422981, 509620811358844406343669072112782398435577020, 19888261269838598952296612667790114958364422981, 796027021978059135393314656928325779313635577020, 32656499591185747972776747396512425885838364422981, 1372349618161694150570365858847999144050545635577020, 59042913445212141486784766209665998363213966364422981, 2599228661343236626556841044804949891956424561635577020, 117022992204136957935406320450852765172427309198364422981, 5385599167607951991914899108349402127789224443761635577020, 253237642343560228651049456045262577841408407945358364422981, 12160677950192512442211239591328112460680077946732401635577020, 596121186084075048430040923729967264426872753432477838364422981, 29817972015629302995182567242334801579950768815528034161635577020, 1521300781271752977229060449226968409483308951201458077838364422981, 79136874389672125594431576407176798565806196489681819746161635577020, 4195746409670353438703582176982222851124537591877131904925838364422981, 226647950929571027033389160506045358232154026979930809227362161635577020, 12469755402728704898931711687060471601348167024469505953048477838364422981, 698528832402134746955113935776664478135149811856698952734398562161635577020, 39828390672475082008725487969655657656845234984369903192450082717838364422981, 2310732940610403489820749422545419026172017083196773021228249831522161635577020, 136372385605079432248118270297843987319730859689490659519593045108637838364422981, 8184614727136310712028222912925520393434441746671755292929684651300962161635577020, 499395599150088488088828589263699706832570087241364247806476254829684637838364422981, 30970577661237849037564293765687064381179710710016867944356691992991422562161635577020, 1951637737743202215078582414596211073163593979517251760161922907619738331037838364422981, 124935294448140961888354806920565269729701922195027940438639971467594965899362161635577020, 8122715297634329704834815499864930982456556629150409552483483162921360809076637838364422981, 536222223779808734298894424747977821661836507759648464980376643706749720339339362161635577020, 35934888694408876553950964671857486605505798806289876128721251856561212716604532637838364422981, 2444100653742421723047039453897314094441893402549077796242989486161660232995578763362161635577020, 168678351774398889649421299427375524997828651490971291597405051437095619521145068660637838364422981, 11809893318195492906423362422261723211461109491055454565957957813190913963268700251019362161635577020, 838668695249666824614744281817664287077123498629740781320472805575397766414810317446260637838364422981, 60395789681636420036909326103457008453700968286067588202502542158402987220806878956757899362161635577020, 4409719671831047920854347812021594101623099731996837427616577550212019116846376438060145780637838364422981, 326378824480107593305098680409232188044060152088938133742995349285199216584125189021190726539362161635577020, 24482761986915290498641378436184801472882183734481184704052899163370643460988742220422624697460637838364422981, 1861011939679134964489290882424961756757512351644848150968435083798473400034549180897307347526539362161635577020, 143322080088606734669581493203883323226982866872563510695813139604263517949121870899167900513721460637838364422981, 11180959098117691096787939665528162905504766712615688479353149686064571807285078895345918312663622539362161635577020, 883437253980179837588356231874303489164303450066956218734514913541773418886216781638015892528346553460637838364422981, 70686019792283622457223177491312228676420353892298796358374930144685265836593932061030928974752467526539362161635577020, 5726440000955084363422511054086796876735936890839327162387490119571704913857298124195153605274993472953460637838364422981, 469637893700329090478715695935318149767077357177154001454773443957172289821041850488811978203204173646406539362161635577020, 38985601803506257421418755484185292421669426050466292273769584084412579273175587484390779961900566697260473460637838364422981, 3275254532761847009577968823645945995578996860191583194845076448298646552018541276645494943006816186458917446539362161635577020, 278435156905293180685369975402415213484477637470382623210256836304261379607777392174394791509334107831816205753460637838364422981, 23948660226767439201080153228038844501800392914958999127628507660415900870134672884615069843391985357739844389446539362161635577020, 2083808638152760278012520365471350750727983345146397213195344003554238214857458501196068353393022808146994627392953460637838364422981, 183398833619245678836784325280074933629492985604252949471226236983335323969170740817904072891411479020269638889458246539362161635577020, 16324556327289215402380134937173544376210173250892288905442294470849835710409338998582008497896189183708810744110298553460637838364422981, 1469391408154472281907142598683652193509359788033796478036774569234135557383656537547410122872987870461908423725867813446539362161635577020, 133730761359685823973259426160811489954077506688872881313704960027919535214176338228137873831877461557289259913042140378553460637838364422981, 12304683293281621431502064899712741587623914209186541475526534622910218175769343180214908250005163885795818227069614613285446539362161635577020, 1144467823788359953327703097406527694627129315367226993710615746590336588945697972034988381266839681418043178062317463477466553460637838364422981, 107592147841885948074037582159380073309559674264815645313786758687454863280472229658194120833316575777142822473140067877053221446539362161635577020, 10222386340397173314525664517235347022088186665852557223898463812546839124314230895213571254552107892786139414391086539473362138553460637838364422981, 981455548530552515895045737024658454136095461985415238220477591025945383684777269092475904782448641089288955324574667766166512421446539362161635577020, 95211304133951567337433380212539040258207718457187560919883999728307800228797098229713403270806624010171995234355103499880901319898553460637838364422981, 9331679144749296178288752362844703433551486045621764102574354777566399269794426700653262755936922495813433855354253356929531746247461446539362161635577020, 923930475294692230638703636199822301473608196598194450583355284174609600662504729388761377005628260366723545352917984225582320362921178553460637838364422981, 92402284968649460451060535220066878189242360067783427018009608611042990392567410879552702599150890025886974375474305774025602890553942821446539362161635577020

( i(0)=i(1)=1, tetapi tantangan itu sendiri hanya berkaitan dengan daftar yang tidak kosong)

Pada saat memposting urutan ini tidak muncul di OEIS .

Output hanya perlu bekerja dalam teori (jangan khawatir tentang kelebihan bilangan bulat, atau kehabisan sumber daya misalnya).

Ini adalah kode-golf , jadi jawaban tersingkat dalam byte menang.

Namun, jangan biarkan bahasa kode-golf menghalangi Anda - solusi yang baik juga harus mendapatkan upvotes!

Haskell , 32 byte

f 1=1
f n=product[1..n]+1-f(n-1)

Cobalah online!

Menggunakan hubungan f(n-1) + f(n) = n! + 1. Anggota yang berdekatan dari sekuens menambah faktorial ditambah satu:

1,   2,   5,   20,   101,   620,   4421, ...
  3     7    25    121    721   5041  ...
 2!+1  3!+1  4!+1  5!+1   6!+1  7!+1 

Jelly , 6 byte

R!ḅ-_Ḃ

Berbasis 0. Cobalah online!

Sangat terinspirasi oleh jawaban @ Neil ES6 .

Penjelasan

R!ḅ-_Ḃ
R       Create the range [1..N].
 !      Take the factorial of each.
  ḅ-    Convert from base -1; that is, sum, but alternate between adding and subtracting.
    _Ḃ  Subtract N%2.

Tapi bagaimana caranya?

Saya menjelaskan dalam jawaban ES6 saya teknik terkait untuk menghitung setiap angka. Rumusnya adalah ini:

(n-1)(n-1)! + (n-3)(n-3)! + (n-5)(n-5)! + ...

Kesadaran melanda saya ketika membaca jawaban ES6 @ Neil . Rumus ini dapat disederhanakan seperti:

(n-1)(n-1)!        + (n-3)(n-3)!            + (n-5)(n-5)!            + ...
(n(n-1!) - (n-1)!) + ((n-2)(n-3!) - (n-3)!) + ((n-4)(n-5)! - (n-5)!) + ...
(n!      - (n-1)!) + ((n-2)!      - (n-3)!) + ((n-4)!      - (n-5)!) + ...
n! - (n-1)! + (n-2)! - (n-3)! + (n-4)! - (n-5)! + ...

Kode Jelly R!ḅ-menghitung rumus ini. Namun, setiap nilai ganjil nakan memiliki nilai tambahan + 0!di akhir, yang kami urus dengan mengurangkannya n%2.

JavaScript (ES6), 38 byte

f=(n,x=n%2,y=1)=>n-x&&f(n,++x,y*=-x)+y

Diindeks 0. (Tidak ada penjelasan karena saya tidak benar-benar tahu mengapa itu berhasil, maaf.)

JavaScript (ES6), 44 byte

f=(x,n=0,g=1)=>x-n&&(x-n&1)*g*n+f(x,++n,g*n)

Berbasis 0. Ini mengambil keuntungan dari fakta bahwa angka-angka dapat direpresentasikan sebagai jumlah faktorial dalam pola berikut:

       1   2   6  24 120 720
   0:                       
   1:  1
   4:      2
  19:  1       3
 100:      2       4
 619:  1       3       5
4420:      2       4       6

Mengapa? Permutasi dapat direpresentasikan dengan baik di basis faktorial : mengeluarkan item ^ke- n dari daftar yang tersisa sesuai dengan digit n pada posisi itu. Kami berganti-ganti antara mengambil item terakhir (digit tertinggi) dan item pertama (nol); oleh karena itu, dalam basis faktorial, angka-angka ini dapat direpresentasikan sebagai:

0
10
200
3010
40200
503010
6040200

dan seterusnya.

MATL , 17 byte

:t"&0)P]vG:Y@!=Af

Output diindeks 1.

Cobalah online!

Penjelasan

Kode menerapkan definisi: membangun permutasi back-to-front, menghasilkan semua permutasi, membandingkan yang pertama dengan yang terakhir, dan menampilkan indeks yang cocok.

:        % Input n implicitly. Push [1 2 ... n]
t        % Duplicate
"        % For each: do the following n times
  &0)    %   Push the last element and then the rest of the array
  P      %   Reverse
]        % End
v        % Concatenate the whole stack vertically. This produces into a column vector
         % with the back-to-front permutation
G:       % Push [1 2 ... n] again
Y@!      % Permutations of [1 2 ... n]. Gives a matrix. Each column is a permutation
=        % Test for equality, element-wise with broadcast
A        % All: true for columns that have all entries equal to true. Gives a row vector
f        % Find: index of non-zero value. Implicitly display

Jelly , 9 byte

RU;¥/ỤUŒ¿

Cobalah online!

Huh, aku mencoba FGITW ini. Ternyata @Dennis diposting lebih dulu, tapi ini lebih pendek.

Penjelasan

RU;¥/ỤUŒ¿
R           List of numbers from 1 to {the input}
   ¥/       Left-fold the list by
 U;         prepending the reverse of the list to the next element
     Ụ      Invert permutation
      U     Reverse the list
       Œ¿   Find index of permutation

Memiliki Œ¿sebagai built-in cukup berguna di sini memungkinkan kita mengubah permutasi ke indeksnya, sehingga 7 byte lainnya bertanggung jawab untuk membangun permutasi back-to-front.

Cara kita melakukan ini adalah pertama-tama membangun permutasi yang berbeda, melalui pola berikut:

1
1 2
2 1 3
3 1 2 4
4 2 1 3 5
5 3 1 2 4 6
6 4 2 1 3 5 7

Setiap kali, kami membalikkan daftar yang kami miliki sejauh ini, lalu menambahkan bilangan bulat berikutnya. Itu tidak menghasilkan permutasi back-to-front, tetapi jelas terkait.

Permutasi yang kami coba dapatkan adalah 7 1 6 2 5 3 4. Bagaimana ini terkait? Nah, elemen di posisi 7 dari permutasi yang kita miliki adalah 7; elemen di posisi 1 adalah 6; elemen di posisi 6 adalah 5; elemen di posisi ke-2 adalah 4, dan seterusnya. Dengan kata lain, itu kebalikan dari permutasi yang kita miliki (dengan elemen dalam urutan terbalik). Dengan demikian, setelah dikurangi, kita dapat membalikkan permutasi dengan Ụdan membalikkan hasilnya dengan Uuntuk mendapatkan permutasi kembali-ke-depan yang kita inginkan.

Mungkin saja ada penghematan di sini, karena ditulis dengan tergesa-gesa dan terasa seperti setidaknya memiliki beberapa potensi untuk mengatur ulang hal-hal. Saya tidak yakin apakah mungkin untuk menyimpan seluruh byte.

Jelly , 10 8 byte

RṚżRFQŒ¿

Terima kasih kepada @ ais523 untuk bermain golf 2 byte dan percepatan luar biasa!

Cobalah online!

Bagaimana itu bekerja

RṚżRFQŒ¿  Main link. Argument: n

R         Range; yield [1, ..., n].
 Ṛ        Reverse; yield [n, ..., 1].
   R      Range; yield [1, ..., n] again.
  ż       Zip; yield [[n, 1], ..., [1, n]].
    F     Flatten.
     Q    Unique; deduplicate the results.
      Œ¿  Compute the permutation index of [n, 1, n-1, 2, ...].

PHP, 86 byte

for($i=$argv[1];$i>0;$i--)$o+=gmp_strval(gmp_fact($i))*($i%2==$argv[1]%2?1:-1);echo$o;

Menggunakan ekstensi GNU Multiple Precision .

Fungsi ini mengambil keuntungan dari fakta yang i(n)sama dengann! - (n-1)! + (n-2)! - (n-3)! etc

Kerusakan

for($i=$argv[1];$i>0;$i--) {        // Simple decreasing for loop (added { for readability)
    $o+=                            //  increment output with
        gmp_strval(gmp_fact($i))    //      $i!
    * ($i%2 == $argv[1]%2 ? 1 : -1) //      multiplied by -1 if ($i is odd when the input is even) or (if $i is even when the input is odd), else by 1
    ;
}
echo $o;                            // echoes output

Batch, 79 byte

@set/ax=%1%%2-1,y=z=1
@for /l %%i in (-%1,1,%x%)do @set/az+=y*=x-=1
@echo %z%

Diindeks 0.

Pyth, 12 byte

x.pQ<Q.i_UQU

Diindeks 0.

Penjelasan

x.pQ<Q.i_UQU
      .i       Interleave
        _UQUQ  Reversed range and range
    <Q         Take first n
x              Find the index
 .pQ           In the list of permutations