Suppose that you are handed a random permutation of
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
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.
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
However, you are not allowed to access the permutation
The only thing you can do with it is to apply it to any vector of
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
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
'b', and they need not be fixed, so you can call
P with both
[2,2,2,1] in the same call to
The definition of
P is not counted toward your score.
The query complexity of your solution on a given input is the number of calls it makes to the auxiliary function
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.
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
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 = *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.