Reconstruct a Permutation

Question

Introduction

Suppose that you are handed a random permutation of n objects. The permutation is sealed in a box, so you have no idea which of the n! possible ones it is. If you managed to apply the permutation to n distinct objects, you could immediately deduce its identity. However, you are only allowed to apply the permutation to length-n binary vectors, which means you'll have to apply it several times in order to recognize it. Clearly, applying it to the n vectors with only one 1 does the job, but if you're clever, you can do it with log(n) applications. The code for that method will be longer, though...

This is an experimental challenge where your score is a combination of code length and query complexity, meaning the number of calls to an auxiliary procedure. The spec is a little long, so bear with me.

The Task

Your task is to write a named function (or closest equivalent) f that takes as inputs a positive integer n, and a permutation p of the first n integers, using either 0-based or 1-based indexing. Its output is the permutation p. However, you are not allowed to access the permutation p directly. The only thing you can do with it is to apply it to any vector of n bits. For this purpose, you shall use an auxiliary function P that takes in a permutation p and a vector of bits v, and returns the permuted vector whose p[i]th coordinate contains the bit v[i]. For example:

P([1,2,3,4,0], [1,1,0,0,0]) == [0,1,1,0,0]

You can replace "bits" with any two distinct values, such as 3 and -4, or 'a' and 'b', and they need not be fixed, so you can call P with both [-4,3,3,-4] and [2,2,2,1] in the same call to f. The definition of P is not counted toward your score.

Scoring

The query complexity of your solution on a given input is the number of calls it makes to the auxiliary function P. To make this measure unambiguous, your solution must be deterministic. You can use pseudo-randomly generated numbers, but then you must also fix an initial seed for the generator.

In this repository you'll find a file called permutations.txt that contains 505 permutations, 5 of each length between 50 and 150 inclusive, using 0-based indexing (increment each number in the 1-based case). Each permutation is on its own line, and its numbers are separated by spaces. Your score is byte count of f + average query complexity on these inputs. Lowest score wins.

Extra Rules

Code with explanations is preferred, and standard loopholes are disallowed. In particular, individual bits are indistinguishable (so you can't give a vector of Integer objects to P and compare their identities), and the function P always returns a new vector instead of re-arranging its input. You can freely change the names of f and P, and the order in which they take their arguments.

If you are the first person to answer in your programming language, you are strongly encouraged to include a test harness, including an implementation of the function P that also counts the number of times it was called. As an example, here's the harness for Python 3.

def f(n,p):
    pass # Your submission goes here

num_calls = 0

def P(permutation, bit_vector):
    global num_calls
    num_calls += 1
    permuted_vector = [0]*len(bit_vector)
    for i in range(len(bit_vector)):
        permuted_vector[permutation[i]] = bit_vector[i]
    return permuted_vector

num_lines = 0
file_stream = open("permutations.txt")
for line in file_stream:
    num_lines += 1
    perm = [int(n) for n in line.split()]
    guess = f(len(perm), perm)
    if guess != perm:
        print("Wrong output\n %s\n given for input\n %s"%(str(guess), str(perm)))
        break
else:
    print("Done. Average query complexity: %g"%(num_calls/num_lines,))
file_stream.close()

In some languages, it is impossible to write such a harness. Most notably, Haskell does not allow the pure function P to record the number of times it is called. For this reason, you are allowed to re-implement your solution in such a way that it also calculates its query complexity, and use that in the harness.

Answer 1

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 (⌈log₂ 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 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&.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.

Answer 2

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

Answer 3

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 = #] &