Take the 2-minute tour ×

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?

share|improve this question
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 '11 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 '11 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 '11 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.) –  Paŭlo Ebermann Dec 2 '11 at 18:22
@PaŭloEbermann: Thanks. –  j.p. Dec 3 '11 at 15:59

1 Answer 1

up vote 2 down vote accepted

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.

In general, inverting a permutation is [exactly] as hard as unordered search.

share|improve this answer
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 '11 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. –  Jeff Burdges Dec 2 '11 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. –  Jeff Burdges Dec 2 '11 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 '11 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. –  Jeff Burdges Dec 2 '11 at 14:33

Your Answer


