CODEWITHSUNDEEP
javaalgorithmsortingarray-algorithms
user491880
user491880

Reputation: 4869

How to find the permutation of a sort in Java

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?

Upvotes: 9

Views: 3891

Answers (5)

Louis Wasserman
Louis Wasserman

Reputation: 198033

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.

Upvotes: 8

clstrfsck
clstrfsck

Reputation: 14829

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

Upvotes: 0

BLUEPIXY
BLUEPIXY

Reputation: 40145

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

Upvotes: 0

Keith Randall
Keith Randall

Reputation: 23265

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]

Upvotes: 1

rickz
rickz

Reputation: 4474

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

Upvotes: 1

Related Questions