Inversion of an array that contains indices

Question

I have an array of length n that contains numbers from 0 to n-1 in random order. I now want to "inverse" this array to one that where index i corresponds to the location of i in the source array.

Example

Source_Array = {2,0,1}

Transform to:

Result_Array = {1,2,0}

This means I find the index 0 at position 1 in my source, 1 is at location 2 and so on.

I did this with the following function:

Dim Sourcelist As List(Of Integer) = Source.ToList
Dim Result(Source.Count - 1) As Integer
For i = 0 To Source.Count - 1
 Result(i) = Sourcelist.IndexOf(i)
Next

Casting the array to List and then slowly using IndexOf to select the indices is not really great. Is there a better method maybe using LINQ?

Both VB.NET and C# answers are very much appreciated.

Answer 1

Unfortunately I don't really know visual basic but I think that you will find it easy to grasp the idea (and implement it in any language) of the following java code:

int[] source = new int[]{2,0,1};
int[] dest = new int[source.length];
for (int i = 0; i < source.length; i += 1) {
 dest[source[i]] = i;
}

The code runs at \$O(n)\$ time whereas if you search for every element you get \$O(n^2)\$ time.

• Jens: Perfect, that's an elegant solution to this problem.

Answer 2

I'm not very good with LINQ but here's my take at it.

Dim Result_Array = From v In Source_Array Select Source_Array(v)