3
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – j.p.
    Dec 2, 2011 at 9:22
  • $\begingroup$ @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). $\endgroup$
    – fgrieu ♦
    Dec 2, 2011 at 10:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – j.p.
    Dec 2, 2011 at 13:26
  • $\begingroup$ @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.) $\endgroup$
    – Paŭlo Ebermann
    Dec 2, 2011 at 18:22

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$
    – fgrieu ♦
    Dec 2, 2011 at 11:59
  • $\begingroup$ 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. $\endgroup$
    – Jeff Burdges
    Dec 2, 2011 at 13:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jeff Burdges
    Dec 2, 2011 at 14:02
  • $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Dec 2, 2011 at 14:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jeff Burdges
    Dec 2, 2011 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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