Come trovare la permutazione di una specie in Java

Question

voglio ordinare un array e trovare l'indice di ogni elemento in modo ordinato. Così, per esempio, se faccio funzionare questo sulla matrice:

[3,2,4] 

avrei avuto:

[1,0,2] 

C'è un modo semplice per fare questo in Java?

Answer 1

Supponiamo gli elementi sono memorizzati in un 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); 

Ora indices contiene gli indici della matrice, nel loro ordine ordinato. È possibile convertirlo in uno int[] con un ciclo abbastanza semplice for.

Answer 2

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 3

Un modo per ottenere ciò è creare una lista di coppie con l'indice iniziale come seconda parte della coppia. Ordina l'elenco di coppie lessicograficamente, quindi leggi le posizioni iniziali dall'array ordinato.

matrice di partenza:

[3,2,4] 

aggiungere coppie con indici partire:

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

ordine è lexicographically

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

poi letta la seconda parte di ciascuna coppia

[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

Come aggiornamento, questo è relativamente facile da eseguire in Java 8 utilizzando l'API di streaming.

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

È piuttosto richiede purtroppo boxe e passo unboxing per gli indici, in quanto non v'è alcun metodo .sorted(IntComparator) su IntStream, o anche un'interfaccia funzionale IntComparator per quella materia.

generalizzare ad un List di Comparable oggetti è abbastanza semplice:

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