Zusammenfassung

Bei einer gegebenen Liste von Ganzzahlen geben Sie den Index zurück, bei dem jede Ganzzahl sortiert wird.

Wenn die Liste zum Beispiel war [0,8,-1,5,8], sollten Sie zurückkehren [1,3,0,2,4]. Beachten Sie, dass die beiden 8ihre Reihenfolge relativ zueinander beibehalten (die Sortierung ist stabil).

Anders ausgedrückt: Geben Sie für jedes Element in der Liste die Anzahl der Elemente in der Liste zurück: Kleiner als das ausgewählte Element ODER (gleich dem Element UND wird vor dem ausgewählten Element angezeigt)

Indizes müssen mit 0 (nicht mit 1) EDIT beginnen: Angesichts des großen Pushbacks erlaube ich 1-basierte Angaben.

Testfälle:

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

⍋⍋

Die eingebaute "Note up", angewendet zweimal. Funktioniert, wenn die Indizierung bei 0 beginnt. Dies ist nicht die Standardeinstellung für alle APL-Varianten. Probieren Sie es hier aus!

Warum funktioniert das?

⍋xGibt eine Liste von Indizes zurück, die stabil sortiert werden könnenx . Beispielsweise:

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

denn wenn Sie Element nehmen 2, dann 6, dann 3... Sie eine stabil sortierte Liste erhalten:

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

Die Indexliste, die diese Frage beantwortet, unterscheidet sich jedoch geringfügig: Zuerst möchten wir den Index des kleinsten Elements, dann des zweitkleinsten usw. - wieder unter Beibehaltung der ursprünglichen Reihenfolge.

Wenn wir uns anschauen ⍋x, aber sehen wir es uns diese Liste leicht geben kann: die Position eines 0in ⍋xmir sagt , wo das kleinste Element nach dem Sortieren enden würde, und die Position eines 1in ⍋xsagt uns , wo das zweitkleinste Element würde am Ende , etc.

Aber wir wissen, ⍋xenthält genau die Zahlen [0, 1… n − 1] . Wenn wir es erneut bewerten, erhalten wir nur den Index von 0in ⍋x, dann den Index von 1in ⍋xusw., und genau das ist es, woran wir interessiert sind.

Die Antwort lautet also ⍋⍋x.

Gelee, 2 Bytes

ỤỤ

Steige zweimal auf. 1-indiziert. Probieren Sie es 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))

Ich mag es nicht, ein Objekt zu benutzen, aber es scheint der kürzeste Weg zu sein, Dupes zu verfolgen

Erläuterung

(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

<<

Benote ( <) zweimal. JohnE sparte drei Bytes, indem er auf implizite Ausdrücke in K hinwies! Super cool. Versuch es.

Haskell, 50 48 Bytes

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

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

Es map snd.sort.zip x [0..]wird zweimal auf die Eingabe angewendet, dh jedes Element e wird mit seinem Index i ( (e,i)) gepaart, und die ersten Elemente werden entfernt. Einmal wiederholen.

@Lynn m=map snd.sort.(`zip`[0..])hat die gleiche Byteanzahl gefunden .

Python 2, 67 60 Bytes

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

Vielen Dank an @xnor für das Golfen mit 7 Bytes!

Teste es auf Ideone .

PowerShell v2 +, 63 Byte

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

Übernimmt Eingaben $n, leitet diese durch eine Schleife über jedes Element |%{...}. Jede Iteration, wir sort $nund erhalten die in IndexOfunserem aktuellen Element $_. Dies zählt, wie viele Elemente kleiner als das aktuelle Element sind. Wir fügen dem ein Stück hinzu $n, das jede Schleifeniteration der Elemente erweitert, die gleich dem aktuellen Element sind$_ und nehmen das .Countdavon. Wir subtrahieren -1dann, um unser aktuelles Element nicht zu zählen, und diese Zahl verbleibt in der Pipeline. Die Ausgabe am Ende ist implizit.

Beispiele

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

Probieren Sie es online!

Erläuterung

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

/:Zweimal benoten ( ) (^:2 ). 0-indiziert.

Probieren Sie es aus, geben f =: /:^:2und dann f 4 4 0 1 1 2 0 1in tryj.tk .

MATL, 10 9 4 Bytes

4 Bytes gespart dank @Luis

&S&S

Diese Lösung verwendet eine 1-basierte Indizierung

Probieren Sie es online

05AB1E, 12 Bytes

2FvyN‚}){€¦˜

Erklärt

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

Probieren Sie es online aus

Python 2, 67 Bytes

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

xnor sparte zwei Bytes.

Haskell, 40 Bytes

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

Beschriften Sie jedes Element mit seinem Index, und ordnen Sie dann jedes Element der Anzahl kleinerer Elemente zu. Keine Sortierung.

Julia, 17 Bytes

~=sortperm;!x=~~x

1-indiziert. Benote ( sortperm) zweimal. Probieren Sie es hier aus.

BEARBEITEN: Dennis hat vier Bytes gespart, indem er die Namen der Benutzer angegeben hat! Julia ist komisch.

JavaScript (ES6), 52 Byte

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

Definiert gals Klassenfunktion, die ein Array von Indizes zurückgibt, von denen alle Elemente im sortierten Array im ursprünglichen Array stammen würden. Leider wollen wir die Indizes, zu denen alle Elemente gehen werden. Glücklicherweise stellt sich heraus, dass dies die Zuordnung von der Note zurück zur ursprünglichen Indexliste ist, die selbst als Ergebnis der Sortierung der Note angesehen werden kann, sodass wir die Note der Note nehmen können, um das gewünschte Ergebnis zu erzielen.

Pyth, 10 9 Bytes

1 Byte danke an Jakube.

xLo@QNUQU

Testsuite.

Es muss einen kürzeren Weg geben ...

Schläger, 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)))))

Ich bin auf ewig enttäuscht über das Fehlen eines Einbaus dafür.

Ruby, 54 53 Bytes

Probieren Sie es online aus

-1 Byte vom Upgrade auf @ Downgoat, bei dem ein Hash zum Speichern von Werten verwendet wird, anstatt jedes Mal die Duplikate zu zählen.

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

Ich erstelle eine anonyme Funktion, die das Eingabearray aufwertet und es bei der Eingabe zweimal durchläuft. Beim ersten Aufruf wird die Note zurückgegeben. Der zweite Aufruf wird für die Note ausgeführt und gibt den Rang zurück.

Brachylog , 27 Bytes

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

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Erläuterung

Dies ist eine einfache Implementierung der folgenden Beziehung: Jede Ganzzahl der Ausgabe, die einem Element der Eingabe entspricht, ist der Index dieses Elements in der sortierten Eingabe.

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

Wenden Sie eine Schwartzsche Transformation zweimal an.

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

Prüfung

(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 (mit externer Bibliothek) (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 zu lib: https://github.com/mvegh1/Enumerable Erklärung des Codes: Erstellen Sie eine anonyme Methode, die eine Liste von Ganzzahlen akzeptiert. _.From erstellt eine Instanz der Bibliothek, die ein Array mit speziellen Methoden umschließt. Select ordnet jedes Element einem neuen Element zu, indem es den Wert "v" aufnimmt, ihn in eine Zeichenfolge zerlegt und dann den "i" -Ndex dieses Elements verkettet (dies löst doppelten Wertefall). Das ist in der Variablen 'a' gespeichert. Anschließend geben wir das folgende Ergebnis zurück: Ordnen Sie jedes Element in 'a' dem Index dieses Elements in der sortierten Version von a (als Ganzzahlen) zu und übertragen Sie es in ein natives JS-Array

Beachten Sie, dass negative doppelte Zahlen in umgekehrter Reihenfolge gedruckt werden. Ich bin nicht sicher, ob das diese Lösung ungültig macht? Technisch gesehen sollten 8,10,4, -1, -1,8 laut OP 3,5,2,0,1,4 sein, aber mein Code druckt 3,5,2,1,0,4, was ich glaube noch technisch gültig?

GNU Core Utils, 39 33 Bytes

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

Erzeugt 1-basierte Ausgabe. -v0Nach der zweiten hinzufügennl , um eine 0-basierte Ausgabe zu erhalten. (+4 Bytes)

Befehle, die wir verwenden:

• nl Fügt jeder Zeile der Eingabe Zeilennummern hinzu.
• sort -n -k 2 sortiert nach Spalte 2 numerisch.
• cut -f 1 Nimmt die erste durch Tabulatoren getrennte Spalte und verwirft den Rest.

Zusätzlich ist die -s Option an übergeben werden sort, um eine stabile Sortierung anzufordern, die wir hier jedoch nicht benötigen. Wenn zwei Elemente identisch sind, sortwird ihre Reihenfolge bestimmt, indem auf die anderen Spalten zurückgegriffen wird. Dies ist in diesem Fall die monoton steigende Ausgabe von nl. Die Sortierung ist also aufgrund der Eingabe stabil, ohne dass sie angegeben werden muss.

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

Golf gespielt

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

Vielen Dank an @ Kevin Cruissjen für das Rasieren von 9 Bytes.

PHP, 88 Bytes

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

arbeitet mit Kommandozeilenargumenten; druckt eine durch 0 Indexe und Unterstriche getrennte Liste. Laufen Sie mit -nr.

Nervenzusammenbruch

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)

Die meisten integrierten Sortierfunktionen von MATLAB geben ein optionales zweites Array mit den sortierten Indizes zurück. Das j=könnte entfernt werden, wenn das Drucken der Indizes akzeptabel ist, anstatt sie zurückzugeben.

CJam , 19 Bytes

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

Probieren Sie es online!

Erläuterung:

_ 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