Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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
1  
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
1  
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
add comment

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
1  
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
1  
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
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.