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

On 6/8/08, Eric Mahurin <eric.mahurin / gmail.com> wrote:
>
> 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.


I improved on this solution further:

* The outer loop in #cost was unnecessary.  I believe the complexity before
was actually O(n*n*2**n) and now it should be O(n*2**n).

* Used Hash instead of Array for costs.  Not sure why this helped (Array was
faster in previous solution).

The new solution is below.  My previous solution could only reasonably
handle about 16 players and the new solution handles about 26 players.

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] # Array
        @cost  0} # Hash seems faster and takes less memory
        @mask   # next mask to use
        # mask <name maps
        @mask2name  }
        @name2mask  ash.new { |name2mask, name|
            # create a new player 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
        if @cost.respond_to?(:map!)
            # Array
            rem  1
            @cost.map! { |cost|
                rem + 
                cost ? (((rem2ヲィュアゥゥヲィイュアゥゥョソ ソ  コ ゥ コ

            
        
            」 ネ
            タョ゜  ャ 
                ィィイヲィュアゥゥヲィイュアゥゥョソ
            
        
    

    」      
     ィャ ャ ゥ
          イロンタイロン
        タロン  タロンーゥォ
    

    」        
     ィャ 
         ィタイョヲアゥョソ
            」         
            イ  イロン
            ア  
             アシタ
                タロアイン  
                ア シシ 
            
        
    

    」 ュ     
     ィ ャ 
        ア  
         アシタ
            イ  アシシア
             イシタ
                タロアイン  
                イ シシ 
            
            ア シシ 
        
    

    」       
    」 マィェイェェゥ  タ    ィ ゥ
    」 マィゥ  タ  
     ィュアゥ
          
        」       
        ア  ヲィュアゥ
        ア  ゛ア 」    
        イ  ア
        」         ア
         ィイ  ヲィュィイシシアゥゥゥョソ
            」      ォ    
              ロアイン ォ ィタロイア゛インィイゥゥ
            」    
                シ
        
        タロン  
    

    」    
    」      
    」   
    」 マィェェイゥ
     ィュアゥ 」 ココ ャ 
          ロン
         ィア  ヲィュアゥゥョソ
            イ  ア
            
                イ  ヲィュィイシシアゥゥ
             

ィー
ロー
アインゥォタロ゛ーン
            」    
            ィタイロアンャ タイロインゥ
             ュ ー
             ゛ ー
        
    



 ァァ

  ミョ
  モョィ「「ゥ

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

ョ
ョ 」       

 ァァ

  
  

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


モヤトナメメョィゥ
ィゥ

ュュュュュュ゜イイエウケ゜イキアカケカケキョアイアイケククウウカオウカュュ