Are You the One? (Mastermind Derivative) I've got a tough one for you!

My girlfriend recently came across a new show on MTV (USA). It's a terrible show, and everyone on it is trashy, but the "game" is pretty interesting.  From Wikipedia: 


  Are You The One? follows 20 people who are living together in Hawaii to find their perfect match. If the 10 men and 10 women are
  able to correctly choose all ten perfect matches in ten weeks, they
  will gain $1 million to split among them.


Now for the game portion (also from Wikipedia):


  Each episode the cast will pair up with who they believe their perfect
  match is to compete in a challenge. The winners of the challenge will
  go on a date, and have a chance to test their match in the truth
  booth. The cast members will choose one of the winning couples to go
  to the truth booth to determine if they are a perfect match or not.
  This is the only way to confirm matches. Each episode ends with a matching ceremony where the couples will be told how many perfect
  matches they have, but not which matches are correct.


TL;DR:  This is a Mastermind derivative ( M(10,10) to be specific). The rules of the game are as follows:


You start with 2 sets of 10, let's call them Set A:
{A,B,C,D,E,F,G,H,I,J} and Set 2: {1,2,3,4,5,6,7,8,9,10}
The computer creates a solution (not visible to you) in the form
of {A1,B2,C3,D4,E5,F6,G7,H8,I9,J10}, where the members in set A are
mapped 1-to-1 to set 2. Another example of a solution could be
{A2,B5,C10,D8,E1,F7,G6,H4,I9,J3}.
Before your first turn, you get to ask if a single, particular
pair of your choice is correct. Your question would be in the form
of {A1} (e.g. {C8}), and you receive either a 1 (meaning correct) or
0 (meaning your guess is incorrect).
Your first actual turn. You make your first guess in the form of
{A1,B2,C3,D4,E5,F6,G7,H8,I9,J10}, or any permutation of your choice.
Your guess cannot contain multiples of any item i.e. a guess of {A1,A2,A3,A4,A5,B6,B7,B8,B9,B10} is NOT a valid guess. After each
turn, the computer tells you the number of correct matches, but
NOT which matches are correct.
Repeat steps 3 and 4 until you get every match correct (i.e. a
response of 10), or until your 10 moves are up (whichever is
sooner). If you solve it before or on your 10th turn, you win $1
million. Otherwise, you lose, and some people (or letters and
numbers) go home alone to spend eternity with their 10 cats.


This is NOT a shortest code contest. The person who can solve a random matching in the least average number of guesses will be the winner. Clever game playing and calculation speed will also likely factor in. I am assuming the average number of turns will almost certainly be greater than 10, so the odds of you winning the $1 million prize (presumably paid by MTV, not me) is slim. Just how impossible is it for the cast to win the grand prize?

Note: Putting it in the {A1, B2, ...} format is not necessarily required. I simply used that form in the question to make it absolutely clear what the puzzle is. If you do not put it in this form, please just explain how to call it.

Good luck!
Python 2 (run faster if run using Pypy)

Believed to almost always guess the correct pairing in 10 rounds or lower

My algorithm is taken from my answer for mastermind as my hobby (see in Ideone). The idea is to find the guess which minimize the number of possibilities left in the worst case. My algorithm below just brute force it, but to save time, it just pick random guess if the number of possibilities left is larger than RANDOM_THRESHOLD. You can play around with this parameter to speed things up or to see better performance.

The algorithm is quite slow, on average 10s for one run if run using Pypy (if using normal CPython interpreter it's around 30s) so I can't test it on the whole permutations. But the performance is quite good, after around 30 tests I haven't seen any instance where it can't find the correct pairing in 10 rounds or lower.

Anyway, if this is used in real life show, it has plenty of time before the next round (one week?) so this algorithm can be used in real life =D

So I think it's safe to assume that on average this will find the correct pairings in 10 guesses or lower.

Try it yourself. I might improve the speed in the next few days (EDIT: it seems difficult to further improve, so I'll just leave the code as is. I tried only doing random pick, but even at size=7, it fails in 3 of the 5040 cases, so I decided to keep the cleverer method). You can run it as:

pypy are_you_the_one.py 10


Or, if you just want to see how it works, input smaller number (so that it runs faster)

To run a full test (warning: it'll take very long for size > 7), put a negative number.

Full test for size=7 (completed in 2m 32s):


...
(6, 5, 4, 1, 3, 2, 0): 5 guesses
(6, 5, 4, 2, 0, 1, 3): 5 guesses
(6, 5, 4, 2, 0, 3, 1): 4 guesses
(6, 5, 4, 2, 1, 0, 3): 5 guesses
(6, 5, 4, 2, 1, 3, 0): 6 guesses
(6, 5, 4, 2, 3, 0, 1): 6 guesses
(6, 5, 4, 2, 3, 1, 0): 6 guesses
(6, 5, 4, 3, 0, 1, 2): 6 guesses
(6, 5, 4, 3, 0, 2, 1): 3 guesses
(6, 5, 4, 3, 1, 0, 2): 7 guesses
(6, 5, 4, 3, 1, 2, 0): 7 guesses
(6, 5, 4, 3, 2, 0, 1): 4 guesses
(6, 5, 4, 3, 2, 1, 0): 7 guesses
Average count: 5.05
Max count    : 7
Min count    : 1
Num success  : 5040


If RANDOM_THRESHOLD and CLEVER_THRESHOLD are both set to a very high value (like 50000), it'll force the algorithm to find the optimal guess that minimizes the number of possibilities in the worst case. This is very slow, but very powerful. For example, running it on size=6 asserts that it can find the correct pairings in maximum 5 rounds.

Although the average is higher compared to using the approximation (which is 4.11 rounds on average), but it always succeeds, even more with one round left to spare. This further strengthen our hypothesis that when size=10, it should almost always find the correct pairings in 10 rounds or less.

The result (completed in 3m 9s):


(5, 4, 2, 1, 0, 3): 5 guesses
(5, 4, 2, 1, 3, 0): 5 guesses
(5, 4, 2, 3, 0, 1): 4 guesses
(5, 4, 2, 3, 1, 0): 4 guesses
(5, 4, 3, 0, 1, 2): 5 guesses
(5, 4, 3, 0, 2, 1): 5 guesses
(5, 4, 3, 1, 0, 2): 5 guesses
(5, 4, 3, 1, 2, 0): 5 guesses
(5, 4, 3, 2, 0, 1): 5 guesses
(5, 4, 3, 2, 1, 0): 5 guesses
Average count: 4.41
Max count    : 5
Min count    : 1
Num success  : 720


The code.

from itertools import permutations, combinations
import random, sys
from collections import Counter

INTERACTIVE = False
ORIG_PERMS = []
RANDOM_THRESHOLD = 100
CLEVER_THRESHOLD = 0

class Unbuffered():
    def __init__(self, stream):
        self.stream = stream

    def write(self, data):
        self.stream.write(data)
        self.stream.flush()

    def __getattr__(self, attr):
        self.stream.getattr(attr)
sys.stdout = Unbuffered(sys.stdout)

def init(size):
    global ORIG_PERMS
    ORIG_PERMS = list(permutations(range(size)))

def evaluate(solution, guess):
    if len(guess) == len(solution):
        cor = 0
        for sol, gss in zip(solution, guess):
            if sol == gss:
                cor += 1
        return cor
    else:
        return 1 if solution[guess[0]] == guess[1] else 0

def remove_perms(perms, evaluation, guess):
    return [perm for perm in perms if evaluate(perm, guess)==evaluation]

def guess_one(possible_perms, guessed_all, count):
    if count == 1:
        return (0,0)
    pairs = Counter()
    for perm in possible_perms:
        for pair in enumerate(perm):
            pairs[pair] += 1
    perm_cnt = len(possible_perms)
    return sorted(pairs.items(), key=lambda x: (abs(perm_cnt-x[1]) if x[1]&lt;perm_cnt else perm_cnt,x[0]) )[0][0]

def guess_all(possible_perms, guessed_all, count):
    size = len(possible_perms[0])
    if count == 1:
        fact = 1
        for i in range(2, size):
            fact *= i
        if len(possible_perms) == fact:
            return tuple(range(size))
        else:
            return tuple([1,0]+range(2,size))
    if len(possible_perms) == 1:
        return possible_perms[0]
    if count &lt; size and len(possible_perms) &gt; RANDOM_THRESHOLD:
        return possible_perms[random.randint(0, len(possible_perms)-1)]
    elif count == size or len(possible_perms) &gt; CLEVER_THRESHOLD:
        (_, next_guess) = min((max(((len(remove_perms(possible_perms, evaluation, next_guess)), next_guess) for evaluation in range(len(next_guess))), key=lambda x: x[0])
                               for next_guess in possible_perms if next_guess not in guessed_all), key=lambda x: x[0])
        return next_guess
    else:
        (_, next_guess) = min((max(((len(remove_perms(possible_perms, evaluation, next_guess)), next_guess) for evaluation in range(len(next_guess))), key=lambda x: x[0])
                               for next_guess in ORIG_PERMS if next_guess not in guessed_all), key=lambda x: x[0])
        return next_guess

def main(size=4):
    if size &lt; 0:
        size = -size
        init(size)
        counts = []
        for solution in ORIG_PERMS:
            count = run_one(solution, False)
            counts.append(count)
            print '%s: %d guesses' % (solution, count)
        sum_count = float(sum(counts))
        print 'Average count: %.2f' % (sum_count/len(counts))
        print 'Max count    : %d' % max(counts)
        print 'Min count    : %d' % min(counts)
        print 'Num success  : %d' % sum(1 for count in counts if count &lt;= size)
    else:
        init(size)
        solution = ORIG_PERMS[random.randint(0,len(ORIG_PERMS)-1)]
        run_one(solution, True)

def run_one(solution, should_print):
    if should_print:
        print solution
    size = len(solution)
    cur_guess = None
    possible_perms = list(ORIG_PERMS)
    count = 0
    guessed_one = []
    guessed_all = []
    while True:
        count += 1
        # Round A, guess one pair
        if should_print:
            print 'Round %dA' % count
        if should_print:
            print 'Num of possibilities: %d' % len(possible_perms)
        cur_guess = guess_one(possible_perms, guessed_all, count)
        if should_print:
            print 'Guess: %s' % str(cur_guess)
        if INTERACTIVE:
            evaluation = int(raw_input('Number of correct pairs: '))
        else:
            evaluation = evaluate(solution, cur_guess)
            if should_print:
                print 'Evaluation: %s' % str(evaluation)
        possible_perms = remove_perms(possible_perms, evaluation, cur_guess)

        # Round B, guess all pairs
        if should_print:
            print 'Round %dB' % count
            print 'Num of possibilities: %d' % len(possible_perms)
        cur_guess = guess_all(possible_perms, guessed_all, count)
        if should_print:
            print 'Guess: %s' % str(cur_guess)
        guessed_all.append(cur_guess)
        if INTERACTIVE:
            evaluation = int(raw_input('Number of correct pairs: '))
        else:
            evaluation = evaluate(solution, cur_guess)
            if should_print: print 'Evaluation: %s' % str(evaluation)
        if evaluation == size:
            if should_print:
                print 'Found %s in %d guesses' % (str(cur_guess), count)
            else:
                return count
            break
        possible_perms = remove_perms(possible_perms, evaluation, cur_guess)

if __name__=='__main__':
    size = 4
    if len(sys.argv) &gt;= 2:
        size = int(sys.argv[1])
        if len(sys.argv) &gt;= 3:
            INTERACTIVE = bool(int(sys.argv[2]))
    main(size)