Задача

Сформировать первоначальный зашифрованный список, от движений , что вставки Сортировать бы сортировать его. Исходный список будет содержать все числа от 0до N-1(включительно), где Nуказан размер ввода.

вход

Список, содержащий необходимые шаги для сортировки списка. Каждое значение представляет количество слотов, смещенных на исходное (скремблированное) число, чтобы быть в его правильном положении, имейте в виду, что этот процесс идет слева направо.
Значение в (0-индексированной) позиции iв списке ввода будет между 0и iвключительно.
Вам не нужно обрабатывать неправильные входные данные, в этом случае допустимо любое поведение (сбой, бесконечный цикл и т. Д.).

Выход

Скремблированный список

Пошаговая генерация ходов

Scrambled List | Moves to sort
[4,0,2,1,3,5]  | [0, , , , , ] #4 stay in place
[4,0,2,1,3,5]  | [0,1, , , , ] #0 is moved 1 slot to the left
[0,4,2,1,3,5]  | [0,1,1, , , ] #2 is moved 1 slot
[0,2,4,1,3,5]  | [0,1,1,2, , ] #1 is moved 2 slot
[0,1,2,4,3,5]  | [0,1,1,2,1, ] #3 is moved 1 slot
[0,1,2,3,4,5]  | [0,1,1,2,1,0] #5 is in the right place already
[0,1,2,3,4,5]

Итак, для ввода [0,1,1,2,1,0]ваша программа должна выводиться [4,0,2,1,3,5].
Имейте в виду, что движения не в положение в (окончательном) отсортированном списке, а в отсортированном сегменте (выделенный жирным шрифтом раздел)

Тестовые случаи

[0,0,0] -> [0,1,2]
[0,1,0,1] -> [1,0,3,2]
[0,0,0,0,0,5] -> [1,2,3,4,5,0]
[0,1,2,3] -> [3,2,1,0]
[0,1,1,1] -> [3,0,1,2]
[0,1,1,2,1,0] -> [4,0,2,1,3,5]

выигрыш

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

Желе , 12 байт

L!_UÆ¡$œ?J’U

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

объяснение

Мы можем в основном видеть два списка (вход и выход) как кодирование целого числа; вход кодирует целое число в факториальной базе, а выход кодирует целое число как перестановку. К счастью, у Jelly есть встроенные функции, которые уже очень близки к обеим этим кодировкам, так что это просто вопрос написания небольших фрагментов кода для преобразования в целое число, а затем обратно в другую кодировку.

L!_UÆ¡$œ?J’U
   U           Reverse {the input}
    Æ¡         and convert from base factorial to integer;
  _   $        subtract that from
L!             the factorial of the length of {the input};
       œ?      then take the nth permutation of
         J     [1,2,...,l], where l is the length of {the input},
          ’    subtract 1 from every elevent,
           U   and reverse it

В случае базового факториала мы можем заметить, что первый элемент списка должен быть 0, второй может быть 0 или 1, третий должен быть 0/1/2 и так далее. Таким образом, мы должны обратить ввод, чтобы привести его элементы в обычный порядок записи для базового преобразования.

Кроме того, чтобы относительные порядки преобразования факториала и преобразования перестановки соответствовали операции, которую использует сортировка вставки, нам нужно сделать две корректировки: изменить последовательность перестановок и изменить порядок списка вывода. Перевернуть список вывода достаточно просто, для этого требуется только Uконец программы. Чтобы изменить последовательность перестановок, мы вычитаем из факториала входную длину (это работает, потому что базовый факториал производит число в диапазоне от 0 до (длина! -1), тогда как перестановки нумеруются Jelly от 1 до длины! создавая неявное значение off-by-one, которое компенсирует значение off-by-one, которое вы обычно получаете при вычитании индекса перестановки из факториала).

Желе , 9 байт, в сотрудничестве с @JonathanAllan

UÆ¡Nœ?J’U

Эта версия программы очень похожа, но использует другой метод изменения последовательности перестановок; простого отрицания ввода с помощью Nдостаточно, чтобы œ?обработать порядок в обратном порядке. Кроме того, он работает так же, как и в предыдущей программе.

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

Mathematica, 92 байта

Permute[Range[l=Length@#]-1,(c=Cycles@{#}&)@{}©##&@@c[i-0~Range~#[[i]]]~Table~{i,l,1,-1}]&

Чистая функция, принимающая список неотрицательных целых чисел в качестве входных данных и возвращающая список неотрицательных целых чисел. Приведенный выше код содержит a ©, что неверно: это заполнитель для 3-байтового символа U + F3DE, который Mathematica представляет кругом с точкой в ​​нем, и который представляет композицию перестановок.

c=Cycles@{#}&определяет функцию, которая преобразует список целых чисел в Cyclesобъект, представляющий перестановку; например, c[{3,4}]это транспонирование местами перестановки элементов 3 и 4 списка. c[i-0~Range~#[[i]]]~Table~{i,l,1,-1}]берет список ввода и генерирует перестановки, необходимые для отмены сортировки вставки. Затем c@{}©##&@@сочиняет все эти перестановки вместе, начиная с перестановки тождеств c@{}. Наконец, Permute[Range[l=Length@#]-1,...]применяет эту перестановку к 0-индексированному списку соответствующей длины.

Python 2, 79 68 байт

Спасибо Krazor за сохранение 10 байтов

Спасибо TuukkaX за сохранение 1 байта

a=input();b=range(len(a));print[b.pop(j-a[j])for j in b[::-1]][::-1]

Работает, генерируя ходы в обратном направлении

JavaScript (ES6), 69 65 63 байта

a=>a.reverse(b=[...a.keys()]).map(o=>+b.splice(~o,1)).reverse()

Досадно, что и вход, и выход находятся в неправильном порядке. Редактировать: 4 байта сохранены благодаря @Arnauld. Сохранено 2 байта благодаря @ETHproductions.

JavaScript (ES6), 73 71 байт

Сохранено 2 байта благодаря ETHproductions

m=>(a=m.map((_,i)=>j=i)).map(_=>a.splice(j,0,+a.splice(j-m[j--],1)))&&a

Контрольные примеры

let f =

m=>(a=m.map((_,i)=>j=i)).map(_=>a.splice(j,0,+a.splice(j-m[j--],1)))&&a

console.log(JSON.stringify(f([0,0,0])));       // -> [0,1,2]
console.log(JSON.stringify(f([0,1,0,1])));     // -> [1,0,3,2]
console.log(JSON.stringify(f([0,0,0,0,0,5]))); // -> [1,2,3,4,5,0]
console.log(JSON.stringify(f([0,1,2,3])));     // -> [3,2,1,0]
console.log(JSON.stringify(f([0,1,1,1])));     // -> [3,0,1,2]
console.log(JSON.stringify(f([0,1,1,2,1,0]))); // -> [4,0,2,1,3,5]

Haskell , 85 байт

f x|n<-length x-1=reverse x#[n,n-1..0]
(n:r)#l=r#(take n l++drop(n+1)l)++[l!!n]
x#l=x

Попробуйте онлайн! Пример использования: f [0,1,1,2,1,0]доходность[4,0,2,1,3,5] .

f xвызывает функцию #с xобращенным списком и списком [length x - 1, length x - 2, ... , 0]. (n:r)#lвыполняет обратную вставку сортировать по рекурсивно принимая nй элемент из l, где l!!nдает nй элемент и take n l++drop(n+1)lдает список lс nго элемента удален.

perl, 61 байт

@o=@p=0..@ARGV-1;splice@o,$_,0,splice@o,$_-pop,1for reverse@p

Выход заканчивается в массиве @o. Пример с входным массивом в качестве аргументов командной строки:

perl -le'@o=@p=0..@ARGV-1;splice@o,$_,0,splice@o,$_-pop,1for reverse@p;print@o' 0 1 1 2 1 0
402135

Рубин, 49 байтов

->l{(w=l.size).times{l.insert(l.shift+w-=1,w)};l}

Выполняет «обратную вставку» внутри списка, начиная с наибольшего числа.