solution.py

from __future__ import print_function
import random, itertools, sets

## The following represents thought process and has not been subjected to rigorus proof
# Possible pairings can be represented as two varieties of cycles in the permutations of the residents due to the restriction on reflexive pairings. 
# For each permutation there is a single cycle through all 7 name and a two disjoint cycles through 3 names and 4 names respectively.
# Total unique pairings are therefore less than 7!*2 = 10080 (less because cycles of a particular permutation generate equivalent pairings)
# There are 7! permutations. Cycles through all 7 that produce equivalent pairings can be elminiated by considering only permutations that begin with a particular digit (eg. 6).
# Therefore unique pairings for cycles through all 7 generates 6! = 720  (ie 7!/7) pairings.
# Considering 3,4 cycles inside of each permutation there should be (7!/(4!*3))(4!/4) = 420
# accounting for equivalent pairings we are left with 720+420 = 1140 possible pairings

# Maximum bound on years before a repeated pair must be 6 because for any individual there are only 6 possible partners.
# But testing shows that all possible partners can be exhausted in as little as 4 years.

def cycle_to_pairing(p):
    return zip(p,p[1:]+p[:1])
    
def cycle_7_pairing(p):
    return tuple(cycle_to_pairing(p))

def cycle_3_4_pairing(p):
    return tuple(cycle_to_pairing(p[:3]) + cycle_to_pairing(p[3:]))

def pairing_to_set(p):
    return sets.ImmutableSet(p)
    
def list_of_pairings_to_set(ps):
    pairs = []
    for p in ps:
        pairs.extend(list(p))
    return sets.ImmutableSet(pairs)

def filter_pairings(pp, pairs):
    return [p for p in pp if not p & pairs]

def pairing_to_string(p, names):
    lines = ['{0} is buying for {1}'.format(names[x[0]], names[x[1]]) for x in p]
    return '\n'.join(lines)

def generate_possible_pairings():
    '''calcuate all possible pairings using sets to eliminate equivalent pairings
    This is acceptable because there are only 7 residents as numbers increase an alternative
    strategy should be considered.
    '''
    residents = range(7)
    all_permutations = list(itertools.permutations(residents))
    possible_pairings = set([])
    for p in all_permutations:
        possible_pairings.add(pairing_to_set(cycle_7_pairing(p)))
        possible_pairings.add(pairing_to_set(cycle_3_4_pairing(p)))
    return list(possible_pairings)    

def pairing_distribution():
    '''count occurences of each pair among all pairings to be sure that the distribution is equal'''
    counter = {}
    for x in generate_possible_pairings():
        for y in list(x):
            if not y in counter:
                counter[y] = 0
            counter[y] += 1
    print(counter, len(counter))

def simulate_consecutive_years(n=100):
    '''runs a simulation of picking consecutive years to test theory about how long it is possible to go without repeats
    testing provides validation for 6 being the upper limit
    in approximately 10% of the tests the possiblites are eliminated after 4 years
    no smaller values have been observed'''
    all_counts = {}
    for i,x in enumerate(random.sample(generate_possible_pairings(),n)):
        print('\r'+str(i), end=' ')
        pp = generate_possible_pairings()
        counts = [len(pp)]
        while pp:
            pp = [a for a in pp if not a & x]
            if not len(pp):
                break
            counts.append(len(pp))
            x = random.choice(pp)
        counts = tuple(counts)
        counts = len(counts)
        if not counts in all_counts:
            all_counts[counts] = 0
        all_counts[counts] += 1
    print('')
    print(all_counts)

if __name__ == '__main__':

    history = 4
    resident_names = ['Buddy Holly','John Bonham','Elvis Presley','Kurt Cobain','Janis Joplin','Richie Valens','John Lennon']
    historical_pairings = [((0,2), (2,4), (4,6), (6,1), (1,3), (3,5), (5,0))]
    
    while True:
        historical_pairings = historical_pairings[-1*history:]
        filter = list_of_pairings_to_set(historical_pairings)
        remaining_pairings = filter_pairings(generate_possible_pairings(), filter)
        try:
            pairing = random.choice(remaining_pairings)
        except IndexError:
            print('All unique pairs have been exhausted!')
            break
        historical_pairings.append(pairing)
        print(pairing_to_string(pairing, resident_names))
        print('')
        if raw_input().upper() == 'Q':
            break