------art_21188_20244148.1212960079726
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

I have a solution at the end of this message.  This solution finds the
optimal solution.  I believe this problem is NP-complete, so a fast optimal
solution for large inputs is out of the question.  But, there are some
things that I did that give significant performance improvement:

* Used memoization to not recalculate costs for subsets that have already
been computed.  This reduced the complexity from O(n!) to O(2**n).

* Divided finding the pairs into 2 phases: finding min cost, and finding
pairs based on min costs.  This simplified the bottleneck of finding the min
cost and reduced its overhead.  Given the min costs, the pairs can be found
in O(n**2).

* Mapped each player to a bit index/mask.  This allowed a set of players to
be represented as simply an Integer/Fixnum.

* Applied some O(1) bit-searching techniques I developed about 10 years ago
on the hardware side (x86 BSR - bit-scan-reverse).

* No small objects are created (and garbage collected) during the algorithm.

Eric

#!/usr/bin/env ruby

Infinity  .0/0.0

class PreferrablePairs

    def initialize
        # remaining bit pattern cost (init to no remaining 0)
        # size will be O(2**n)
        # only patterns with an even number of bits set will be used
        @cost  0]
        #@cost  0} # Hash could be used just as well (little slower)
        @mask   # next mask to use
        # mask <name maps
        @mask2name  }
        @name2mask  ash.new { |name2mask, name|
            # create a new entry when it is missing
            begin
                @mask2name[@mask]  ame
                name2mask[name]  mask
            ensure
                # post operation
                @mask << 
            end
        }
    end

    # throw out all cached costs - for more than just pairs
    # O(2**n)
    def flush
        @mask.times { |rem|
            # little trick for masking lowest bit set (applied twice)
            rem2  em&(rem-1)
            rem2  em2&(rem2-1)
            next if rem2.zero? # 2 or fewer bits of mask set
            @cost[rem]  il
        }
    end

    # add a cost between a pair
    def add(first, second, cost)
        mask  name2mask[first]|@name2mask[second]
        @cost[mask]  @cost[mask]||0)+cost
    end

    # fill-in default costs for unassociated pairs
    # ensure we have an even number of entries
    def fill(defcost evenname, evencost
        mask1  
        while mask1<@mask
            mask2  ask1<<1
            while mask2<@mask
                @cost[mask1|mask2] || efcost
                mask2 << 
            end
            mask1 << 
        end
        if (@name2mask.size&1).nonzero?
            # add another entry when we have an odd number
            mask2  name2mask[evenname]
            mask1  
            while mask1<@mask
                @cost[mask1|mask2] || vencost
                mask1 << 
            end
        end
    end

    # cost for a remaining set of entries
    # O(2**n) if @cost is not cached (n ゥ
    」 マィェェイゥ  タ  
    」 マィ。ォゥ    
     ィュアゥ
          
        」      
        ア  
        」         ア
         ィア  ヲィュアゥゥョソ
            ア  ヲア 」    
            イ  ア
             ィイ  アヲィアュイゥゥョソ
                イ  アヲイ 」    
                」      ォ    
                」      ィ      ゥ
                  ロアイン ォ ィタロインィイゥゥ
                」    
                 シ
                      
                
                イ シシ 
            
            ア シシ 
        
        
    

    」    
    」         
    」   
    」 マィェェイゥ ッ 
    」 マィ。ォゥ ッ 
     ィャ ュアゥ 」 ココ ャ 
         ィア  ヲィュアゥゥョソ
            ア  ヲア
            イ  ア
             ィイ  アヲィアュイゥゥョソ
                」 タロョョョン ィタロョョョンィョョョゥゥ   
                
ィー
ロー
アインゥォタロアヲイン
                    」    
                    ィタイロアンャ タイロインゥ
                     ュ ー
                     ヲ ー
                    
                
                イ シシ 
            
        
    



 ァァ

  ミョ
  モョィ「「ゥ

モヤトノホョ゜  
    ョ  
    ョィッワェッゥ
      ョィッワォッゥ  
    ョィッワェワコッゥ  
      
     ョィッワェッゥ    ョィッワォッゥ
        ョィャ ャ ェゥ
         ォ 
    

ョ

 ァァ

  
  

エョ 
    ツョ  
          「
        ョ 
              ョ
            ョィゥ  ャ 
                ョィ「」 」ワ「ゥ
            
        
        ョ
    


モヤトナメメョィゥ
ィゥ

ュュュュュュ゜イアアクク゜イーイエエアエクョアイアイケカーーキケキイカュュ