Le défi

Étant donné le nombre d'éléments, ndans une liste triée non vide, affichez l'index, i(n)auquel sa
" permutation de l'arrière-plan "
résiderait dans une liste de toutes les permutations si ces permutations étaient triées lexicographiquement.

Les résultats peuvent être basés sur 0 ou 1, dites simplement lequel (c'est-à-dire i, non n).

La permutation back-to-front

... est le résultat de la construction d'une liste d'éléments en prenant à plusieurs reprises l'arrière (droite) puis l'avant (gauche) d'une liste triée vers l'avant (de gauche à droite) jusqu'à ce que tous les éléments aient été déplacés vers la nouvelle liste, comme ceci :

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]

L'indice de permutation

Si nc'est le cas 7(comme dans l'exemple Back-To-Front ci-dessus), il existe 7! = 5040des permutations possibles des éléments (distincts).

Le premier élément (ou zéro si vous préférez) dans la liste triée lexicographiquement de toutes ces permutations serait lui- [1,2,3,4,5,6,7]même.
Le deuxième élément serait [1,2,3,4,5,7,6].
L'avant-dernier article serait [7,6,5,4,3,1,2].
Le dernier élément serait [7,6,5,4,3,2,1].

Quelque part dans la liste se trouve [7,1,6,2,5,3,4]- la permutation Back-To-Front.
En fait, il réside à l'indice 4421 (ou 4420, basé sur 0).

Les 100 premiers termes de la série d' i(n)énoncés avec (1) n=1sont:

[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, mais le défi lui-même ne concerne que les listes non vides)

Au moment de la publication, cette séquence n'apparaissait pas dans l' OEIS .

La sortie ne doit fonctionner qu'en théorie (ne vous inquiétez pas du débordement d'entiers ou de la pénurie de ressources par exemple).

Il s'agit de code-golf , donc la réponse la plus courte en octets l'emporte.

Cependant, ne laissez pas les langages de golf de code vous dissuader - les bonnes solutions devraient également obtenir des votes positifs!

Haskell , 32 octets

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

Essayez-le en ligne!

Utilise la relation f(n-1) + f(n) = n! + 1. Les membres adjacents des séquences s'ajoutent aux factoriels plus un:

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 

Gelée , 6 octets

R!ḅ-_Ḃ

Basé sur 0. Essayez-le en ligne!

Fortement inspiré par la réponse ES6 de @ Neil .

Explication

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.

Mais comment?

J'explique dans ma réponse ES6 une technique connexe pour calculer chaque nombre. La formule est la suivante:

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

Une réalisation m'a frappé en lisant la réponse ES6 de @ Neil . Cette formule peut être simplifiée comme suit:

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

Le code Jelly R!ḅ-calcule cette formule. Cependant, chaque valeur impaire de naura un supplément + 0!à la fin, que nous prenons en charge en soustrayant n%2.

JavaScript (ES6), 38 octets

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

0 indexé. (Aucune explication car je ne sais pas vraiment pourquoi cela fonctionne, désolé.)

JavaScript (ES6), 44 octets

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

Basé sur 0. Cela profite du fait que les nombres peuvent être représentés comme des sommes de factorielles dans le modèle suivant:

       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

Pourquoi? Les permutations peuvent être représentés facilement dans la base de factorielle : prendre le n ^ième élément de la liste restant correspond à un chiffre n à cette position. Nous alternons entre prendre le dernier élément (chiffre le plus élevé) et le premier élément (zéro); par conséquent, dans la base factorielle, ces nombres peuvent être représentés comme:

0
10
200
3010
40200
503010
6040200

etc.

MATL , 17 octets

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

La sortie est indexée 1.

Essayez-le en ligne!

Explication

Le code applique la définition: construit la permutation d'arrière en avant, génère toutes les permutations, compare la première à toutes les secondes et génère l'index de la correspondance.

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

Gelée , 9 octets

RU;¥/ỤUŒ¿

Essayez-le en ligne!

Huh, j'essayais de FGITW cela. Il s'avère que @Dennis a été publié en premier, mais c'est plus court.

Explication

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

Le fait d'avoir Œ¿une fonction intégrée est assez pratique ici, nous permettant de convertir une permutation en son index, de sorte que les 7 autres octets sont responsables de la construction de la permutation d'arrière-plan.

La façon dont nous le faisons est d'abord de construire une permutation différente, via le modèle suivant:

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

Chaque fois, nous inversons la liste que nous avons jusqu'à présent, puis ajoutons le prochain entier. Cela ne produit pas la permutation d'arrière en avant, mais c'est clairement lié.

La permutation que nous essayons d'obtenir est 7 1 6 2 5 3 4. Comment est-ce lié? Eh bien, l'élément en 7ème position de la permutation que nous avons est un 7; l'élément en 1ère position est un 6; l'élément en 6ème position est un 5; l'élément en 2ème position est un 4, et ainsi de suite. En d'autres termes, c'est l'inverse de la permutation que nous avons (avec les éléments dans l'ordre inverse). En tant que tel, après la réduction, nous pouvons inverser la permutation avec Ụet inverser le résultat avec Upour obtenir la permutation d'arrière-plan que nous voulons.

Il est possible qu'il y ait des économies ici, car il a été écrit à la hâte et donne l'impression qu'il a au moins un certain potentiel de réorganisation. Je ne suis pas sûr qu'il soit possible d'enregistrer un octet entier, cependant.

Gelée , 10 8 octets

RṚżRFQŒ¿

Merci à @ ais523 pour avoir joué au golf sur 2 octets et pour une accélération formidable!

Essayez-le en ligne!

Comment ça fonctionne

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 octets

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

Utilise l' extension GNU Multiple Precision .

Cette fonction tire parti du fait qu'elle i(n)est égale àn! - (n-1)! + (n-2)! - (n-3)! etc

Panne

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

Lot, 79 octets

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

0 indexé.

Pyth, 12 octets

x.pQ<Q.i_UQU

0 indexé.

Explication

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