Sumário

Dada uma lista de números inteiros, retorne o índice em que cada número inteiro terminaria ao ser classificado.

Por exemplo, se a lista estivesse [0,8,-1,5,8], você deveria retornar [1,3,0,2,4]. Observe que os dois 8s mantêm sua ordem em relação um ao outro (a classificação é estável).

Em outras palavras: para cada elemento da lista, retorne o número de elementos na lista que são: Menor que o elemento escolhido OR (igual ao elemento AND aparece antes do elemento escolhido)

Os índices devem começar com 0 (não 1) EDIT: dada a grande recuo, permitirei indicações baseadas em 1.

Casos de teste:

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 bytes

⍋⍋

O "nivelamento" interno, aplicado duas vezes. Funciona se a indexação começar em 0, o que não é o padrão para todos os tipos de APL. Experimente aqui!

Por que isso funciona?

⍋xretorna uma lista de índices que seriam classificados de forma estávelx . Por exemplo:

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

porque se você pegar o elemento 2, 6então 3... você recebe uma lista classificada de forma estável:

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

Mas a lista de índices que responde a essa pergunta é sutilmente diferente: primeiro queremos o índice do menor elemento, depois o segundo menor etc. - novamente, mantendo a ordem original.

Se observarmos ⍋x, porém, veremos que ela pode nos fornecer essa lista facilmente: a posição de um 0in ⍋xnos diz onde o menor elemento terminaria após a classificação e a posição de 1in ⍋xnos diz onde o segundo menor elemento acabaria etc.

Mas sabemos que ⍋xcontém exatamente os números [0, 1 ... n-1] . Se a classificarmos novamente , obteremos apenas o índice de 0in ⍋x, o índice de 1in ⍋x, etc., e é exatamente nisso que estamos interessados.

Então a resposta é ⍋⍋x.

Geléia, 2 bytes

ỤỤ

Classifique duas vezes. 1 indexado. Experimente online!

JavaScript ES6, 87 82 79 74 70 bytes

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

Não gosto de usar um objeto, mas parece ser a maneira mais curta de rastrear os enganos

Explicação

(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 bytes

<<

Classifique ( <) duas vezes. JohnE salvou três bytes apontando expressões tácitas existentes no K! Muito legal. Experimente.

Haskell, 50 48 bytes

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

Exemplo de uso: m.m $ [4,4,0,1,1,2,0,1] -> [6,7,0,2,3,5,1,4].

Está map snd.sort.zip x [0..] aplicado duas vezes na entrada, ou seja, emparelhe cada elemento e com seu índice i ( (e,i)), classifique-o e remova os primeiros elementos. Repita uma vez.

O @Lynn surgiu com m=map snd.sort.(`zip`[0..])a mesma contagem de bytes.

Python 2, 67 60 bytes

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

Graças a @xnor por jogar fora 7 bytes!

Teste em Ideone .

PowerShell v2 +, 63 bytes

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

Recebe entrada $n, canaliza através de um loop sobre todos os elementos |%{...}. A cada iteração, sort $nobtemos o IndexOfelemento atual $_. Isso conta quantos itens são menores que o elemento atual. Adicionamos a isso uma fatia de $n, que expande toda iteração de loop, dos elementos que são iguais ao elemento atual $_e retira o valor .Countdisso. Em seguida, subtraímos -1para não contar nosso elemento atual e esse número é deixado no pipeline. A saída no final está implícita.

Exemplos

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 bytes

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

Experimente online!

Explicação

{             }       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 bytes

/:^:2

Classifique ( /:) duas vezes ( ^:2). Indexado a 0.

Para testá-lo, digite f =: /:^:2e, em seguida, f 4 4 0 1 1 2 0 1em tryj.tk .

MATL, 10 9 4 bytes

4 bytes salvos graças a @Luis

&S&S

Esta solução usa indexação baseada em 1

Experimente Online

05AB1E, 12 bytes

2FvyN‚}){€¦˜

Explicado

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

Experimente online

Python 2, 67 bytes

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

O xnor salvou dois bytes.

Haskell, 40 bytes

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

Anote cada elemento com seu índice e, em seguida, mapeie cada elemento para a contagem de elementos menores, com desempate no índice. Sem classificação.

Julia, 17 bytes

~=sortperm;!x=~~x

1 indexado. Classifique ( sortperm) duas vezes. Experimente aqui.

Edição: Dennis salvou quatro bytes, dando nomes de operador-y coisas! Julia é estranha.

JavaScript (ES6), 52 bytes

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

Define gcomo a função de classificação, que retorna uma matriz de índices da qual todos os elementos na matriz classificada teriam vindo na matriz original. Infelizmente, o que queremos são os índices para os quais todos os elementos irão. Felizmente, isso acaba sendo o mapeamento da nota para a lista original de índices, que por si só pode ser considerado o resultado da classificação da nota, o que nos permite tirar a nota da nota para alcançar o resultado desejado.

Pitão, 10 9 bytes

1 byte graças a Jakube.

xLo@QNUQU

Suíte de teste.

Não deve ser um caminho mais curto ...

Raquete, 117 bytes

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

Estou eternamente decepcionado com a falta de uma base para isso.

Ruby, 54 53 bytes

Experimente online

-1 byte da atualização para a abordagem do @ Downgoat de usar um hash para armazenar valores em vez de contar as duplicatas a cada vez.

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

Clojure, 83 bytes

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

I create an anonymous function that grades the input array up and iterate it twice on the input. The first call will return the grade. The second call operates on the grade and returns the rank.

Brachylog, 27 bytes

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

Try it online! or verify all test cases.

Explanation

This is a straightforward implementation of the following relationship: each integer of the output corresponding to an element of the input is the index of that element in the sorted input.

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 bytes

(o=Ordering)@*o

Mathematica, 135 bytes

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

Common Lisp, 117 bytes

(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))))

Apply a Schwartzian transform twice.

;; 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 (using external library) (105 bytes)

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

Link to lib: https://github.com/mvegh1/Enumerable Explanation of code: Create anonymous method that accepts a list of integers. _.From creates an instance of the library that wraps an array with special methods. Select maps each item to a new item, by taking the "v"alue, parsing it to a string, then concatenating the "i"ndex of that item (this solves duplicate value case). Thats stored in variable 'a'. Then we return the result of the following: Map each item in 'a' to the index of that item in the sorted version of a (as integers), and cast back to a native JS array

Note that negative duplicate numbers seem to print in the reverse order. I'm not sure if that invalidates this solution? Technically 8,10,4,-1,-1,8 should be 3,5,2,0,1,4 according to OP but my code is printing 3,5,2,1,0,4 which I believe is still technically valid?

GNU Core Utils, 39 33 bytes

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

Produces 1-based output. Add -v0 after the second nl to get 0-based output. (+4 bytes)

Commands we are using:

• nl adds line numbers to each line of the input.
• sort -n -k 2 sorts by column 2 numerically.
• cut -f 1 takes the first Tab-delimited column, discarding the rest.

Além disso, a -sopção pode ser passada para sortsolicitar uma classificação estável, mas não precisamos dela aqui. Se dois itens forem idênticos, sortdeterminará sua ordem voltando para as outras colunas, que neste caso é a saída monotonicamente crescente de nl. Portanto, a classificação será estável sem precisar especificá-la, em virtude da entrada.

Java 149 140 bytes

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;
}

Golfe

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;}

Obrigado a @ Kevin Cruissjen pelo corte de 9 bytes.

PHP, 88 bytes

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

operates on command line arguments; prints 0-indexed, underscore-separated list. Run with -nr.

breakdown

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 bytes

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

Most of MATLAB's sorting built-ins will return an optional second array containing the sorted indices. The j= could be removed if printing the indices is acceptable, rather than returning them.

CJam, 19 bytes

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

Try it online!

Explanation:

_ 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