# How do we find the last two correspondences in an otherwise known even permutation?

A secret even permutation $P$ of the set of non-negative integers less than $n$ is chosen. That might be a Feisltel cipher with a random key.

We are given in sequence the $P(x)$ for $x$ from $0$ to $n-3$, and must output the ordered pair $(P(n-2),P(n-1))$.

What's an efficient online algorithm for that? What’s a practical minimum for the memory needed?

What if we are allowed $n-2$ queries giving $P(x_i)$ for any $x_i$ that we iteratively decide, and must output $(x_{n-2},P(x_{n-2}),x_{n-1},P(x_{n-1}))$ where $x_{n-2}$ and $x_{n-1}$ have not been queried?

What if we are allowed to repeat an earlier query for free?

• There are $n$ over $n/2$ subsets of order $n/2$. Each of them might equal $\{P(0), \dots, P(n/2)\}$. So you need at least $\log_2(\binom{n}{n/2}) \approx \log_2(2^n) = n$ bit memory.
– j.p.
Dec 2, 2011 at 9:22
• @jug: yes, that gives a lower bound for the memory needed (though not in the variant where we can re-query, which is not apparent from your sketch).
– fgrieu
Dec 2, 2011 at 10:24
• If time doesn't matter to you, you can query at most $n*(n-2)$ times to find the two missing values. Then count the number of inversions of the permutation you get when assigning the two missing values to $n-1$ and $n$ in a fixed random way. You can do this in $n^2$ time and $\log(n)$ space (see mathoverflow.net/questions/72669/…). Finally correct the assignment if the permutation was odd.
– j.p.
Dec 2, 2011 at 13:26
• @jug: a \over b results in $a \over b$. You can get a binomial coefficient by \binom{a}{b} = $\binom{a}{b}$. (I was so free to edit your comment.) Dec 2, 2011 at 18:22

All permutations have a cycle decomposition from which you may immediately read off your $P(n-2)$ and $P(n-1)$. There are trivial algorithms for doing this that run in either $O(n)$ time and $O(n)$ space (invert the permutation), or $O(n^2)$ time and $O(1)$ space (walk backwards by querying everybody repeatedly).

You could adapt that invert the permutation algorithm to use only 1 bit per element, but that's still $O(n)$ space. Alternatively, if you have an efficient representation for a sparse permutation, then you may replace $n$ by the number of elements actually moved.

• On second try at a comment, I think that I get an algorithm for cycle decomposition in $O(n)$ time, and how to adapt that for a full algorithm, but I need $O(n \cdot log(n))$ space in the first stated problem. Any pointer or clue to something using less memory?
– fgrieu
Dec 2, 2011 at 11:59
• Inverse : Initialize $inverse[i] = -1$ for $i=1..n$. Set $inverse[P(i)] = i$ for $i=1..n$. If $inverse[n-2] = -1$ or $inverse[n-1] = -1$, then use parity to decide whether it's a fixed point or maps to $n-1$ or $n-2$, respectively. Dec 2, 2011 at 13:39
• If your going for n bits plus O(1), then : Iterate thorough the entries exhausting each elements cycle as far as possible to gradually build out the cycle(s) that end in $n-2$ and $n-1$. You use the n bit array to prevent reprocessing cycles. Dec 2, 2011 at 14:02
• OK, you count variables the same regardless of their bit width, which actually grows as $o(log_2(n))$. So your $O(n)$ space is my $O(n\cdot log(n))$ space.
– fgrieu
Dec 2, 2011 at 14:04
• Create an object Pmod with two variables a and b such that Pmod(a) = n-1, Pmod(b) = n-2, and Pmod(j) = P(j) otherwise. For i=0..n-3, if done[i]==0 then : Initialize j=i. Loop setting done[j]=1 and j=Pmod(j)\$ until done[j]==1. If j==n-1, set a=i. If j==n-2, set b=i. You compute the answer using the final values of a and b. Dec 2, 2011 at 14:33