Revert array shuffle faster than in O(n^2) I want to reverse an array that was shuffled with the function 

array&lt;integer&gt; shuffle(arr: array&lt;integer&gt;, f: (integer) -&gt; integer) {
    for (i: integer = 0; i &lt; arr.length; i++) swap(arr[i], arr[f(i)]);
    return arr;
}


The array passed to this function is [0, 1, 2, 3, ... n-1] and function f for any i returns a value that is less or equal to i. I have an array returned by the function and I want to restore the results of f(i) for each iteration. What I do currently is:

array&lt;integer&gt; deshuffle(arr: array&lt;integer&gt;) {
    array&lt;integer&gt; result = [];
    for (i : integer = arr.length - 1; i &gt; 0; i++) {
        index: integer = -1;
        for (j: integer = 0; j &lt; i + 1; j++) {
            if (arr[j] == i) {
                index = j;
                break;
            }
        }
        result.push(index);
        swap(arr[i], arr[index]);
    }
}


Here I rely on the fact that the last member of the array can only be shuffled during the last iteration, which means I can find it, push the index and reswap it back and repeat it recursively (this is kinda like the insertion sort if I remember the name correctly). But the trouble is that this code is slow (O($n^{2}$)). Is there any way to do it faster?
It's not very clear what you are asking. It seems you want to find the values of f(i) for all i.

Problem: You can't distinguish between f(0) = 1, f(1) = 0, and f(0) = 0, f(1) = 1.