0

Given a permutation on n letters, how many clues do you need to solve it?

For example if the permutation is 31524, the clues come in the form of 5<4, meaning that 5 comes before 4.

So, given a permutation $\sigma$ and a set of clues C: ($\sigma$, C), determine whether C determines $\sigma$.

JMP
  • 21,771
  • Is this the same as asking for the worst case scenario to sort $n$ things? That may be known, and as I recall the "bubble sort" does the job but may not be optimal in the sense of best worst case scenario. – coffeemath Mar 22 '15 at 11:28
  • i could tell you 3<1, 1<5, 5<2, 2<4 and we'ed be done. or 3<1, 3<5, 3<2, 3<4, 1<5, 1<2, 1<4, 5<2, 5<4 but we still don't know 2R4. i think the Q is asking if a set of clues enables a solution. – JMP Mar 22 '15 at 11:32

0 Answers0