Cel

Wygeneruj oryginalną zaszyfrowaną listę na podstawie ruchów, które wykonałby Sortowanie wstawiania , aby ją posortować. Oryginalna lista będzie zawierać wszystkie liczby od 0do N-1(włącznie), gdzie Njest rozmiar danych wejściowych.

Wejście

Lista zawierająca niezbędne ruchy do posortowania listy. Każda wartość reprezentuje liczbę miejsc przesuniętych przez pierwotną (zaszyfrowaną) liczbę, aby znalazły się na swojej właściwej pozycji, pamiętaj, że ten proces odbywa się od lewej do prawej.
Wartość w pozycji (indeksowanej 0) ina liście danych wejściowych będzie pomiędzy 0i iwłącznie.
Nie musisz obsługiwać nieprawidłowych danych wejściowych, w tym przypadku dopuszczalne jest dowolne zachowanie (awaria, nieskończona pętla itp.).

Wynik

Zakodowana lista

Krok po kroku, aby wygenerować ruchy

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]

Tak więc dla danych wejściowych [0,1,1,2,1,0]twój program musi generować dane wyjściowe [4,0,2,1,3,5].
Pamiętaj, że ruchy nie są w pozycji na (końcowej) posortowanej liście, ale w posortowanym segmencie (pogrubiona sekcja)

Przypadki testowe

[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]

Zwycięski

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź.

Galaretka , 12 bajtów

L!_UÆ¡$œ?J’U

Wypróbuj online!

Wyjaśnienie

Zasadniczo możemy zobaczyć dwie listy (wejściową i wyjściową) jako kodujące liczbę całkowitą; wejście koduje liczbę całkowitą w podstawie silni, a wyjście koduje liczbę całkowitą jako permutację. Na szczęście Jelly ma wbudowane funkcje, które są już bardzo zbliżone do obu tych kodowań, więc wystarczy napisać małe fragmenty kodu, aby przekonwertować je na liczbę całkowitą, a następnie z powrotem na inne kodowanie.

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

W przypadku podstawowej silni możemy zaobserwować, że pierwszy element listy musi wynosić 0, drugi może wynosić 0 lub 1, trzeci musi wynosić 0/1/2 i tak dalej. Dlatego musimy odwrócić dane wejściowe, aby wprowadzić elementy do normalnej kolejności zapisu dla konwersji podstawowej.

Ponadto, aby względne porządki konwersji czynnikowej i konwersji permutacji były zgodne z operacją stosowaną przez sortowanie przy wstawianiu, musimy dokonać dwóch korekt: odwrócić sekwencję permutacji i odwrócić kolejność listy wyników. Odwrócenie listy wyników jest dość łatwe, wymaga tylko Ukońca programu. Aby odwrócić sekwencję permutacji, odejmujemy od silni długości wejściowej (działa to, ponieważ silnia podstawowa daje liczbę w zakresie od 0 do (długość! -1), podczas gdy permutacje są ponumerowane przez galaretkę od 1 do długości! , generując niejawne rozwiązanie off-by-one, które anuluje działanie off-by-one, które normalnie uzyskuje się po odjęciu indeksu permutacji od silni).

Galaretka , 9 bajtów, we współpracy z @JonathanAllan

UÆ¡Nœ?J’U

Ta wersja programu jest bardzo podobna, ale wykorzystuje inną metodę odwracania sekwencji permutacji; wystarczy po prostu zanegować dane wejściowe za pomocą N, aby wykonać œ?kolejność w odwrotnej kolejności. Poza tym działa identycznie jak w poprzednim programie.

Wypróbuj online!

Mathematica, 92 bajty

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

Czysta funkcja przyjmuje na wejściu listę nieujemnych liczb całkowitych i zwraca listę nieujemnych liczb całkowitych. Powyższy kod zawiera ©niepoprawny: jest to symbol zastępczy 3-bajtowego symbolu U + F3DE, który Mathematica reprezentuje okręgiem z kropką, i który reprezentuje układ permutacji.

c=Cycles@{#}&definiuje funkcję, która konwertuje listę liczb całkowitych na Cyclesobiekt reprezentujący permutację; na przykład c[{3,4}]to elementy zamiany transpozycji 3 i 4 listy. c[i-0~Range~#[[i]]]~Table~{i,l,1,-1}]pobiera listę danych wejściowych i generuje permutacje niezbędne do cofnięcia sortowania wstawiania. Następnie c@{}©##&@@składa wszystkie te permutacje razem, zaczynając od permutacji tożsamości c@{}. Na koniec Permute[Range[l=Length@#]-1,...]stosuje tę permutację do zindeksowanej listy o odpowiedniej długości.

Python 2, 79 68 bajtów

Dzięki Krazorowi za zaoszczędzenie 10 bajtów

Dzięki TuukkaX za zapisanie 1 bajtu

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

Działa poprzez generowanie ruchów w odwrotnej kolejności

JavaScript (ES6), 69 65 63 bajtów

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

Irytujące jest to, że dane wejściowe i wyjściowe są w niewłaściwej kolejności. Edycja: Zapisano 4 bajty dzięki @Arnauld. Zaoszczędź 2 bajty dzięki @ETHproductions.

JavaScript (ES6), 73 71 bajtów

Zaoszczędzono 2 bajty dzięki produktom ETH

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

Przypadki testowe

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 bajtów

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

Wypróbuj online! Przykładowe użycie: f [0,1,1,2,1,0]daje [4,0,2,1,3,5].

f xwywołuje funkcję #z xodwróconą listą i listą [length x - 1, length x - 2, ... , 0]. (n:r)#lwykonuje sortowanie z odwrotnym wstawieniem, rekurencyjnie wyjmując nelement th z l, gdzie l!!nzwraca nelement th i take n l++drop(n+1)lzwraca listę lz nusuniętym elementem th.

perl, 61 bajtów

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

Dane wyjściowe kończą się w tablicy @o. Przykład z tablicą wejściową jako argumentami wiersza poleceń:

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

Ruby, 49 bajtów

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

Wykonuje „wstawianie wsteczne” w miejscu na liście, zaczynając od największej liczby.