Die Herausforderung

Angesichts der Anzahl der Elemente wird nin einer nicht leeren, sortierten Liste der Index ausgegeben i(n), bei dem sich die
" Back-To-Front-Permutation "
in einer Liste aller Permutationen befinden würde, wenn die Permutationen lexikographisch sortiert wären.

Die Ergebnisse können auf 0 oder 1 basieren, sagen Sie einfach welche (das heißt inicht n).

Die Back-To-Front-Permutation

... ist das Ergebnis des Erstellens einer Liste von Elementen, indem wiederholt das Ende (rechts) und das Ende (links) einer vorwärts sortierten Liste (von links nach rechts) genommen werden, bis alle Elemente wie folgt in die neue Liste verschoben wurden :

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]

Der Permutationsindex

Wenn nist 7(wie im obigen Back-To-Front-Beispiel), gibt es 7! = 5040mögliche Permutationen der (unterschiedlichen) Elemente.

Das erste (oder nullte, wenn Sie es vorziehen) Element in der lexikografisch sortierten Liste all dieser Permutationen wäre es [1,2,3,4,5,6,7]selbst.
Der zweite Punkt wäre [1,2,3,4,5,7,6].
Der vorletzte Punkt wäre [7,6,5,4,3,1,2].
Der letzte Punkt wäre [7,6,5,4,3,2,1].

Irgendwo in der Liste steht [7,1,6,2,5,3,4]- die Back-To-Front-Permutation.
Tatsächlich befindet es sich am Index 4421 (oder 4420, 0-basiert).

Die ersten 100 Begriffe der (1-basierten) Reihe i(n), mit denen angegeben wird, n=1sind:

[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, aber die Herausforderung selbst befasst sich nur mit nicht leeren Listen)

Zum Zeitpunkt der Veröffentlichung war diese Sequenz nicht im OEIS enthalten .

Die Ausgabe muss nur theoretisch funktionieren (machen Sie sich zum Beispiel keine Sorgen über überlaufende ganze Zahlen oder über unzureichende Ressourcen).

Das ist Code-Golf , also gewinnt die kürzeste Antwort in Bytes.

Lassen Sie sich jedoch nicht von Code-Golf-Sprachen abbringen - gute Lösungen sollten auch positiv bewertet werden!

Haskell , 32 Bytes

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

Probieren Sie es online!

Benutzt die Beziehung f(n-1) + f(n) = n! + 1. Benachbarte Mitglieder der Sequenzen addieren zu Fakultäten plus eins:

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 

Gelee , 6 Bytes

R!ḅ-_Ḃ

0-basiert. Probieren Sie es online!

Stark inspiriert von der Antwort auf @ Neils ES6 .

Erläuterung

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.

Aber wie?

Ich erkläre in meiner ES6-Antwort eine verwandte Technik zur Berechnung jeder Zahl. Die Formel lautet:

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

Eine Erkenntnis fiel mir beim Lesen von Neils ES6-Antwort auf . Diese Formel kann wie folgt vereinfacht werden:

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

Der Jelly Code R!ḅ-berechnet diese Formel. Allerdings hat jeder ungerade Wert von am Ende nein Extra + 0!, um das wir uns kümmern, indem wir subtrahieren n%2.

JavaScript (ES6), 38 Byte

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

0-indiziert. (Keine Erklärung, da ich eigentlich nicht weiß, warum es funktioniert, sorry.)

JavaScript (ES6), 44 Byte

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

0-basiert. Dies nutzt die Tatsache aus, dass die Zahlen als Summen von Fakultäten in folgendem Muster dargestellt werden können:

       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

Warum? Die Permutationen lassen sich in der Fakultätsbasis gut darstellen : Das Herausnehmen des n- ^ten Elements aus der verbleibenden Liste entspricht einer Ziffer von n an dieser Position. Wir wechseln zwischen dem letzten Artikel (höchste Ziffer) und dem ersten Artikel (Null). Daher können diese Zahlen in der Fakultätsbasis wie folgt dargestellt werden:

0
10
200
3010
40200
503010
6040200

und so weiter.

MATL , 17 Bytes

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

Die Ausgabe ist 1-indiziert.

Probieren Sie es online!

Erläuterung

Der Code wendet die Definition an: Erstellt die Back-to-Front-Permutation, generiert alle Permutationen, vergleicht die ersteren mit allen letzteren und gibt den Index der Übereinstimmung aus.

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

Gelee , 9 Bytes

RU;¥/ỤUŒ¿

Probieren Sie es online!

Huh, ich habe versucht, dies zu tun. Es stellt sich heraus, dass @Dennis zuerst veröffentlicht wurde, dies ist jedoch kürzer.

Erläuterung

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

Als Œ¿eingebautes Element zu haben, ist hier ziemlich praktisch, damit wir eine Permutation in ihren Index konvertieren können. Die anderen 7 Bytes sind für die Konstruktion der Back-to-Front-Permutation verantwortlich.

Die Art und Weise, wie wir dies tun, besteht zunächst darin, eine andere Permutation über das folgende Muster zu konstruieren:

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

Jedes Mal kehren wir die bisherige Liste um und fügen dann die nächste Ganzzahl hinzu. Das erzeugt nicht die Umstellung von hinten nach vorne, aber es ist eindeutig verwandt.

Die Permutation, die wir versuchen zu bekommen, ist 7 1 6 2 5 3 4. Wie hängt das zusammen? Nun, das Element in der 7. Position der Permutation, die wir haben, ist eine 7; das Element in der 1. Position ist eine 6; das Element in der 6. Position ist eine 5; Das Element an der 2. Position ist eine 4 und so weiter. Mit anderen Worten, es ist die Umkehrung der Permutation, die wir haben (mit den Elementen in umgekehrter Reihenfolge). Daher können wir nach dem Reduzieren die Permutation mit invertieren Ụund das Ergebnis mit umkehren U, um die gewünschte Rückwärtspermutation zu erhalten.

Es ist möglich, dass es hier Einsparungen gibt, weil es in Eile geschrieben wurde und das Gefühl hat, dass es zumindest ein gewisses Potenzial hat, Dinge neu zu ordnen. Ich bin mir jedoch nicht sicher, ob es möglich ist, ein ganzes Byte zu speichern.

Jelly , 10 8 Bytes

RṚżRFQŒ¿

Vielen Dank an @ ais523 für das Abschlagen von 2 Bytes und eine enorme Beschleunigung!

Probieren Sie es online!

Wie es funktioniert

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 Bytes

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

Verwendet die GNU Multiple Precision- Erweiterung.

Diese Funktion nutzt die Tatsache, dass i(n)gleich istn! - (n-1)! + (n-2)! - (n-3)! etc

Nervenzusammenbruch

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 Bytes

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

0-indiziert.

Pyth, 12 Bytes

x.pQ<Q.i_UQU

0-indiziert.

Erläuterung

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