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 >. 2 ^. n (⌈log2 n⌉). I believe this is optimal.
f=:P&.|:&.#:@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 > # ~. 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&.|:&.#:@i.
f =: 3 : 'P&.|:&.#: 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 from0toy - 1.#: y–yrepresented in base 2. This is extended to vectors of numbers in the natural way. For instance,#: i. 16yields: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–yinterpreted as a base 2 number. Notably, this is the inverse to#:;y ~: #. #:always holds.|: y–ytransposed.u&.v y–uunderv, that isvinv u v ywherevinvis the inverse tov. Notice that|:is its own inverse.P y– the functionPapplied to each vector inyby definition.
Pyth 32 + 7.06931 = 37.06931
I found the following algorithm completely independent. But it's more or less the same thing as FUZxxl very short J solution (as far as I understand it).
First the definition of the function P, which permutes an bit-array according to an unknown permutation.
D%GHJHVJ XJ@HN@GN)RJ
And then the code, that determines the permutation.
Mmxmi_mbk2Cm%dHCm+_jk2*sltG]0GdG
This defines a function g, that takes two arguments. You can call it by g5[4 2 1 3 0. Here's an online demonstration. Never used so many (5) nested maps.
Btw I haven't actually made a test harness. Neither does the function P count how many times I call it. I have spend way to much time already figuring out the algorithm. But if you read my explanation, it's quite obvious that it uses int(log2(n-1)) + 1 calls (= ceil(log2(n))). And sum(int(log2(n-1)) + 1 for n in range(50, 151)) / 101.0 = 7.069306930693069.
Explanation:
I actually had quite a hard time finding this algorithm. It was not clear to me at all, how to achieve log(n). So I started doing some experiments with small n.
First note: A bit-array gathers the same information as the complement bit-array. Therefore all bit-arrays in my solution have at most n/2 active bit.
n = 3:
Since we can only use bit-array with 1 active bit, the optimal solution depends of two calls. E.g. P([1, 0, 0]) and P([0, 1, 0]). The results tell us the first and second number of the permutation, indirectly we get the third one.
n = 4:
Here it get's a little bit interesting. We now can use two kinds of bit-array. Those with 1 active bit and those with 2 active bits. If we use a bit-array with one active bit, we only gather information about one number of the permutation, and fall back to n = 3, resulting in 1 + 2 = 3 calls of P. The interesting part is that we can do the same thing with only 2 calls, if we use bit-arrays with 2 active bits. E.g. P([1, 1, 0, 0]) and P([1, 0, 1, 0]).
Let's say we get the outputs [1, 0, 0, 1] and [0, 0, 1, 1]. We see, that the bit number 4 is active in both output arrays. The only bit that was active in both input arrays was bit number 1, so clearly the permutation starts with 4. Now it's easy to see, that bit 2 was moved to bit 1 (first output), and bit 3 was moved to bit 3 (second output). Therefore the permutation must be [4, 1, 3, 2].
n = 7:
Now something bigger. I'll show the calls of P immediately. They are the once, that I came up with after a little thinking and experimenting. (Notice these are not the ones, that I use in my code.)
P([1, 1, 1, 0, 0, 0, 0])
P([1, 0, 0, 1, 1, 0, 0])
P([0, 0, 1, 1, 0, 1, 0])
If in the first two output arrays (and not in the third) the bit 2 is active, we know that the permutation moves bit 1 to bit 2, since bit one is the only bit that is active in the first two input arrays.
The important thing is, that (interpreting the inputs as matrix) each of the columns are unique. This remembered me on Hamming codes, where the same thing is accomplished. They simply take the numbers 1 to 7, and use their bit-representation as columns. I'll use the numbers 0 to 6. Now the nice part, we can interpret the outputs (again the columns) as numbers again. These tell us the result of the permutation applied to [0, 1, 2, 3, 4, 5, 6].
0 1 2 3 4 5 6 1 3 6 4 5 0 2
P([0, 1, 0, 1, 0, 1, 0]) = [1, 1, 0, 0, 1, 0, 0]
P([0, 0, 1, 1, 0, 0, 1]) = [0, 1, 1, 0, 0, 0, 1]
P([0, 0, 0, 0, 1, 1, 1]) = [0, 0, 1, 1, 1, 0, 0]
So we only have to trace back the numbers. Bit 0 ended up in bit 5, bit 1 ended up in bit 0, bit 2 ended up in bit 6, ... So the permutation was [5, 0, 6, 1, 3, 4, 2].
Mmxmi_mbk2Cm%dHCm+_jk2*sltG]0GdG
M define a function g(G, H), that will return
the result of the following computation:
G is n, and H is the permutation.
m G map each k in [0, 1, ..., Q-1] to:
_ their inverse
jk2 binary representation (list of 1s and 0s)
+ extended with
*sltG]0 int(log2(Q - 1)) zeros
C transpose matrix # rows that are longer
# than others are shortened
m%dH map each row (former column) d of
the matrix to the function P (here %)
C transpose back
m map each row k to:
i 2 the decimal number of the
_mbk inverse list(k) # C returns tuple :-(
Let's call the result X.
m G map each d in [0, 1, ..., Q - 1] to:
x X d the index of d in X
And the code for the permutation function:
D%GHJHVJ XJ@HN@GN)RJ
D%GH def %(G, H): # the function is called %
JH J = copy(H)
VJ ) for N in [0, 1, ..., len(J) - 1]:
XJ@HN@GN J[H[N]] = G[N]
RJ return J
Mathematica, 63 + 100 = 163
I'm using one-based permutations, since that's how indexing works in Mathematica.
First, the test harness. This is the query function p (user-defined names shouldn't be upper-case in Mathematica):
p[perm_, vec_] := (
i += 1;
vec[[Ordering@perm]]
);
And input preparation along with the test loop:
permutations =
ToExpression@StringSplit@# + 1 & /@
StringSplit[Import[
"https://raw.githubusercontent.com/iatorm/permutations/master/permutations.txt"
], "\n"];
total = 0;
(
i = 0;
result = f@#;
If[# != result,
Print["Wrong result for ", #, ". Returned ," result ", instead."]
];
total += i;
) & /@ permutations;
N[total/Length@permutations]
And finally, my actual submission which uses the naive algorithm for now:
f=(v=0q;v[[#]]=1;Position[q~p~v,1][[1,1]])&/@Range@Length[q=#]&
Or with indentation:
f = (
v = 0 q;
v[[#]] = 1;
Position[q~p~v, 1][[1, 1]]
) & /@ Range@Length[q = #] &