Ordering a list

Question

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

Answer 1

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.

Answer 2

Jelly, 2 bytes

ỤỤ

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

Answer 3

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
   )

Answer 4

K, 5 2 bytes

<<

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

Answer 5

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.

Answer 6

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.

Answer 7

MATL, 10 9 4 bytes

4 Bytes saved thanks to @Luis

&S&S

This solution uses 1-based indexing

Try it Online

Answer 8

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.

Answer 9

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.

Answer 10

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

Answer 11

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.

Answer 12

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

Answer 13

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.

Answer 14

Pyth, 10 9 bytes

1 byte thanks to Jakube.

xLo@QNUQU

Test suite.

There must be a shorter way...

Answer 15

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.

Answer 16

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.

Answer 17

Mathematica, 135 bytes

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

Answer 18

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.

Answer 19

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

Answer 20

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.

Answer 21

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

Answer 22

Mathematica, 15 bytes

(o=Ordering)@*o

Answer 23

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
    ;

Answer 24

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

Answer 25

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.

Answer 26

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?

Answer 27

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.

Answer 28

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.

Answer 29

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