El reto

Dado el número de elementos, nen una lista ordenada no vacía, se genera el índice, i(n)en el que su
" Permutación de atrás hacia
adelante " residiría en una lista de todas las permutaciones si dichas permutaciones se ordenaran lexicográficamente.

Los resultados pueden estar basados ​​en 0 o 1, solo diga cuál (es decir i, no n).

La permutación de atrás hacia adelante

... es el resultado de crear una lista de elementos tomando repetidamente la parte posterior (derecha) y luego frontal (izquierda) de una lista ordenada hacia adelante (de izquierda a derecha) hasta que todos los elementos se hayan movido a la nueva lista, así :

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]

El índice de permutación

Si nes 7(como en el ejemplo anterior al frente) hay 7! = 5040posibles permutaciones de los elementos (distintos).

El primer elemento (o cero si lo prefiere) en la lista ordenada lexicográficamente de todas esas permutaciones sería él [1,2,3,4,5,6,7]mismo.
El segundo elemento sería [1,2,3,4,5,7,6].
El penúltimo artículo sería [7,6,5,4,3,1,2].
El artículo final sería [7,6,5,4,3,2,1].

En algún lugar de la lista está [7,1,6,2,5,3,4]: la permutación de atrás hacia adelante.
De hecho, reside en el índice 4421 (o 4420, basado en 0).

Los primeros 100 términos de la serie (basada en 1) de i(n)declaración con n=1son:

[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, pero el desafío en sí solo trata con listas no vacías)

Al momento de publicar esta secuencia no aparecía en el OEIS .

La salida solo debe funcionar en teoría (no se preocupe por desbordar enteros o quedarse sin recursos, por ejemplo).

Este es el código de golf , por lo que gana la respuesta más corta en bytes.

Sin embargo, no deje que los lenguajes de código de golf lo disuadan: ¡las buenas soluciones también deberían recibir votos positivos!

Haskell , 32 bytes

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

Pruébalo en línea!

Utiliza la relación f(n-1) + f(n) = n! + 1. Los miembros adyacentes de las secuencias se suman a los factoriales más uno:

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 

Jalea , 6 bytes

R!ḅ-_Ḃ

Basado en 0. Pruébalo en línea!

Muy inspirado por la respuesta ES6 de @ Neil .

Explicación

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.

¿Pero cómo?

Explico en mi respuesta ES6 una técnica relacionada para calcular cada número. La fórmula es esta:

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

Me di cuenta cuando leí la respuesta ES6 de @ Neil . Esta fórmula se puede simplificar así:

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

El código Jelly R!ḅ-calcula esta fórmula. Sin embargo, cada valor impar de ntendrá un extra + 0!al final, del cual nos ocuparemos restando n%2.

JavaScript (ES6), 38 bytes

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

0 indexado. (No hay explicación porque en realidad no sé por qué funciona, lo siento).

JavaScript (ES6), 44 bytes

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

Basado en 0. Esto aprovecha el hecho de que los números se pueden representar como sumas de factoriales en el siguiente patrón:

       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

¿Por qué? Las permutaciones se pueden representar muy bien en la base de factorial : tomar el n ^º artículo hacia fuera de los corresponde lista restante a un dígito de n en esa posición. Estamos alternando entre tomar el último elemento (dígito más alto) y el primer elemento (cero); por lo tanto, en la base factorial, estos números se pueden representar como:

0
10
200
3010
40200
503010
6040200

y así.

MATL , 17 bytes

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

La salida está indexada en 1.

Pruébalo en línea!

Explicación

El código aplica la definición: construye la permutación de atrás hacia adelante, genera todas las permutaciones, compara la primera con todas las últimas y genera el índice de coincidencia.

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

Jalea , 9 bytes

RU;¥/ỤUŒ¿

Pruébalo en línea!

Huh, estaba tratando de FGITW esto. Resulta que @Dennis publicó primero, pero esto es más corto.

Explicación

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

Tenerlo Œ¿incorporado es bastante útil aquí, lo que nos permite convertir una permutación a su índice, por lo que los otros 7 bytes son responsables de construir la permutación de atrás hacia adelante.

La forma en que hacemos esto es primero construir una permutación diferente, a través del siguiente patrón:

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

Cada vez, estamos invirtiendo la lista que tenemos hasta ahora, y luego agregamos el siguiente entero. Eso no produce la permutación de atrás hacia adelante, pero está claramente relacionada.

La permutación que estamos tratando de obtener es 7 1 6 2 5 3 4. ¿Cómo se relaciona esto? Bueno, el elemento en la séptima posición de la permutación que tenemos es un 7; el elemento en la primera posición es un 6; el elemento en la sexta posición es un 5; el elemento en la segunda posición es un 4, y así sucesivamente. En otras palabras, es el inverso de la permutación que tenemos (con los elementos en orden inverso). Como tal, después de la reducción, podemos invertir la permutación Ụe invertir el resultado Upara obtener la permutación de atrás hacia adelante que deseamos.

Es posible que haya ahorros aquí, porque fue escrito a toda prisa y parece que tiene al menos algún potencial para reorganizar las cosas. Sin embargo, no estoy seguro de que sea posible guardar un byte completo.

Jalea , 10 8 bytes

RṚżRFQŒ¿

¡Gracias a @ ais523 por jugar 2 bytes y una tremenda aceleración!

Pruébalo en línea!

Cómo funciona

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;

Utiliza la extensión GNU Multiple Precision .

Esta función aprovecha el hecho de que i(n)es igual an! - (n-1)! + (n-2)! - (n-3)! etc

Descompostura

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

Lote, 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 indexado.

Pyth, 12 bytes

x.pQ<Q.i_UQU

0 indexado.

Explicación

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