8
$\begingroup$

You want to design a set of yes/no questions for quickly searching the symmetric group. The questions have to be of the form "Does your permutation move $a_1$ to $b_1$ or $a_2$ to $b_2$ or ... or $a_k$ to $b_k$?" Given a random permutation, you will ask all of your questions about that permutation, and your goal is to know what the permutation is once you know the answers to your questions.

In particular, note that you aren't allowed to have later questions depend on the answers to earlier questions. You always ask the same questions of whichever random permutation you get.

Here's a slightly different way to phrase the type of question you're allowed to ask. If we represent the elements of the symmetric group by permutation matrices, then the questions you can ask involve picking a (0,1)-matrix and asking if the random permutation matrix has any 1 where your chosen matrix has a 1 (i.e., if I apply the componentwise AND function to the random matrix and your chosen matrix, do I get 0 or 1?)

Two questions:

  1. How many such questions are needed in order to search $S_n$? How much bigger than $log_2 n!$ is this?
  2. Are there "good" strategies for designing sets of questions that can be used for any n? Can we achieve the minimum number of questions for each n with a single strategy?
$\endgroup$

3 Answers 3

6
$\begingroup$

It certainly isn't difficult to obtain an upper bound of $n\lceil \log_2 n \rceil = O(\log_2 n!)$. All you need to do is to separately learn each bit of each value of the permutation. This looks like it is only roughly optimal, but actually it is already $(1+o(1))(\log_2 n!)$. (Thanks to t3suji for noticing this.) However, the $o(1)$ term only decays logarithmically in this algorithm, so you could ask whether you could make it $(1+O(n^{-\alpha}))(\log_2 n!)$.

I agree with Michael that it seems similar to the asymptotic question of sorting with comparisons. However, in the usual version of that problem, you are allowed to move elements based on an incomplete list of comparisons, which then amounts to adaptive comparisons. You could call this new question "non-adaptive Mastermind for permutations with matrix guesses". Michael also suggested the restricted problem of permutation guesses, which seems like a more difficult problem to me.

$\endgroup$
3
  • $\begingroup$ I agree that permutation guesses are harder. $\endgroup$ Dec 21, 2009 at 16:58
  • 2
    $\begingroup$ I don't understand. Isn't $n\lceil\log_2 n\rceil=(1+o(1))(\log_2 n!)$? $\endgroup$
    – t3suji
    Dec 21, 2009 at 17:14
  • $\begingroup$ Oh yeah, you're right! $\endgroup$ Dec 21, 2009 at 17:21
3
$\begingroup$

This is likely to be a difficult problem. It feels analogous to determining the minimal number of comparisons needed to sort n elements, which appears to only be known up to n = 13. In particular, in both cases we're getting information about a permutation one bit at a time.

However, I think it's known that asymptotically the number of comparisons needed to sort n elements is $(1+o(1)) log_2 (n!)$; I wouldn't be surprised to learn that the same is true for your problem. However, your constraint that later questions can't depend on earlier questions makes things tricky, because it's hard to think of "orthogonal" questions.

Call the unknown permutation $\sigma$. Then one sort of question that could be asked is "does your permutation satisfy $\sigma(k) = \tau(k)$ for any $k$", where $\tau$ is some fixed permutation. In general, the answer will be "yes" with probability about 1-1/e. Perhaps a clever choice of permutations $\tau$ would lead to a solution requiring $C log_2 (n!)$ questions, where $C = 1.0537...$ is the reciprocal of the entropy (in bits) of a Bernoulli(1-1/e) random variable.

$\endgroup$
3
  • $\begingroup$ You can sort n elements in O(log_2 n!) time even if later comparisons are not allowed to depend on earlier ones. See doi.acm.org/10.1145/800061.808726 I don't know whether the best constant in the O( ) is known. $\endgroup$ Dec 21, 2009 at 16:55
  • $\begingroup$ David, can a sorting network be made non-adaptive in the same sense as Gabe's questions? In other words, in the sense of determining a permutation "with 20 questions" with the questions set in advance. I would think that it isn't the same model. $\endgroup$ Dec 21, 2009 at 18:38
  • $\begingroup$ Oh, good point. No, I don't think it can. If there are ever two elements, i and j, which are not directly compared, then we can't distinguish the permutations ij... and ji... , where the ellipsis are the same permutation in both cases. So we need (n choose 2) comparisons. $\endgroup$ Dec 21, 2009 at 21:33
2
$\begingroup$

(The question was updated after this answer and Alon's comment below were written)

If you ask $p$ questions, then the string of answers is a sequence of $p$ bits, with at most $2^p$ different answers. If the string of answers is supposed to identify a unique permutation, then you need that $2^p\geq n!$ or, equivalently, that $p\geq\log_2n!$.

$\endgroup$
2
  • $\begingroup$ May be worth mentioning that log_2(n!) is roughly n log(n), which is worse than exponential in log(n), the benchmark set by the OP. $\endgroup$
    – Alon Amit
    Dec 21, 2009 at 16:00
  • $\begingroup$ Oops, I meant log_2(n!), not log_2(n). I'll fix that now! $\endgroup$ Dec 21, 2009 at 16:12

Your Answer

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

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