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\$
  • \$\begingroup\$ Despite the simpleness of this challenge, I couldn't find a duplicate of this challenge. \$\endgroup\$ – Nathan Merrill Jul 19 '16 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\$ – Peter Taylor Jul 19 '16 at 18:28
  • \$\begingroup\$ @PeterTaylor: In that challenge, the array has no repeats. \$\endgroup\$ – Lynn Jul 19 '16 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 '16 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\$ – Nathan Merrill Jul 19 '16 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\$
  • \$\begingroup\$ wow, this must of been painstakingly golfed :P \$\endgroup\$ – Downgoat Jul 19 '16 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 '16 at 19:08
  • \$\begingroup\$ That makes me wonder: are there any try-it-onlines for classic APL flavors? \$\endgroup\$ – Lynn Jul 19 '16 at 19:12
  • \$\begingroup\$ There's TryAPL for Dyalog, but IO defaults to 1. It's easily changeable though. permalink \$\endgroup\$ – Dennis Jul 19 '16 at 19:13
  • \$\begingroup\$ 1-based is allowed now. \$\endgroup\$ – Nathan Merrill Jul 19 '16 at 19:30
12
\$\begingroup\$

Jelly, 2 bytes

ỤỤ

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

\$\endgroup\$
  • \$\begingroup\$ Two bytes in what encoding scheme? \$\endgroup\$ – WGroleau Jul 19 '16 at 20:50
  • 5
    \$\begingroup\$ Ah! In the Jelly code page. I added a link in the header. :) \$\endgroup\$ – Lynn Jul 19 '16 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\$
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\$
  • \$\begingroup\$ The lambda wrapper is not strictly necessary- you can just write this as a tacit expression <<. Try it here. \$\endgroup\$ – JohnE Jul 21 '16 at 22:04
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\$
  • \$\begingroup\$ The flipped enumerate can be done shorter with a zip: l=input();x=zip(l,range(len(l))). \$\endgroup\$ – xnor Jul 19 '16 at 23:23
  • \$\begingroup\$ In that case, a function is even shorter. Thanks! \$\endgroup\$ – Dennis Jul 19 '16 at 23:34
4
\$\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\$
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\$
  • \$\begingroup\$ Or /:@/: with an equal byte-count. \$\endgroup\$ – Leaky Nun Jul 19 '16 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\$
  • \$\begingroup\$ @DrGreenEggsandIronMan I search meta, and I couldn't find anything indicating either way. That said, I've reverted the restricition. \$\endgroup\$ – Nathan Merrill Jul 19 '16 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\$
  • \$\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 '16 at 23:21
  • \$\begingroup\$ Ah, I like that! Thank you. \$\endgroup\$ – Lynn Jul 19 '16 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\$
3
\$\begingroup\$

Pyth, 10 9 bytes

1 byte thanks to Jakube.

xLo@QNUQU

Test suite.

There must be a shorter way...

\$\endgroup\$
  • \$\begingroup\$ xL instead of sxR. Or am I overlooking something? \$\endgroup\$ – Jakube Jul 19 '16 at 22:06
  • \$\begingroup\$ @Jakube Thanks! \$\endgroup\$ – Leaky Nun Jul 20 '16 at 2:53
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\$
  • \$\begingroup\$ Would it be shorter to put each element in a (number, index) pair, then sort it? \$\endgroup\$ – Nathan Merrill Jul 19 '16 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 '16 at 20:46
2
\$\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\$
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\$
  • \$\begingroup\$ Ruby's sort is unstable, which means that this might do the wrong thing on ties. \$\endgroup\$ – Nathan Merrill Jul 19 '16 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 '16 at 20:42
  • \$\begingroup\$ Ah, ok. I wasn't sure what the rest of the code is doing (I don't know Ruby) \$\endgroup\$ – Nathan Merrill Jul 19 '16 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 '16 at 20:52
  • \$\begingroup\$ @WGroleau it's an Anchorman quote. My code works all the time, though. \$\endgroup\$ – Value Ink Jul 19 '16 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\$
  • \$\begingroup\$ @Nathan Merrill I noticed that when i golfed it, but forgot it when i pasted the golfed answer in. \$\endgroup\$ – Roman Gräf Aug 1 '16 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\$ – Kevin Cruijssen Aug 2 '16 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, privacy policy and cookie policy

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