# Choosing permutations with constraints

I have to choose $k$ items out of $n$ choices, and my selection needs to be in the correct order (i.e. permutation, not combination). After I make a choice, I receive a hint that tells me how many of my selections were correct, and how many were in the correct order.

For example, if I'm trying to choose $k = 4$ out of $n = 6$ items, and the correct ordered set is $\{5, 3, 1, 2\}$, then an exchange may go as follows:

0,1,2,3
(3, 0) # 3 correct, 0 in the correct position

0,1,2,5
(3, 0)

0,1,5,3
(3, 0)

0,5,2,3
(3,0)

5,1,2,3
(4,1)

5,3,1,2
(4,4)

-> correct order, the game is over


The problem is I'm only given a limited number of tries to get the order right, so if $n = 6, k = 4$, then I only get $t = 6$ tries, if $n = 10, k = 5$ then $t = 5$, and if $n = 35, k = 6$ then $t = 18$.

Where do I start to even solve this? It almost seems like a constraint solving problem. The hard part seems to be that I only know something for sure if I only change 1 thing at once, but the upper bound on that is way more than the number of tries I get.

-
If the no. of tries given is small, there may be no way to actually solve it(unless you're lucky). – Ishan Banerjee Feb 1 '13 at 5:39
$t=5, n=10, k=5$ sounds awfully tight, but the others should be quite feasible with a basic strategy. Think of it as similar to binary search, where each guess allows you to throw out a certain fraction of the number of possibilities. You might find inspiration in Knuth's algorithm for a very similar game. – Erick Wong Feb 1 '13 at 6:16