Перекрестный индекс перестановок

12

Соревнование

Учитывая количество элементов, nв непустом отсортированном списке выведите индекс, i(n)при котором его
« Перестановка вперед-назад »
будет находиться в списке всех перестановок, если указанные перестановки будут отсортированы лексикографически.

Результаты могут быть на основе 0 или 1, просто скажите, какие (то есть i, нет n).

Перестановка вперед-назад

... является результатом построения списка элементов путем многократного выбора заднего (правого), затем переднего (левого) списка, отсортированного вперед (слева направо), пока все элементы не будут перемещены в новый список, как показано ниже. : 

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]

Индекс перестановки

Если nесть 7(как в приведенном выше примере Back-To-Front), 7! = 5040возможны перестановки (отдельных) элементов.

Первый (или нулевой, если вы предпочитаете) элемент в лексикографически отсортированном списке всех этих перестановок будет [1,2,3,4,5,6,7]сам по себе.
Второй пункт будет [1,2,3,4,5,7,6].
Предпоследний пункт будет [7,6,5,4,3,1,2].
Последний пункт будет [7,6,5,4,3,2,1].

Где-то в списке - [7,1,6,2,5,3,4]перестановка Back-To-Front.
Фактически он находится в индексе 4421 (или 4420, на основе 0).

Первыми 100 терминами (основанной на 1) серии i(n)заявлений 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)=1но сама задача касается только непустых списков)

На момент публикации эта последовательность не появилась в OEIS .

Вывод должен работать только теоретически (например, не беспокойтесь о переполнении целых чисел или нехватке ресурсов).

Это код-гольф , поэтому выигрывает самый короткий ответ в байтах.

Тем не менее, не позволяйте языкам кода-гольфа отговаривать вас - хорошие решения тоже должны вызывать отклики!

code-golf sequence sorting permutations Джонатан Аллан
источник
1
Надеюсь, что все в порядке с этим - это было в песочнице больше месяца без обратной связи.
Джонатан Аллан
Связанный - Нумерация перестановок
xnor
Это чередующиеся факториалы, каждая другая запись увеличена на 1.
xnor
@xnor да, они есть - перестановка «от начала к концу» имеет предыдущий индекс, который находится перед спиной к фронту.
Джонатан Аллан

Ответы:

8

Haskell , 32 байта

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

Попробуйте онлайн!

Использует отношения f(n-1) + f(n) = n! + 1. Соседние члены последовательностей добавляют к факториалам плюс один:

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
XNOR
источник
6

Желе , 6 байт

R!ḅ-_Ḃ

0 на основе. Попробуйте онлайн!

Сильно вдохновлен ответом @ Neil's ES6 .

объяснение

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.

Но как?

Я объясняю в своем ответе ES6 связанную технику для вычисления каждого числа. Формула такая:

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

Осознание поразило меня, читая ответ @ 6 Нейла . Эта формула может быть упрощена следующим образом:

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

Код Jelly R!ḅ-рассчитывает эту формулу. Однако каждое нечетное значение в конце nбудет иметь дополнительное + 0!значение, о котором мы заботимся, вычитая n%2.

ETHproductions
источник
1
Поздравляю, вы нашли мое решение! (обратите внимание, что это 0).
Джонатан Аллан
Цифры, которые вы использовали бы ḅ-рано или поздно ...: P Отличная работа!
Деннис
@JonathanAllan Я знал, как только увидел, что ты отправил вызов, что будет хитрый ответ Желе. Хотя, чтобы найти его, потребовалось много времени. Большой вызов :-)
ETHproductions
4

JavaScript (ES6), 38 байт

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

0 индексированные. (Никаких объяснений, потому что я не знаю, почему это работает, извините.)

Нил
источник
1
О, это гений. Мой ответ занимает (n-1)*(n-1)! + (n-3)*(n-3)! + (n-5)*(n-5)! + ..., что эквивалентно тому, (n! - (n-1)!) + ((n+2)! - (n-3)!) + ((n-4)! - (n-5)!) + ...что делает ваш ответ.
ETHproductions
3

JavaScript (ES6), 44 байта

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

0 на основе. Это использует тот факт, что числа могут быть представлены в виде сумм факториалов по следующей схеме:

       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

Почему? Перестановки могут быть хорошо представлены в факториальной базе : удаление n- го элемента из оставшегося списка соответствует цифре n в этой позиции. Мы чередуем выбор последнего элемента (наибольшая цифра) и первого элемента (ноль); поэтому в факториальной базе эти числа могут быть представлены как:

0
10
200
3010
40200
503010
6040200

и так далее.

ETHproductions
источник
2

MATL , 17 байт

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

Выход 1 индексируется.

Попробуйте онлайн!

объяснение

Код применяет определение: строит перестановку «назад к фронту», генерирует все перестановки, сравнивает первую со всеми последними и выводит индекс соответствия.

:        % 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
Луис Мендо
источник
2

Желе , 9 байт

RU;¥/ỤUŒ¿

Попробуйте онлайн!

Да, я пытался это сделать. Оказывается, @Dennis размещен первым, но это короче.

объяснение

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

Наличие Œ¿в качестве встроенного достаточно удобно, что позволяет нам преобразовывать перестановку в ее индекс, поэтому остальные 7 байтов отвечают за построение перестановки «назад к фронту».

Сначала мы создаем другую перестановку по следующей схеме:

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

Каждый раз мы переворачиваем список, который у нас есть, затем добавляем следующее целое число. Это не приводит к перестановке «назад к фронту», но это явно связано.

Перестановка, которую мы пытаемся получить, такова 7 1 6 2 5 3 4. Как это связано? Хорошо, элемент в 7-й позиции перестановки, которую мы имеем, является 7; элемент в 1-й позиции - 6; элемент в 6-й позиции - 5; элемент во 2-й позиции равен 4, и так далее. Другими словами, это обратная перестановка, которую мы имеем (с элементами в обратном порядке). Таким образом, после сокращения мы можем инвертировать перестановку Ụи обратить результат с помощью, Uчтобы получить обратную перестановку, которую мы хотим.

Возможно, что здесь есть экономия, потому что она написана на скорую руку и кажется, что у нее есть хоть какой-то потенциал для перестановки вещей. Я не уверен, что возможно сохранить целый байт.


источник
2

Желе , 10 8 байт

RṚżRFQŒ¿

Спасибо @ ais523 за 2 байта и огромное ускорение!

Попробуйте онлайн!

Как это устроено

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, ...].
Деннис
источник
1
Похоже, вы пропустили Œ¿встроенное. Ваш метод построения списка на один байт короче моего, поэтому, если вы можете заменить его i@Œ!на это, вы сможете уменьшить его до 8 байт, опередив мой ответ.
Полностью забыл, что это была вещь. Благодарность!
Деннис
0

PHP, 86 байт

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

Использует расширение GNU Multiple Precision .

Эта функция использует тот факт, что i(n)равенn! - (n-1)! + (n-2)! - (n-3)! etc

Сломать

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
roberto06
источник
0

Пакетная, 79 байтов

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

0 индексированные.

Нил
источник
0

Pyth, 12 байт

x.pQ<Q.i_UQU

0 индексированные.

объяснение

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

источник