Reconstruct a Permutation
J, 44.0693 22.0693 = 37 15 + 7.06931

If we can't call P on i. n, we can at least call P on each bit of i. n separately. The number of invocations of P is &gt;. 2 ^. n (&lceil;log2&thinsp;n&rceil;). I believe this is optimal.

f=:P&amp;.|:&amp;.#:@i.


Here is an implementation of the function P which uses the permutation vector p and saves the number of invocations into Pinv.

P =: 3 : 0"1
 Pinv =: Pinv + 1
 assert 3 &gt; # ~. y    NB. make sure y is binary
 p { y
)


Here is a testing harness that receives a permutation and returns the number of invocations of p:

harness =: 3 : 0
 Pinv =: 0
 p =: y
 assert y = f # y     NB. make sure f computed the right permutation
 Pinv
)


And here is how you can use it on the file permutations.txt:

NB. average P invocation count
(+/ % #) harness@".;._2 fread 'permutations.txt'


Explanation

The short explanation is already provided above, but here is a more detailed one. First, f with spaces inserted and as an explicit function:

f =: P&amp;.|:&amp;.#:@i.
f =: 3 : 'P&amp;.|:&amp;.#: i. y'


Read:


  Let f be P under transposition under base-2 representation of the first y integers.


where y is the formal parameter to f. in J, the parameters to a  (function) are called x and y if the verb is dyadic (has two parameters) and y if it is monadic (has one parameter).

Instead of invoking P on i. n (i.e. 0 1 2 ... (n - 1)), we invoke P on each bit position of the numbers in i. n. Since all permutations permute in the same way, we can reassemble the permutated bits into numbers to get a permutation vector:


i. y – integers from 0 to y - 1.
#: y – y represented in base 2. This is extended to vectors of numbers in the natural way. For instance, #: i. 16 yields:

0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

#. y – y interpreted as a base 2 number. Notably, this is the inverse to #:; y ~: #. #: always holds.
|: y – y transposed.
u&amp;.v y – u under v, that is vinv u v y where vinv is the inverse to v. Notice that |: is its own inverse.
P y – the function P applied to each vector in y by definition.