26
\$\begingroup\$

Summary

Given a list of integers, return the index each integer would end up at when sorted.

For example, if the list was [0,8,-1,5,8], you should return [1,3,0,2,4]. Note that the two 8s maintain their order relative to each other (the sort is stable).

Put another way: For each element in the list, return the number of elements in the list that are: Smaller than the chosen element OR (equal to the element AND appears before the chosen element)

Indexes must start with 0 (not 1)EDIT: given the large pushback, I'll allow 1-based indicies.

Test cases:

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
\$\endgroup\$
6
  • \$\begingroup\$ Despite the simpleness of this challenge, I couldn't find a duplicate of this challenge. \$\endgroup\$ Jul 19, 2016 at 18:05
  • 1
    \$\begingroup\$ This is a specialisation of this question where instead of taking two arrays it takes one array and the second one is [0 1 ... n-1]. \$\endgroup\$ Jul 19, 2016 at 18:28
  • \$\begingroup\$ @PeterTaylor: In that challenge, the array has no repeats. \$\endgroup\$
    – Lynn
    Jul 19, 2016 at 18:32
  • 2
    \$\begingroup\$ Note to solvers: that 8,10,4,-1,-1 test case is very deceptive. Try the 4,4,0,1,1,2,0,1 one first. \$\endgroup\$
    – Lynn
    Jul 19, 2016 at 18:59
  • \$\begingroup\$ @Lynn I looked up what "grade up" does, and I figured out why that test case is so deceptive. Fixed. \$\endgroup\$ Jul 19, 2016 at 19:46

29 Answers 29

21
\$\begingroup\$

APL, 2 bytes

⍋⍋

The “grade up” built-in, applied twice. Works if indexing starts at 0, which isn’t the default for all flavors of APL. Try it here!

Why does this work?

⍋x returns a list of indices that would stably sort x. For example:

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

because if you take element 2, then 6, then 3… you get a stably sorted list:

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

But the index list that answers this question is subtly different: first we want the index of the smallest element, then the second smallest, etc. — again, keeping the original order.

If we look at ⍋x, though, we see it can give us this list easily: the position of a 0 in ⍋x tells us where the smallest element would end up after sorting, and the position of a 1 in ⍋x tells us where the second smallest element would end up, etc.

But we know ⍋x contains exactly the numbers [0, 1… n−1]. If we grade it again, we’ll just get the index of 0 in ⍋x, then the index of 1 in ⍋x, etc., which is precisely what we’re interested in.

So the answer is ⍋⍋x.

\$\endgroup\$
5
  • \$\begingroup\$ wow, this must of been painstakingly golfed :P \$\endgroup\$
    – Downgoat
    Jul 19, 2016 at 18:54
  • \$\begingroup\$ ngn-apl only supports UTF-8, but this works in pretty much every flavor provided that the index origin is set to 0. \$\endgroup\$
    – Dennis
    Jul 19, 2016 at 19:08
  • \$\begingroup\$ That makes me wonder: are there any try-it-onlines for classic APL flavors? \$\endgroup\$
    – Lynn
    Jul 19, 2016 at 19:12
  • \$\begingroup\$ There's TryAPL for Dyalog, but IO defaults to 1. It's easily changeable though. permalink \$\endgroup\$
    – Dennis
    Jul 19, 2016 at 19:13
  • \$\begingroup\$ 1-based is allowed now. \$\endgroup\$ Jul 19, 2016 at 19:30
12
\$\begingroup\$

Jelly, 2 bytes

ỤỤ

Grade up twice. 1-indexed. Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Two bytes in what encoding scheme? \$\endgroup\$
    – WGroleau
    Jul 19, 2016 at 20:50
  • 5
    \$\begingroup\$ Ah! In the Jelly code page. I added a link in the header. :) \$\endgroup\$
    – Lynn
    Jul 19, 2016 at 20:54
6
\$\begingroup\$

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

Don't like using an object but it seems to be the shortest way to keep track of dupes

Explanation

(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
   )
\$\endgroup\$
1
  • \$\begingroup\$ 61 bytes \$\endgroup\$
    – Arnauld
    Sep 14, 2019 at 11:07
6
\$\begingroup\$

K, 5 2 bytes

<<

Grade up (<) twice. JohnE saved three bytes by pointing out tacit expressions exist in K! Super cool. Try it out.

\$\endgroup\$
1
  • \$\begingroup\$ The lambda wrapper is not strictly necessary- you can just write this as a tacit expression <<. Try it here. \$\endgroup\$
    – JohnE
    Jul 21, 2016 at 22:04
5
\$\begingroup\$

Haskell, 50 48 bytes

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

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

It's map snd.sort.zip x [0..] applied twice on the input, i.e pair each element e with it's index i ((e,i)), sort it remove the first elements. Repeat one time.

@Lynn came up with m=map snd.sort.(`zip`[0..]) which has the same byte count.

\$\endgroup\$
0
5
\$\begingroup\$

Python 2, 67 60 bytes

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

Thanks to @xnor for golfing off 7 bytes!

Test it on Ideone.

\$\endgroup\$
2
  • \$\begingroup\$ The flipped enumerate can be done shorter with a zip: l=input();x=zip(l,range(len(l))). \$\endgroup\$
    – xnor
    Jul 19, 2016 at 23:23
  • \$\begingroup\$ In that case, a function is even shorter. Thanks! \$\endgroup\$
    – Dennis
    Jul 19, 2016 at 23:34
4
\$\begingroup\$

PowerShell v2+, 63 bytes

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

Takes input $n, pipes that through a loop over every element |%{...}. Each iteration, we sort $n and get the IndexOf our current element $_. This counts how many items are smaller than the current element. We add to that a slice of $n, that expands every loop iteration, of the elements that are equal to the current element $_ and take the .Count of that. We then subtract -1 so we don't count our current element, and that number is left on the pipeline. Output at the end is implicit.

Examples

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
\$\endgroup\$
4
\$\begingroup\$

CJam, 15 bytes

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

Try it online!

Explanation

{             }       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.
\$\endgroup\$
4
\$\begingroup\$

J, 5 bytes

/:^:2

Grade up (/:) twice (^:2). 0-indexed.

To try it out, type f =: /:^:2 and then f 4 4 0 1 1 2 0 1 into tryj.tk.

\$\endgroup\$
1
  • \$\begingroup\$ Or /:@/: with an equal byte-count. \$\endgroup\$
    – Leaky Nun
    Jul 19, 2016 at 19:57
4
\$\begingroup\$

MATL, 10 9 4 bytes

4 Bytes saved thanks to @Luis

&S&S

This solution uses 1-based indexing

Try it Online

\$\endgroup\$
1
  • \$\begingroup\$ @DrGreenEggsandIronMan I search meta, and I couldn't find anything indicating either way. That said, I've reverted the restricition. \$\endgroup\$ Jul 19, 2016 at 19:30
4
\$\begingroup\$

05AB1E, 12 bytes

2FvyN‚}){€¦˜

Explained

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

Try it online

\$\endgroup\$
4
\$\begingroup\$

Python 2, 67 bytes

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

xnor saved two bytes.

\$\endgroup\$
2
  • \$\begingroup\$ It's shorter to recreate the list of previously-seen elements as you go: a=input();p=[]\nfor x in a:print sorted(a).index(x)+p.count(x);p+=x, \$\endgroup\$
    – xnor
    Jul 19, 2016 at 23:21
  • \$\begingroup\$ Ah, I like that! Thank you. \$\endgroup\$
    – Lynn
    Jul 19, 2016 at 23:31
4
\$\begingroup\$

Haskell, 40 bytes

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

Annotate each element with its index, then map each element to the count of smaller elements, tiebreaking on index. No sorting.

\$\endgroup\$
3
\$\begingroup\$

Julia, 17 bytes

~=sortperm;!x=~~x

1-indexed. Grade up (sortperm) twice. Try it here.

EDIT: Dennis saved four bytes by giving stuff operator-y names! Julia is weird.

\$\endgroup\$
0
3
\$\begingroup\$

JavaScript (ES6), 52 bytes

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

Defines g as the grade function, which returns an array of indices to which all the elements in the sorted array would have come from in the original array. Unfortunately what we want is the indices which all the elements will go to. Fortunately this turns out to be the mapping from the grade back to the original list of indices, which itself can be considered to be the result of sorting the grade, thus allowing us to take the grade of the grade to achieve the desired result.

\$\endgroup\$
3
\$\begingroup\$

Pyth, 10 9 bytes

1 byte thanks to Jakube.

xLo@QNUQU

Test suite.

There must be a shorter way...

\$\endgroup\$
1
  • \$\begingroup\$ xL instead of sxR. Or am I overlooking something? \$\endgroup\$
    – Jakube
    Jul 19, 2016 at 22:06
2
\$\begingroup\$

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

I am eternally disappointed by the lack of a builtin for this.

\$\endgroup\$
2
  • \$\begingroup\$ Would it be shorter to put each element in a (number, index) pair, then sort it? \$\endgroup\$ Jul 19, 2016 at 20:40
  • \$\begingroup\$ I tried that, but it gives me the inverse of the list that I'd want, and unfortunately getting the index of an object within the list in order to invert it is horribly byte-inefficient. \$\endgroup\$
    – Steven H.
    Jul 19, 2016 at 20:46
2
\$\begingroup\$

Ruby, 54 53 bytes

Try it online

-1 byte from upgrading to @Downgoat's approach of using a hash to store values instead of counting the duplicates each time.

->a{b={};a.map{|e|a.sort.index(e)+b[e]=(b[e]||-1)+1}}
\$\endgroup\$
5
  • \$\begingroup\$ Ruby's sort is unstable, which means that this might do the wrong thing on ties. \$\endgroup\$ Jul 19, 2016 at 20:39
  • 1
    \$\begingroup\$ @NathaMerrill It doesn't because of the exact method I am using to generate the numbers. If I sorted on a list of indices, it would produce the wrong result. Try the link! It'll work 60% of the time, every time. I'll post an explanation later on it, too. \$\endgroup\$
    – Value Ink
    Jul 19, 2016 at 20:42
  • \$\begingroup\$ Ah, ok. I wasn't sure what the rest of the code is doing (I don't know Ruby) \$\endgroup\$ Jul 19, 2016 at 20:44
  • \$\begingroup\$ ? It doesn't do the wrong thing on ties, but it does something else wrong 40% of the time? \$\endgroup\$
    – WGroleau
    Jul 19, 2016 at 20:52
  • \$\begingroup\$ @WGroleau it's an Anchorman quote. My code works all the time, though. \$\endgroup\$
    – Value Ink
    Jul 19, 2016 at 21:00
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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])
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 15 bytes

(o=Ordering)@*o
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 135 bytes

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

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
\$\endgroup\$
1
\$\begingroup\$

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

enter image description here

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?

\$\endgroup\$
1
\$\begingroup\$

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.

Additionally, the -s option can be passed to sort to request a stable sort, but we don't need it here. If two items are identical, sort will determine their order by falling back to the other columns, which in this case is the monotonically increasing output from nl. So the sort will be stable without needing to specify it, by virtue of the input.

\$\endgroup\$
1
\$\begingroup\$

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

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

Thanks to @Kevin Cruissjen for shaving of 9 bytes.

\$\endgroup\$
2
  • \$\begingroup\$ @Nathan Merrill I noticed that when i golfed it, but forgot it when i pasted the golfed answer in. \$\endgroup\$ Aug 1, 2016 at 20:41
  • 1
    \$\begingroup\$ You can golf it some more. You don't need the spaces between int[] a and int[] b. You can take the int out of the loops. And since you use b.length twice at the start you can put it in a separate field. So in total something like this: int[]a(int[]b){int l=b.length,o[]=new int[l],i,j;for(i=-1;++i<l;)for(j=-1;++i<b.length;)if(b[i]==Arrays.sort(b.clone())[j])o[i]=j;return o;} (140 bytes) Hmm, also, it doesn't seem to work.. Arrays.sort(...) doesn't return anything (it's a void method), so how can you compare it with b[i]?.. \$\endgroup\$ Aug 2, 2016 at 7:58
1
\$\begingroup\$

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
    ;
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.