Форум программистов [Powered by Invision Power Board]

Код

def test_algo( tests, index = None):
    if not index:
        for index, test in enumerate( tests ):
            print '#', index, ' ======================'
            print 'Solving: ', test
            print 'Result:  ', algo( copy.deepcopy( test ) )
            print '==========================='
    else:
        print '#', index, ' ======================'
        print 'Solving: ', tests[ index ]
        print 'Result:  ', algo( copy.deepcopy( tests[ index ] ) )
        print '==========================='
    
def algo_group( flat_test, test ):
    group = dict( ( key, [] ) for key in flat_test )
    for index, test_group in enumerate( test ):
        for key in test_group:
            group[ key ].append( index )
    return group

def remove_duplicates( test ):
    seen     = set()
    seen_add = seen.add
    return [ x for x in test if not ( x in seen or seen_add( x ) ) ]
            
def remove_group_duplicates( test ):
    for test_group in test:
        remove_duplicates( test_group )
        
def has_empty( output ):
    for group in output:
        if not len( group ):
            return True
    return False

def has_unique( group ):
    for length in group.values():
        if len( length ) == 1:
            return True
    return False
    
def add_unique( output, group ):
    keys = group.keys()
    for key in keys:
        if len( group[ key ] ) == 1:
            group_index = group[ key ][0]
            output[ group_index ].append( key )
            del group[ key ]
            for groups in group.values():
                if len( groups ) > 1 and group_index in groups:
                    groups.remove( group_index )
            
def add_loop( output, test, group ):
    temp_test  = copy.deepcopy( test )
    temp_group = copy.deepcopy( group )

    path = find_loop( temp_test, temp_group, [], 0 )
    if path == 'False':
        raise 'Cannot find solution'
    else:
        for out_group, key in path:
            output[ out_group ].append( key )
            for groups in group.values():
                if len( groups ) > 1 and out_group in groups:
                    groups.remove( out_group )
    
def find_loop( test, group, path, index ):
    test_indices = test[ index ]
    for key in test_indices:
        test[ index ].remove( key )
        group[ key ].remove( index )
        indices = group[ key ]
        for group_index in indices:
            if not key in test[ group_index ]:
                continue
            test[ group_index ].remove( key )
            path.append( ( group_index, key ) )
            if group_index == 0:
                return path
            else:
                result = find_loop( test, group, path, group_index )
                if result != False:
                    return result
            path.remove( ( group_index, key ) )
            test[ group_index ].append( key )
        group[ key ].append( index )
        test[ index ].append( key )
    return False
        
def algo( test ):
    remove_group_duplicates( test )
    
    flat_test = sum( test, [] )
    group      = algo_group( flat_test, test )
    
    output    = [ [] for _ in xrange( len( test ) ) ]
    while has_empty( output ):
        while has_unique( group ):
            add_unique( output, group )
        if has_empty( output ):
            add_loop( output, test, group )
            
    final_output = [ [] for _ in xrange( len( test ) ) ]
    group = algo_group( flat_test, test )
    for index, test_group in enumerate( test ):
        for key in test_group:
            if key in output[ index ] and ( len( group[ key ] ) == 1 or len( final_output[ index ] ) == 0 ):
                final_output[ index ].append( key )
        
    return final_output