Sortowanie z odwrotnym wstawieniem

19

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 , więc wygrywa najkrótsza odpowiedź.

Pręt
źródło
1
Czy program może również przyjmować długość listy jako dane wejściowe?
mbomb007
@ mbomb007 nope.
Rod
Czy zamiast tego możemy użyć kroków (n-1)? Pierwszy jest niepotrzebny, ponieważ zawsze wynosi zero.
GB
@ GB na pewno, dopóki dane wyjściowe są prawidłowe, możesz użyć dowolnego algorytmu
Rod

Odpowiedzi:

14

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!


źródło
4
O_O Co to za czary ?
DLosc
Och, fajnie - wiedziałem, że moje Æ¡i œ?atomy na to zadziałają (już wcześniej próbowałem wykorzystać je do tego wyzwania - byłem tak blisko, potrzebowałem tylko L!tam).
Jonathan Allan
Doskonały kod!
Greg Martin
1
W rzeczywistości możesz to zrobić w 9 bajtach, UÆ¡Nœ?L’Uponieważ zaimplementowałem œ?(i podobnie), aby działać modułowo (tak jakby korzystały z list Jelly). W Nzaledwie w indeksy z wartością ujemną. Uwaga: Zmieniłem Jna L- to tylko dlatego, że podany numer i tak sprawia, że ​​zasięg jest pod maską).
Jonathan Allan
6

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.

Greg Martin
źródło
1
Co nie ma wbudowanego ?! Na pewno ...
Jonathan Allan
3
@{#}&)@{}©##&@@wygląda strasznie.
Yytsi
6

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

ćpun matematyki
źródło
2
Zrób to 66 ! Jak o: a=input();b=range(len(a));print[b.pop(j-a[j]) for j in b[::-1]][::-1]. Zrób listę ftw!
FMaz
1
@Krazor Masz miejsce, które można było wcześniej usunąć for, więc zrób 65 Myślę, że: D
Yytsi
@Krazor Okazuje się, że zrozumienie listy nie do końca działało, ale podobał mi się pomysł użycia b [:: - 1]!
ćpun matematyki
Nie ma mowy? Komentowałem za pomocą telefonu komórkowego, może coś pomyliłem. Która część nie działa? Dla mnie poprawnie zinterpretował i spełnił wszystkie przypadki testowe.
FMaz
@Krazor Oh, ups, nie masz racji. To ja pomyliłem go podczas testowania.
ćpun matematyki
5

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.

Neil
źródło
Wciąż próbowałem znaleźć lepszy sposób, ale byłeś znacznie szybszy. Niezłe!
Arnauld
1
Nie potrzebujesz i, prawda?
Arnauld
@Arnauld Najwyraźniej nie. Zacząłem od próby zrozumienia odpowiedzi w języku Python i właśnie zauważyłem, że tak naprawdę nie używa i...
Neil
1
Łatwe -2:o=>+b.splice(~o,1)
ETHprodukcje
3

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

Arnauld
źródło
Fajny sposób na uzyskanie długości i zasięgu w tym samym czasie. Miałem zasugerować a=m.map(_=>j++,j=0), ale to ta sama długość i jestem pewien, że już próbowałeś.
ETHprodukcje
@ETHproductions Masz rację: próbowałem również. :-) (Warto zauważyć, że nie jest to równoważne: ustawiłoby jto a.lengthraczej na a.length-1i wymagałoby a.splice(--j,0,a.splice(j-m[j],1)[0]))
Arnauld
Heh, też o tym myślałem, ale nie sądziłem, że warto o tym wspomnieć, ponieważ ma taką samą długość
ETHproductions
1
Łatwe -2:+a.splice(j-m[j--],1)
ETHprodukcje
2

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.

Laikoni
źródło
Haskell, taki piękny.
FMaz
1

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
Kjetil S.
źródło
1

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.

GB
źródło