Резюме

Получив список целых чисел, верните индекс, в котором каждое целое число будет в итоге при сортировке.

Например, если список был [0,8,-1,5,8], вы должны вернуться [1,3,0,2,4]. Обратите внимание, что эти два 8поддерживают свой порядок относительно друг друга (сортировка стабильна).

Другими словами: для каждого элемента в списке вернуть количество элементов в списке: Меньше, чем выбранный элемент ИЛИ (равный элементу И появляется перед выбранным элементом)

Индексы должны начинаться с 0 (не с 1) РЕДАКТИРОВАТЬ: учитывая большой откат, я позволю индикации на основе 1.

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

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 байта

⍋⍋

Встроенная оценка, применяется дважды. Работает, если индексирование начинается с 0, что не является значением по умолчанию для всех разновидностей APL. Попробуй это здесь!

Почему это работает?

⍋xвозвращает список индексов, которые будут стабильно сортироватьсяx . Например:

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

потому что если вы возьмете элемент 2, тогда ... 6тогда 3вы получите стабильно отсортированный список:

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

Но список индексов, который отвечает на этот вопрос, несколько отличается: сначала нам нужен индекс наименьшего элемента, затем второй наименьший и т. Д., Опять же, сохраняя первоначальный порядок.

Если мы посмотрим на ⍋x, хотя, мы видим , что может дать нам этот список легко: позиция из 0ин ⍋xговорит нам , где наименьший элемент будет в конечном итоге после сортировки, а также положение о 1ин ⍋xговорит нам , где второй наименьший элемент будет в конечном итоге , так далее.

Но мы знаем, что ⍋xсодержит именно числа [0, 1… n − 1] . Если мы снова оценим его , мы просто получим индекс 0in ⍋x, затем индекс 1in ⍋xи т. Д., И это именно то, что нас интересует.

Так что ответ ⍋⍋x.

Желе, 2 байта

ỤỤ

Оценить в два раза. 1-индексироваться. Попробуйте онлайн!

JavaScript ES6, 87 82 79 74 70 байт

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

Не люблю использовать объект, но это, кажется, самый короткий способ отследить обманщиков

объяснение

(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 байта

<<

Оценить ( <) в два раза. JohnE сохранил три байта, указав, что в K существуют неявные выражения! Очень круто. Попробуйте это.

Haskell, 50 48 байтов

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

Пример использования: m.m $ [4,4,0,1,1,2,0,1]-> [6,7,0,2,3,5,1,4].

Он map snd.sort.zip x [0..]применяется дважды на входе, т.е. соединяет каждый элемент e с его индексом i ( (e,i)), сортирует его, удаляя первые элементы. Повторите один раз.

@Lynn придумал, у m=map snd.sort.(`zip`[0..])которого есть то же самое число байтов.

Python 2, 67 60 байт

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

Спасибо @xnor за 7 байтов!

Проверьте это на Ideone .

PowerShell v2 +, 63 байта

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

Принимает ввод $n, передает это через цикл по каждому элементу |%{...}. На каждой итерации мы sort $nи получаем IndexOfнаш текущий элемент $_. Это подсчитывает, сколько элементов меньше, чем текущий элемент. Мы добавляем к этому кусочек $n, который расширяет каждую итерацию цикла, элементов, которые равны текущему элементу, $_и принимаем его .Count. Затем мы вычитаем, -1чтобы не считать наш текущий элемент, и это число остается в конвейере. Вывод в конце неявный.

Примеры

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 байтов

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

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

объяснение

{             }       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 байт

/:^:2

Оценить ( /:) в два раза ( ^:2). 0 индексированные.

Для того, чтобы попробовать его, типа , f =: /:^:2а затем f 4 4 0 1 1 2 0 1в tryj.tk .

MATL, 10 9 4 байта

4 байта сохранены благодаря @Luis

&S&S

В этом решении используется индексирование на основе 1

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

05AB1E, 12 байтов

2FvyN‚}){€¦˜

Разъяснения

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

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

Python 2, 67 байт

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

xnor сохранил два байта.

Haskell, 40 байт

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

Аннотируйте каждый элемент с его индексом, затем сопоставьте каждый элемент с количеством меньших элементов, разрывая связь по индексу. Нет сортировки.

Юлия, 17 байт

~=sortperm;!x=~~x

1-индексироваться. Оценить ( sortperm) в два раза. Попробуй это здесь.

РЕДАКТИРОВАТЬ: Деннис сэкономил четыре байта, давая имена операторов вещи! Юлия странная

JavaScript (ES6), 52 байта

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

Определяется gкак функция оценки, которая возвращает массив индексов, из которого все элементы в отсортированном массиве были бы взяты из исходного массива. К сожалению, нам нужны индексы, на которые пойдут все элементы. К счастью, это оказывается сопоставлением оценки с первоначальным списком показателей, который сам по себе можно считать результатом сортировки оценки, что позволяет нам получить оценку оценки для достижения желаемого результата.

Pyth, 10 9 байтов

1 байт благодаря Якубе.

xLo@QNUQU

Тестирование.

Там должна быть более коротким путем ...

Ракетка, 117 байт

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

Я вечно разочарован отсутствием встроенных средств для этого.

Рубин, 54 53 байта

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

-1 байт от обновления до подхода @ Downgoat - использование хеша для хранения значений вместо подсчета дубликатов каждый раз.

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

Clojure, 83 байта

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

Я создаю анонимную функцию, которая оценивает входной массив и повторяет его дважды на входе. Первый звонок вернет оценку. Второй вызов действует на оценку и возвращает рейтинг.

Брахилог , 27 байт

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

Попробуйте онлайн! или проверьте все контрольные примеры .

объяснение

Это простая реализация следующего отношения: каждое целое число выходных данных, соответствующее элементу входных данных, является индексом этого элемента в отсортированном входном файле.

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 байт

(o=Ordering)@*o

Mathematica, 135 байт

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

Common Lisp, 117 байт

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

Примените преобразование Шварца дважды.

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

Тест

(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 (с использованием внешней библиотеки) (105 байт)

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

Ссылка на lib: https://github.com/mvegh1/Enumerable Объяснение кода: Создайте анонимный метод, который принимает список целых чисел. _.From создает экземпляр библиотеки, которая упаковывает массив специальными методами. Select сопоставляет каждый элемент новому элементу, беря значение «v», анализируя его в строку, а затем конкатенируя «i» ndex этого элемента (это решает случай повторяющегося значения). Это хранится в переменной «а». Затем мы возвращаем результат следующего: сопоставить каждый элемент в 'a' с индексом этого элемента в отсортированной версии a (как целые числа) и привести обратно к собственному массиву JS

Обратите внимание, что отрицательные повторяющиеся числа печатаются в обратном порядке. Я не уверен, что это делает это решение недействительным? Технически 8,10,4, -1, -1,8 должны быть 3,5,2,0,1,4 в соответствии с OP, но мой код печатает 3,5,2,1,0,4, который я считаю все еще технически действительный?

GNU Core Utils, 39 33 байта

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

Производит вывод на основе 1. Добавить -v0после второгоnl чтобы получить 0 на основе вывода. (+4 байта)

Команды, которые мы используем:

• nl добавляет номера строк к каждой строке ввода.
• sort -n -k 2 сортирует по столбцу 2 численно.
• cut -f 1 занимает первый столбец с разделителями табуляции, отбрасывая остальные.

Кроме того, -sопция может быть передана для sortзапроса стабильной сортировки, но здесь она нам не нужна. Если два элемента идентичны, они sortбудут определять их порядок, возвращаясь к другим столбцам, что в данном случае является монотонно увеличивающимся выходом nl. Таким образом, сортировка будет стабильной без необходимости ее указания, благодаря вводу.

Java 149 140 байт

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

Golfed

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

Спасибо @Kevin Cruissjen за бритье 9 байтов.

PHP, 88 байт

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

оперирует аргументами командной строки; печатает 0-индексированный список, разделенный подчеркиванием. Беги с -nr.

сломать

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 байт

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

Большинство встроенных модулей сортировки MATLAB будут возвращать дополнительный второй массив, содержащий отсортированные индексы. Они j=могут быть удалены, если печать индексов приемлема, а не возвращать их.

CJam , 19 байтов

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

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

Объяснение:

_ 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