Вступление

Лексикографические перестановки списка с n элементами могут быть пронумерованы от 0 до n ! - 1. Например, 3! = 6 перестановок (1,2,3)будет (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).

Когда к списку применяется перестановка, ее элементы упорядочиваются в том же порядке, что и числа в перестановке. Например, применяя перестановку (2,3,1)к l = (a,b,c)выходам (l[2],l[3],l[1]) = (b,c,a).

Инверсия перестановки определяется как перестановка, которая переворачивает эту операцию, то есть применение перестановки, а затем ее обратной (или наоборот) не изменяет массив. Например, обратное значение (2,3,1)равно (3,1,2), поскольку применяется к (b,c,a)доходностям (a,b,c).

Кроме того, обратная перестановка, примененная к самой перестановке, дает целые числа 1… n . Например, обращаясь (3,1,2)к (2,3,1)доходам (1,2,3).

Теперь определим функцию revind ( x ) как индекс обратной перестановки перестановки с индексом x . (Это A056019 , если вам интересно.)

Поскольку перестановка с индексом i изменяет только последние k элементов списка, если 0 ≤ i < k !, Мы можем добавить любое количество элементов в начало списка, не влияя на revind ( i ). Поэтому длина списка не влияет на результат.

Вызов

Ваша задача - реализовать revind ( x ). Вы напишете полную программу или функцию, которая принимает одно неотрицательное целое число x в качестве входных данных / аргументов и выводит / возвращает результат как одно неотрицательное целое число.

Вход и выход могут быть 0-индексированными или 1-индексированными, но это должно быть согласовано между ними.

Встроенные функции, которые генерируют перестановки по индексу, возвращают индекс перестановки или находят обратную перестановку, запрещены. (Встроенные функции, которые генерируют все перестановки или следующую перестановку, разрешены.)

Применяются стандартные правила игры в гольф .

Примеры

Приведенные ниже примеры имеют индекс 0.

Input    Output
0        0
1        1
2        2
3        4
4        3
5        5
6        6
13       10
42       51
100      41
1000     3628
2000     3974
10000    30593
100000   303016

Ссылочная реализация (Python 3)

def revind(n):
    from math import factorial
    from itertools import permutations, count
    l = next(filter(lambda x: factorial(x) > n, count(1)))
    pms = list(permutations(range(l)))
    return [k for k in range(len(pms)) if tuple(pms[n][i] for i in pms[k]) == pms[0]][0]

Желе , 6 байт

ịŒ!⁺iR

Ввод / вывод использует индексирование на основе 1. Очень медленный и жаждущий памяти.

верификация

Пока вход не превышает 8! = 40320 , достаточно рассмотреть все перестановки массива [1,…, 8] . Для последнего теста достаточно перестановок [1,…, 9] .

С немного измененным кодом, который учитывает только перестановки первых 8 или 9 положительных целых чисел, вы можете попробовать это онлайн!или проверьте все оставшиеся тестовые случаи .

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

ịŒ!⁺iR  Main link. Argument: n

 Œ!     Yield all permutations of [1, ..., n].
ị       At-index; retrieve the n-th permutation.
   ⁺    Duplicate the Œ! atom, generating all permutations of the n-th permutation.
     R  Range; yield [1, ..., n].
    i   Index; find the index of [1, ..., n] in the generated 2D array.

Альтернативный подход, 6 байтов (неверно)

Œ!Ụ€Ụi

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

Предваряя 8 (или 9 для последнего контрольного примера), мы можем попробовать онлайн!

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

Œ!Ụ€Ụi  Main link. Argument: n

Œ!      Yield all permutations of [1, ..., n].
  Ụ€    Grade up each; sort the indices of each permutation by the corresponding
        values. For a permutation of [1, ..., n], this inverts the permutation.
    Ụ   Grade up; sort [1, ..., n!] by the corresponding inverted permutations
        (lexicographical order).
     i  Index; yield the 1-based index of n, which corresponds to the inverse of
        the n-th permutation.

Mathematica, 74 байта

Max@k[i,Flatten@Outer[i=Permutations[j=Range@#];k=Position,{i[[#]]},j,1]]&

Использует 1-индексацию. Очень неэффективно. (использует ~ 11 ГБ памяти при входе 11)

объяснение

j=Range@#

Создайте список от 1 до N. Сохраните это в j.

i=Permutations[...]

Найти все перестановки j. Храните это в i.

k=Position

Сохраните Positionфункцию в k. (чтобы уменьшить количество байтов при Positionповторном использовании )

Flatten@Outer[...,{i[[#]]},j,1]

Найти обратную перестановку N-й перестановки.

Max@k[i,...]

Найти k( Position) обратной перестановки в i(все перестановки)

Используя встроенные модули, 46 43 байта

a[(a=Ordering)/@Permutations@Range@#][[#]]&

1-индексироваться.

MATL , 15 байт

:Y@tGY)Z)G:=!Af

Вход и выход основаны на 1.

Аналогичен ответу CJam от @ MartinEnder , но находит обратную перестановку путем составления всех возможных перестановок с той, которая указана на входе, и выяснения, которая стала перестановкой тождеств.

В онлайн-компиляторе не хватает памяти для ввода 10.

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

объяснение

:      % Implicitly input N. Push range [1 2 ... N]
Y@     % Matrix witll all permutations of size N. Each permutation is a row
tGY)   % Duplicate. Get the N-th row
Z)     % Use that as a column index into the matrix of all permutations
G:=    % Compare each row with [1 2 ... N]
!Af    % Find index of the row that matches. Implicitly display

Pyth, 12 байт

xJ.phQxL@JQh

Тестирование

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

Объяснение:

xJ.phQxL@JQh
xJ.phQxL@JQhQ    Implicit variable introduction
                 Q = eval(input())
  .phQ           Form all permutations of range(Q+1), namely [0, 1, .. Q]
 J               Save to J.
        @JQ      Take the Qth element of J.
      xL   hQ    Map all elements of [0, 1, ..., Q] to their index in above
x                Find the index in J of the above.

05AB1E , 14 13 байт

Очень неэффективная память. Теперь еще больше неэффективной памяти (но на 1 байт короче).
Диапазон на основе 0
Использует кодировку CP-1252 .

ƒ¹ÝœD¹èNkˆ}¯k

Попробуйте онлайн! или как модифицированный набор тестов

объяснение

ƒ               # for N in range[0 .. x]
 ¹ÝœD           # generate 2 copies of all permutations of range[0 .. x]
     ¹è         # get permutation at index x
       Nkˆ      # store index of N in that permutation in global list
         }      # end loop
          ¯k    # get index of global list (inverse) in list of permutations

CJam , 16 байтов

ri_)e!_@=_$\f#a#

Индексы начинаются с 0.

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

Я не становлюсь более неэффективным, чем это ... не 8хватает памяти с настройками Java по умолчанию для входов больше (но в принципе работает для произвольных входов, учитывая достаточное количество вселенных времени и памяти).

объяснение

ri    e# Read input and convert to integer N.
_)e!  e# Duplicate N, get all permutations of [0 1 ... N].
_@=   e# Duplicate permutations, get the Nth permutation.
_$    e# Duplicate and sort to get the sorted range [0 1 ... N].
\f#   e# For each of these values, get its index in the Nth permutation.
      e# This inverts the permutation.
a#    e# Find the index of this new permutation in the list of all permutations.

GAP , 108 байт

h:=l->n->PositionProperty(l,p->l[n]*p=());
f:=n->h(Set(SymmetricGroup(First([1..n],k->Factorial(k)>=n))))(n);

1-индексироваться. Новые строки не учитываются, они не нужны. Мне не обязательно назначать конечную функцию имени, но ...

hявляется функцией карри, которая берет список перестановок и индекс в этом списке и возвращает индекс обратной перестановки. Без ограничений я бы просто обошелся Position(l,l[n]^-1). fвызывает эту функцию с отсортированными перестановками достаточно большой симметричной группы и заданным n.

Я мог бы просто написать SymmetricGroup(n), тогда функция могла бы быть вычислена для значений до 9. Поскольку решения уже намного меньше, я предпочитаю делать это:

gap> f(100001);
303017

Действительно эффективное 0-индексированное решение, которое работает для аргументов ниже 99! (и может работать для аргументов ниже 999! за счет одного байта):

f:=function(n)
 local m,l,p,i,g;
 m:=First([1..99],k->Factorial(k)>n);
 g:=List([m-1,m-2..0],Factorial);
 l:=[1..m];
 p:=[];
 for i in g do
  Add(p,Remove(l,QuoInt(n,i)+1));
  n:=n mod i;
 od;
 return Sum(ListN(List([1..m],i->Number([1..Position(p,i)],j->p[j]>i)),g,\*));
end;

После удаления пробела это имеет 255 байтов.

JavaScript (ES6), 163 120 110 байт

f=(n,a=[],i=0,r=0,[j,...b]=a)=>n?a.splice(n%-~i,0,i)|f(n/++i|0,a,i):i?f(n,b,i-1,b.reduce((r,k)=>r+=k>j,r*i)):r

<input type=number min=0 oninput=o.textContent=f(+this.value)><pre id=o>

0 индексированные. Работает путем преобразования индекса в перестановку, инвертирования его и последующего преобразования обратно в индекс. Редактировать: Экономия около 25% путем fинвертирования и перестановки перестановок, а затем gпреобразования обратной перестановки обратно в индекс. Сохранение еще 10 байтов путем объединения двух рекурсивных вызовов в одну функцию. Ungolfed:

function index(n) {
    var a = [0];
    for (var i = 1; n = Math.floor(n / i); i++) {
        var j = i - n % (i + 1);
        for (var k = 0; k < i; k++) {
            if (a[k] > j) a[k]++;
        }
        a.push(j);
    }
    a = [...a.keys()].map(k => a.indexOf(k));
    while (i) {
        n *= i--;
        j = a.pop();
        for (k = 0; k < i; k++) {
            if (a[k] > j) n++;
        }
    }
    return n;
}

J, 55 50 байт

g=:/:~i.@#
[:(#\.#.+/@(<{.)\.)@g(-i.)@>:g@g@,/@#:]

Основано на эссе индексу перестановок .

Этот код требует только памяти порядка, nно использует больше времени, так как он сортирует список nраз и ищет егоn по каждому индексу.

Используя встроенную функцию, /:которая может найти оценку списка и обратную перестановку, существует 42-байтовое решение, которое является более эффективным.

[:(#\.#.+/@(<{.)\.)@/:(-i.)@>:/:@/:@,/@#:]

Эта версия требует только 44 секунд для вычисления последнего контрольного примера по сравнению с другим, который требует 105 секунд.

использование

   g =: /:~i.@#
   f =: [:(#\.#.+/@(<{.)\.)@g(-i.)@>:g@g@,/@#:]
   (,.f"0) 0 1 2 3 4 5 6 13 42 100 1000 2000 10000
    0     0
    1     1
    2     2
    3     4
    4     3
    5     5
    6     6
   13    10
   42    51
  100    41
 1000  3628
 2000  3974
10000 30593
   timex 'r =: f 100000'
105.787
   r
303016

Желе , 14 13 9 байт

-4 байта благодаря @Dennis (который он продолжил, используя быстрый ⁺в своем ответе )

Œ!ịịŒ!$iR

Еще одна очень медленная реализация.
Здесь используется индексация на основе 1, поэтому ожидаемые результаты:

input:  1 2 3 4 5 6 7 8  9 10 11
output: 1 2 3 5 4 6 7 8 13 19  9

Нет смысла даже размещать онлайн-ссылку на IDE, поскольку TIO убивает при входе 10. Локальные результаты (последний очень медленный и требует тонны памяти!):

C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 1
1
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 2
2
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 3
3
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 4
5
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 5
4
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 6
6
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 7
7
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 8
8
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 9
13
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 10
19
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 11
9

Как?

Œ!ịịŒ!$iR - Main link 1: n
      $   - last two links as a monad
    Œ!    -     permutations of implicit range [1,2,3,...,n]
   ị      -     value at index n (the nth permutation)
Œ!        - permutations of implicit range [1,2,3,...,n]
  ị       - value at index (the indexes of the permuted values in the nth permutation)
       i  - index of
        R - range [1,2,3,...,n]

Примечание: нет необходимости сортировать перестановки, так как мы используем один и тот же порядок как для нахождения перестановки, так и для обратной.

Python 2, 116 114 байт

from itertools import*
def f(n):r=range(n+1);l=list(permutations(r));print l.index(tuple(l[n].index(v)for v in r))

repl.it

0 на основе. Медленно и память голодна, но мало байтов.

Не используя перестановочных функций; и память и время эффективно. 289 285 байт

-4 байта благодаря @Christian Sievers (полная перестановка уже сформирована)

h=lambda n,v=1,x=1:v and(n>=v and h(n,v*x,x+1)or(v,x-1))or n and h(n-1,0,n*x)or x
i=lambda p,j=0,r=0:j<len(p)and i(p,j+1,r+sum(k<p[j]for k in p[j+1:])*h(len(p)-j-1,0))or r
def f(n):t,x=h(n);g=range(x);o=g[:];r=[];exec"t/=x;x-=1;r+=[o.pop(n/t)];n%=t;"*x;return i([r.index(v)for v in g])

Я знаю, что это кодовый гольф, но я думаю, что @ Pietu1998 также заинтересован в эффективных реализациях.

Смотрите это в действии на repl.it

Хотя для этого используется больше байтов, чем для эталонной реализации, для сравнения n=5000000:

ref:    6GB 148s  
this: 200KB <1ms

f является функцией обратного индекса.

fсначала получает следующий факториал выше n, tи целое число, факториал которого, xвызывая h(n), и устанавливает g=range(x)элементы, которые будут составлять перестановку,o=g[:] и держатель перестановки,r=[]

Затем он создает перестановку по индексу n, поочередно popизвлекая индексы факториального базового представления из nэлементов oи добавляя их к r. Факториальное базовое представление находится с помощью div и mod nс tгде tделится на xи xуменьшается до1 .

Наконец, он находит индекс обратной перестановки, вызывая iс обратной перестановкой,[r.index(v)for v in g]

h является функцией двойного назначения для вычисления факториала неотрицательного целого числа или для вычисления следующего факториала выше неотрицательного целого числа и целого числа, которое делает этот факториал.

В этом состоянии по умолчанию , v=1и это делает последний путем умножения vна x(также изначально 1) и приращении xдо тех пор , nпока по крайней мере, большой, то она возвращается vиx-1 в кортеже.

Вычислить n!один вызов, h(n,0)который умножается x(изначально 1) на nи уменьшается nдо тех пор, nпока 0он не вернется x.

iобеспечивает лексикографическом индекс перестановки, p, детали [0,1,...n]путем сложения продуктов факториала факторного основания каждого индекс, h(len(p)-j-1,0)и сколько элементов справа от индекса меньше , чем значение в этом индексе, sum(k<p[j]for k in p[j+1:]).

Python 2, 130 129 байт

p=lambda x,k,j=1:x[j:]and p(x,k/j,j+1)+[x.pop(k%j)]
n=input();r=range(n+2);k=0
while[p(r*1,n)[i]for i in p(r*1,k)]>r:k+=1
print k

На самом деле , 18 11 байтов

Этот ответ использует алгоритм в ответе Денниса «Желе», но имеет индекс 0. Предложения по игре в гольф приветствуются! Попробуйте онлайн!

4╞r;)╨E╨♂#í

Ungolfing

      Implicit input n.
4╞    Push 4 duplicates of n. Stack: n, n, n, n
r;)   Push the range [0...n], and move a duplicate of that range to BOS for later.
╨E    Push the n-length permutations of [0...n] and get perm_list[n].
        Stack: perm_list[n], n, [0...n]
╨     Push the n-length permutations of perm_list[n].
♂#    Convert every "list" in the zip to an actual list.
        Stack: perm(perm_list[n]), [0...n]
í     Get the index of [0...n] in the list of permutations of perm_list[n].
      Implicit return.