Wyzwanie

Biorąc pod uwagę liczbę elementów, nna niepustej, posortowanej liście wyprowadza indeks, i(n)w którym jego
„ Permutacja od tyłu do przodu ”
znajdowałaby się na liście wszystkich permutacji, gdyby wymienione permutacje zostały posortowane leksykograficznie.

Wyniki mogą być oparte na 0 lub 1, wystarczy powiedzieć, które (to znaczy inie n).

Permutacja od tyłu do przodu

... jest wynikiem budowania listy elementów poprzez wielokrotne przechodzenie do tyłu (w prawo), a następnie do przodu (w lewo) listy posortowanej do przodu (od lewej do prawej), aż wszystkie elementy zostaną przeniesione na nową listę, podobnie :

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 permutacji

Jeśli njest 7(jak w powyższym przykładzie Back-To-Front), 7! = 5040możliwe są permutacje (odrębnych) elementów.

Pierwszy (lub zerowy, jeśli wolisz) element na posortowanej leksykograficznie liście wszystkich tych permutacji byłby [1,2,3,4,5,6,7]sam.
Drugi przedmiot to [1,2,3,4,5,7,6].
Przedostatni przedmiot byłby [7,6,5,4,3,1,2].
Ostatnim przedmiotem byłby [7,6,5,4,3,2,1].

Gdzieś na liście jest [7,1,6,2,5,3,4]- permutacja Back-To-Front.
W rzeczywistości znajduje się w indeksie 4421 (lub 4420, w oparciu o 0).

Pierwsze 100 terminów (1) serii i(n)stwierdzeń z n=1:

[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)=1ale samo wyzwanie dotyczy tylko niepustych list)

W momencie publikacji ta sekwencja nie pojawiła się w OEIS .

Dane wyjściowe muszą działać tylko teoretycznie (nie przejmuj się na przykład przepełnieniem liczb całkowitych lub wyczerpaniem zasobów).

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.

Nie pozwól jednak, aby języki kod-golfowe Cię zniechęciły - dobre rozwiązania również powinny zyskać aprobatę!

Haskell , 32 bajty

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

Wypróbuj online!

Wykorzystuje relację f(n-1) + f(n) = n! + 1. Sąsiadujący członkowie sekwencji dodają do silni plus jeden:

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 

Galaretka , 6 bajtów

R!ḅ-_Ḃ

W oparciu o 0. Wypróbuj online!

Mocno zainspirowany odpowiedzią ES6 @ Neila .

Wyjaśnienie

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.

Ale jak?

W mojej odpowiedzi na ES6 wyjaśniam pokrewną technikę obliczania każdej liczby. Wzór jest następujący:

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

Uświadomiłem sobie, czytając odpowiedź ES6 @ Neila . Ta formuła może zostać uproszczona w następujący sposób:

(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)! + ...

Kod Jelly R!ḅ-oblicza tę formułę. Jednak każda nieparzysta wartość nbędzie miała + 0!na końcu dodatkową , o którą dbamy, odejmując n%2.

JavaScript (ES6), 38 bajtów

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

0-indeksowane. (Brak wyjaśnienia, bo tak naprawdę nie wiem, dlaczego to działa, przepraszam.)

JavaScript (ES6), 44 bajty

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

W oparciu o 0. Wykorzystuje to fakt, że liczby mogą być reprezentowane jako sumy silni według następującego wzoru:

       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

Dlaczego? Permutacje można ładnie przedstawić w podstawie silni : usunięcie n- ^tej pozycji z pozostałej listy odpowiada cyfrze nw tej pozycji. Na przemian wybieramy ostatni przedmiot (najwyższa cyfra) i pierwszy przedmiot (zero); dlatego w podstawie silni liczby te można przedstawić jako:

0
10
200
3010
40200
503010
6040200

i tak dalej.

MATL , 17 bajtów

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

Dane wyjściowe są indeksowane 1.

Wypróbuj online!

Wyjaśnienie

Kod stosuje definicję: buduje permutację typu back-to-front, generuje wszystkie permutacje, porównuje pierwszą z wszystkimi ostatnimi i generuje indeks dopasowania.

:        % 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

Galaretka , 9 bajtów

RU;¥/ỤUŒ¿

Wypróbuj online!

Huh, próbowałem to FGITW. Okazuje się, że @Dennis wysłał pierwszy, ale to jest krótsze.

Wyjaśnienie

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

Posiadanie Œ¿wbudowanego jest tutaj dość przydatne, pozwalając nam przekonwertować permutację na jego indeks, więc pozostałe 7 bajtów jest odpowiedzialnych za tworzenie permutacji typu back-to-front.

Sposób, w jaki to robimy, polega na skonstruowaniu innej permutacji według następującego wzoru:

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

Za każdym razem cofamy listę, którą mamy do tej pory, a następnie dodajemy kolejną liczbę całkowitą. To nie powoduje permutacji od tyłu do przodu, ale jest wyraźnie powiązane.

Permutacja, którą próbujemy uzyskać, jest 7 1 6 2 5 3 4. Jak to się wiąże? Cóż, element na 7. pozycji permutacji, którą mamy, to 7; element na 1. pozycji to 6; element na 6. pozycji to 5; element na 2. pozycji to 4 i tak dalej. Innymi słowy, jest to odwrotność permutacji, którą mamy (z elementami w odwrotnej kolejności). Jako taki, po zmniejszeniu możemy odwrócić permutację za pomocą Ụi odwrócić wynik za pomocą, Uaby uzyskać pożądaną permutację od przodu do przodu.

Możliwe, że są tu oszczędności, ponieważ zostało napisane w pośpiechu i wydaje się, że ma co najmniej pewien potencjał do zmiany układu. Nie jestem jednak pewien, czy można zapisać cały bajt.

Galaretka , 10 8 bajtów

RṚżRFQŒ¿

Dzięki @ ais523 za grę w golfa przy 2 bajtach i ogromne przyspieszenie!

Wypróbuj online!

Jak to działa

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 bajtów

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

Wykorzystuje GNU Multiple Precision .

Ta funkcja korzysta z faktu, że i(n)jest równan! - (n-1)! + (n-2)! - (n-3)! etc

Awaria

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

Partia, 79 bajtów

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

0-indeksowane.

Pyth, 12 bajtów

x.pQ<Q.i_UQU

0-indeksowane.

Wyjaśnienie

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