How to find the permutation of a sort in Java

Question

I want to sort an array and find the index of each element in the sorted order. So for instance if I run this on the array:

[3,2,4]

I'd get:

[1,0,2]

Is there an easy way to do this in Java?

Answer 1

import java.util.*;
public class Testing{
   public static void main(String[] args){
       int[] arr = {3, 2, 4, 6, 5};
       TreeMap map = new TreeMap();
       for(int i = 0; i < arr.length; i++){
            map.put(arr[i], i);
       }
       System.out.println(Arrays.toString(map.values().toArray()));
   }
}

Answer 2

Let's assume your elements are stored in an array.

final int[] arr = // elements you want
List<Integer> indices = new ArrayList<Integer>(arr.length);
for (int i = 0; i < arr.length; i++) {
  indices.add(i);
}
Comparator<Integer> comparator = new Comparator<Integer>() {
  public int compare(Integer i, Integer j) {
    return Integer.compare(arr[i], arr[j]);
  }
}
Collections.sort(indices, comparator);

Now indices contains the indices of the array, in their sorted order. You can convert that back to an int[] with a straightforward enough for loop.

Answer 3

One way to achieve this is to make a list of pairs with the starting index as the second part of the pair. Sort the list of pairs lexicographically, then read off the starting positions from the sorted array.

Starting array:

[3,2,4]

Add pairs with starting indexes:

[(3,0), (2,1), (4,2)]

Sort it lexicographically

[(2,1), (3,0), (4,2)]

then read off the second part of each pair

[1,0,2]

Answer 4

import java.io.*;

public class Sample {
    public static void main(String[] args) {
        int[] data = {0, 3, 2, 4, 6, 5, 10};//case:range 0 - 10
        int i, rangeHigh = 10;
        int [] rank = new int[rangeHigh + 1];
        //counting sort
        for(i=0; i< data.length ;++i) ++rank[data[i]];
        for(i=1; i< rank.length;++i) rank[i] += rank[i-1];
        for(i=0;i<data.length;++i)
            System.out.print((rank[data[i]]-1) + " ");//0 2 1 3 5 4 6
    }
}

Answer 5

As an update, this is relatively easy to do in Java 8 using the streams API.

public static int[] sortedPermutation(final int[] items) {
  return IntStream.range(0, items.length)
    .mapToObj(value -> Integer.valueOf(value))
    .sorted((i1, i2) -> Integer.compare(items[i1], items[i2]))
    .mapToInt(value -> value.intValue())
    .toArray();
}

It somewhat unfortunately requires a boxing and unboxing step for the indices, as there is no .sorted(IntComparator) method on IntStream, or even an IntComparator functional interface for that matter.

To generalize to a List of Comparable objects is pretty straightforward:

public static <K extends Comparable <? super K>> int[] sortedPermutation(final List<K> items) {
  return IntStream.range(0, items.size())
    .mapToObj(value -> Integer.valueOf(value))
    .sorted((i1, i2) -> items.get(i1).compareTo(items.get(i2)))
    .mapToInt(value -> value.intValue())
    .toArray();
}