Data structure for permutations in Java

Question

I need to store a permutation of n integers and be able to compute both the permutation of a value and the inverse operation in efficient time.

I.e, I need to store a reordering of values [0...n-1] in such a way I can ask for position(i) and value(j) (with 0 <= i,j <= n).

With an example—Suppose we have the following permutation of values:

• [7,2,3,6,0,4,8,9,1,5]

I need the following operations:

• position(7) = 9
• value(9) = 7

I know libraries in C++ for that, such as: https://github.com/fclaude/libcds2

Is there any structure or library in Java that allows to do that and is efficient in space and time?

Answer 1

If there are no duplicates, the List interface will suit your needs.

It provides the following methods:

• List#get(index) returns the element with index index
• List#indexOf(element) returns the index of the first encountered element