Podsumowanie

Biorąc pod uwagę listę liczb całkowitych, zwróć indeks, na którym kończą się liczby całkowite podczas sortowania.

Na przykład, jeśli lista była [0,8,-1,5,8], powinieneś powrócić [1,3,0,2,4]. Zauważ, że dwa 8zachowują swoją kolejność względem siebie (sortowanie jest stabilne).

Innymi słowy: dla każdego elementu na liście zwróć liczbę elementów na liście, które są: Mniejsze niż wybrany element LUB (równe elementowi AND pojawia się przed wybranym elementem)

Indeksy muszą zaczynać się od 0 (nie 1) EDYCJA: biorąc pod uwagę duży zwrot, pozwolę na wskazania oparte na 1.

Przypadki testowe:

0                -> 0
23               -> 0
2,3              -> 0,1
3,2              -> 1,0
2,2              -> 0,1
8,10,4,-1,-1,8   -> 3,5,2,0,1,4
0,1,2,3,4,5,6,7  -> 0,1,2,3,4,5,6,7
7,6,5,4,3,2,1,0  -> 7,6,5,4,3,2,1,0
4,4,0,1,1,2,0,1  -> 6,7,0,2,3,5,1,4
1,1,1,1,1,1,1,1  -> 0,1,2,3,4,5,6,7
1,1,1,1,1,1,1,0  -> 1,2,3,4,5,6,7,0

APL, 2 bajty

⍋⍋

Wbudowane „podwyższenie oceny” zastosowano dwukrotnie. Działa, jeśli indeksowanie rozpoczyna się od 0, co nie jest wartością domyślną dla wszystkich odmian APL. Wypróbuj tutaj!

Dlaczego to działa?

⍋xzwraca listę indeksów, które byłyby stabilnie sortowanex . Na przykład:

    x ← 4 4 0 1 1 2 0 1
    ⍋x
2 6 3 4 7 5 0 1

ponieważ jeśli weźmiesz element 2, 6wtedy 3… otrzymasz stabilnie posortowaną listę:

    x[⍋x]
0 0 1 1 1 2 4 4

Ale lista indeksów, która odpowiada na to pytanie, jest nieco inna: najpierw chcemy indeksu najmniejszego elementu, potem drugiego najmniejszego itd. - znowu, zachowując pierwotną kolejność.

Jeśli przyjrzymy się ⍋x, chociaż widzimy, może dać nam tę listę łatwo: the pozycja z 0IN ⍋xmówi nam, gdzie najmniejszy element będzie kończyć się po sortowaniu, a pozycja o 1in ⍋xmówi nam, gdzie drugi najmniejszy element byłoby skończyć itd.

Ale wiemy, że ⍋xzawiera dokładnie liczby [0, 1… n − 1] . Jeśli ponownie go ocenimy , otrzymamy indeks 0in ⍋x, następnie indeks 1in ⍋xitp., Czyli dokładnie to, czym jesteśmy zainteresowani.

Tak więc odpowiedź brzmi ⍋⍋x.

Galaretka, 2 bajty

ỤỤ

Oceń dwa razy. 1-indeksowany. Wypróbuj online!

JavaScript ES6, 87 82 79 74 70 bajtów

(a,b={})=>a.map(l=>[...a].sort((a,b)=>a-b).indexOf(l)+(b[l]=b[l]+1|0))

Nie lubisz używać obiektu, ale wydaje się, że jest to najkrótszy sposób śledzenia kopii

Wyjaśnienie

(a,b={})=>          `a` is input
                    `b` stores the occurrences of each number
  a.map(l =>        Loop over the array, `l` is item
  [...a]            Copy `a`
    .sort(...)       Sort in ascending numerical order
    .indexOf(l)      Index of input in that array
  +                 Add the following to account for dupes
   (b[l]=            set and return the item `l` in hashmap `b` to...
     b[l]+1           Increase the counter by one if it exists yet
     |0               default is zero
   )

K , 5 2 bajty

<<

Oceń <dwa razy ( ). JohnE zapisał trzy bajty, wskazując, że ukryte wyrażenia istnieją w K! Super fajne. Wypróbuj to.

Haskell, 50 48 bajtów

import Data.List
m x=map snd$sort$zip x[0..]
m.m

Przykład użycia: m.m $ [4,4,0,1,1,2,0,1]-> [6,7,0,2,3,5,1,4].

Stosuje się go map snd.sort.zip x [0..]dwukrotnie na wejściu, tj. Sparuj każdy element ez jego indeksem i ( (e,i)), posortuj, aby usunąć pierwsze elementy. Powtórz jeden raz.

@Lynn wymyślił, m=map snd.sort.(`zip`[0..])który ma taką samą liczbę bajtów.

Python 2, 67 60 bajtów

def f(x):x=zip(x,range(len(x)));print map(sorted(x).index,x)

Dzięki @xnor za grę w golfa z 7 bajtów!

Przetestuj na Ideone .

PowerShell v2 +, 63 bajty

param($n)$n|%{($n|sort).IndexOf($_)+($n[0..$i++]-eq$_).count-1}

Pobiera dane wejściowe $n, przepływa przez pętlę nad każdym elementem |%{...}. Z każdą iteracją sort $notrzymujemy IndexOfnasz aktualny element $_. Zlicza to, ile elementów jest mniejszych niż bieżący element. Dodajemy do tego kawałek $n, który rozszerza każdą iterację pętli, elementów równych bieżącemu elementowi $_i przyjmujemy .Countto. Następnie odejmujemy, -1aby nie liczyć naszego bieżącego elementu, a liczba ta pozostaje w kolejce. Wynik końcowy jest niejawny.

Przykłady

PS C:\Tools\Scripts\golfing> .\ordering-a-list.ps1 @(4,4,0,1,1,2,0,1)
6
7
0
2
3
5
1
4

PS C:\Tools\Scripts\golfing> .\ordering-a-list.ps1 @(8,10,4,-1,-1)
3
4
2
0
1

CJam, 15 bajtów

{{eeWf%$1f=}2*}

Wypróbuj online!

Wyjaśnienie

{             }       Delimits an anonymous block.
 {         }2*        Run this block on the argument twice:
  ee                  Enumerate ([A B C] → [[0 A] [1 B] [2 C]])
    Wf%               Reverse each ([[A 0] [B 1] [C 2]])
       $              Sort the pairs lexicographically;
                        i.e. first by value, then by index.
        1f=           Keep the indices.

J, 5 bajtów

/:^:2

Ocena w górę ( /:) dwa razy ( ^:2). 0-indeksowane.

Aby go wypróbować, typ f =: /:^:2, a następnie f 4 4 0 1 1 2 0 1do tryj.tk .

MATL, 10 9 4 bajtów

4 bajty zapisane dzięki @Luis

&S&S

To rozwiązanie wykorzystuje indeksowanie 1

Wypróbuj online

05AB1E, 12 bajtów

2FvyN‚}){€¦˜

Wyjaśnił

2F            # 2 times do
  vyN‚})      # create list of [n, index]-pairs
        {€¦   # sort and remove first element leaving the index
           ˜  # deep flatten
              # implicit output

Wypróbuj online

Python 2, 67 bajtów

a=input()
p=[]
for x in a:print sorted(a).index(x)+p.count(x);p+=x,

xnor zapisał dwa bajty.

Haskell, 40 bajtów

f l|z<-zip l[0..]=[sum[1|y<-z,y<x]|x<-z]

Adnotuj każdy element za pomocą indeksu, a następnie przypisz każdy element do liczby mniejszych elementów, przerywając remis w indeksie. Bez sortowania.

Julia, 17 bajtów

~=sortperm;!x=~~x

1-indeksowany. Oceń sortpermdwa razy ( ). Wypróbuj tutaj.

EDYCJA: Dennis zapisał cztery bajty, nadając operatorowi nazwy-y! Julia jest dziwna.

JavaScript (ES6), 52 bajty

a=>(g=a=>[...a.keys()].sort((n,m)=>a[n]-a[m]))(g(a))

Definiuje gjako funkcję gradacji, która zwraca tablicę indeksów, z której wszystkie elementy w sortowanej tablicy pochodziłyby z oryginalnej tablicy. Niestety, potrzebujemy wskaźników, do których trafią wszystkie elementy. Na szczęście okazuje się, że jest to odwzorowanie oceny z powrotem na pierwotną listę indeksów, co samo w sobie może być uważane za wynik sortowania oceny, co pozwala nam na ocenę oceny w celu osiągnięcia pożądanego wyniku.

Pyth, 10 9 bajtów

1 bajt dzięki Jakube.

xLo@QNUQU

Zestaw testowy.

Tam musi być krótsza droga ...

Rakieta, 117 bajtów

(λ(x)(build-list(length x)(λ(h)((λ(y)(+(count(λ(z)(< z y))x)(count(λ(z)(eq? z y))(take x h))))(list-ref x h)))))

Jestem wiecznie rozczarowany brakiem wbudowanego do tego celu.

Rubin, 54 53 bajtów

Wypróbuj online

-1 bajt od aktualizacji do @ Downgoat podejścia polegającego na użyciu skrótu do przechowywania wartości zamiast liczenia duplikatów za każdym razem.

->a{b={};a.map{|e|a.sort.index(e)+b[e]=(b[e]||-1)+1}}

Clojure, 83 bajty

(fn[a](nth(iterate #(->> %(map-indexed(comp vec rseq vector))sort(map second))a)2))

Tworzę anonimową funkcję, która ocenia tablicę wejściową w górę i iteruje ją dwukrotnie na wejściu. Pierwsze połączenie zwróci ocenę. Drugie połączenie działa na ocenę i zwraca rangę.

Brachylog , 27 bajtów

lL-M,?og:MjO,L~l.#d:Orz:ma?

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Wyjaśnienie

Jest to prosta implementacja następującej zależności: każda liczba całkowita wyniku odpowiadająca elementowi wejścia jest indeksem tego elementu w posortowanym wejściu.

Example input: [3:2]

lL               L is the length of the input (e.g L=2)
  -M,            M = L-1 (e.g. M=1)
?o               Sort the input...
  g:MjO,         ... and create a list O with L copies of the input (e.g. O=[[2:3]:[2:3]])
L~l.             Output is a list of length L (e.g. [I:J])
    #d           All elements of the output must be distinct (e.g. I≠J)
      :Orz       Zip O with the output (e.g. [[[2:3]:I]:[[2:3]:J]])
          :ma?   Apply predicate Member with that zip as input and the input as output
                 (e.g. 3 is the Ith element of [2:3] and 2 is the Jth element of [2:3])

Mathematica, 15 bajtów

(o=Ordering)@*o

Mathematica, 135 bajtów

Function[{list}, SortBy[MapIndexed[Join[{#1}, #2]&, Sort@MapIndexed[Join[{#1}, #2] &, list]], #[[1, 2]] &][[All, 2]] - 1]

Common Lisp, 117 bajtów

(flet((i(Z)(mapcar'cdr(stable-sort(loop for e in Z for x from 0 collect(cons e x))'< :key'car))))(lambda(L)(i(i L))))

Zastosuj transformację Schwartziana dwa razy.

;; FIRST TIME

(0 8 -1 5 8)
;; add indexes
((0 . 0) (8 . 1) (-1 . 2) (5 . 3) (8 . 4))
;; sort by first element
((-1 . 2) (0 . 0) (5 . 3) (8 . 1) (8 . 4))
;; extract second elements
(2 0 3 1 4)

;; SECOND TIME

(2 0 3 1 4)
;; indexes
((2 . 0) (0 . 1) (3 . 2) (1 . 3) (4 . 4))
;; sort by first element
((0 . 1) (1 . 3) (2 . 0) (3 . 2) (4 . 4))
;; extract second elements
(1 3 0 2 4)

Test

(let ((fn (flet((i(Z)(mapcar'cdr(stable-sort(loop for e in Z for x from 0 collect(cons e x))'< :key'car))))(lambda(L)(i(i L))))))
  (every
   (lambda (test expected)
     (equal (funcall fn test) expected))

   '((0) (23) (2 3) (3 2) (2 2) (8 10 4 -1 -1 8) (0 1 2 3 4 5 6 7)
     (7 6 5 4 3 2 1 0) (4 4 0 1 1 2 0 1) (1 1 1 1 1 1 1 1) (1 1 1 1 1 1 1 0))

   '((0) (0) (0 1) (1 0) (0 1) (3 5 2 0 1 4) (0 1 2 3 4 5 6 7) (7 6 5 4 3 2 1 0)
     (6 7 0 2 3 5 1 4) (0 1 2 3 4 5 6 7) (1 2 3 4 5 6 7 0))))
=> T

JavaScript (przy użyciu zewnętrznej biblioteki) (105 bajtów)

(n)=>{var a=_.From(n).Select((v,i)=>v+""+i);return a.Select(x=>a.OrderBy(y=>(y|0)).IndexOf(x)).ToArray()}

Link do lib: https://github.com/mvegh1/Enumerable Objaśnienie kodu: Utwórz anonimową metodę, która akceptuje listę liczb całkowitych. _.From tworzy instancję biblioteki, która otacza tablicę specjalnymi metodami. Wybierz mapuje każdy element na nowy element, biorąc alue „v”, analizując go do łańcucha, a następnie łącząc indeks „i” tego elementu (rozwiązuje to przypadek zduplikowanej wartości). To jest przechowywane w zmiennej „a”. Następnie zwracamy wynik: Zamapuj każdy element w „a” na indeks tego elementu w posortowanej wersji (jako liczby całkowite) i rzutuj z powrotem na natywną tablicę JS

Zauważ, że zduplikowane liczby ujemne wydają się drukować w odwrotnej kolejności. Nie jestem pewien, czy to unieważnia to rozwiązanie? Technicznie 8,10,4, -1, -1,8 powinno wynosić 3,5,2,0,1,4 zgodnie z OP, ale mój kod drukuje 3,5,2,1,0,4, który moim zdaniem jest nadal technicznie ważne?

GNU Core Utils, 39 33 bajtów

nl|sort -nk2|nl|sort -nk2|cut -f1

Tworzy dane wyjściowe na podstawie 1. Dodaj -v0po drugim, nlaby uzyskać wyjście oparte na 0. (+4 bajty)

Polecenia, których używamy:

• nl dodaje numery linii do każdej linii wejścia.
• sort -n -k 2 sortuje według kolumny 2 numerycznie.
• cut -f 1 pobiera pierwszą kolumnę rozdzielaną tabulatorami, odrzucając resztę.

Dodatkowo -smożna przekazać opcję sortżądania stabilnego sortowania, ale tutaj jej nie potrzebujemy. Jeśli dwa elementy są identyczne, sortokreśli ich kolejność, wracając do innych kolumn, co w tym przypadku jest monotonicznie rosnącą wydajnością nl. Tak więc sortowanie będzie stabilne bez konieczności określania go na podstawie danych wejściowych.

Java 149 140 bajtów

public int[] indexArray(int[] index){
  int[] out=new int[index.length];
  for(int i=-1;++i<index.length;){
    for(int j=-1;++i<index.length;){
      if(index[i]==Arrays.sort(index.clone())[j]){
        out[i]=j;
      }
    }
  }
  return out;
}

Grał w golfa

int[]a(int[]b){int l=b.length;int[]o=new int[l];for(int i=-1;++i<l;)for(int j=-1;++i<l;)if(b[i]==Arrays.sort(b.clone())[j])o[i]=j;return o;}

Dzięki @Kevin Cruissjen za golenie 9 bajtów.

PHP, 88 bajtów

unset($argv[0]);$a=$argv;sort($a);foreach($argv as$e)echo$h[$e]+++array_search($e,$a),_;

działa na argumentach wiersza poleceń; wypisuje 0-indeksowaną listę rozdzieloną podkreśleniem. Uruchom z -nr.

awaria

unset($argv[0]);        // remove file name from arguments
$a=$argv;               // create copy
sort($a);               // sort copy (includes reindexing, starting with 0)
foreach($argv as$e)     // loop $e through original
    echo                    // print:
        $h[$e]++            // number of previous occurences
        +array_search($e,$a)// plus position in copy 
        ,_                  // followed by underscore
    ;

MATLAB, 29 bajtów

function j=f(s);[~,j]=sort(s)

Większość wbudowanych funkcji sortowania MATLAB zwróci opcjonalną drugą tablicę zawierającą posortowane indeksy. j=Mogą być usunięte, jeśli drukowanie indeksów jest dopuszczalne, zamiast ich powrocie.

CJam , 19 bajtów

_$:A;{A#_AWt:A;1+}%

Wypróbuj online!

Wyjaśnienie:

_ duplicate array
 $ sort array
  :A store in variable A
    ; discard top item in stack
     {A#_AWt:A;1+} block that finds index of item and removes it from sorted array to prevent duplicates
      % map block onto every item in array