直接使用穷举法不是一个好的想法,排列数为N!,两两运算种类有 { a+b, a-b, b-a, a*b, a/b, b/a },为(N-1)^6,因此总计算量为N! * (N-1)^6,是指数级的运算。

能不能通过设计来减少计算量呢?

考虑分治策略,将大集合拆分为小集合运算再合并。

这样 f(A) = U Fork( f(A1), f(A-A1) ),其中A1是A的任何一个子集,Fork代表子集之间的运算,而整个集合A的结果就是所有子集间计算后的合并。

注意到,子集可能会出现重复,例如:

f {1, 2, 3, 4} = Fork(f {1}, f{2,3,4} ) U Fork( f{2}, f{1,3,4} ) U Fork( f{1,2}, f{3,4} ) U …

f{2,3,4} = Fork( f{2}, f{3,4} ) U …

可以看到计算过程中,存在很多相同的子集合的重复计算,因此我们可以记录下计算结果,以后可以通过查表的方式,没有计算过才计算。

那怎么表示集合呢?

注意到子集无非是某一个位置上的数有或者没有,恰好可以对应二进制中的1和0,因此将子集表示为二进制数非常适合。

如:
(a1, a2, a3, a4) -> 1111
(a1, a3, a4) -> 1011

注意:

  1. 关键点:分治法(并且取消重复计算)、集合表示。
  2. 如果目标只要一种计算方法,那么计算过程中,如果计算得到相同的结果,其实只要记录一个即可,这样也达到减枝减少计算的效果。

按照该思路写的一个例程:

#include <map>
#include <string>
#include <set>
#include <vector>
#include <boost/lexical_cast.hpp>
 
class Game24Points
{
public:
    Game24Points() : target_point(24)
    {
       memset( card, 0, sizeof(card) );
    }
 
    void SetCardVal( int v0, int v1, int v2, int v3 )
    {
       card[0] = v0;
       card[1] = v1;
       card[2] = v2;
       card[3] = v3;
 
      
       calcParts[ 1 << 3 ].insert( CalcPartsValueType(card[0], Type2Str( card[0] )) );
       calcParts[ 1 << 2 ].insert( CalcPartsValueType(card[1], Type2Str( card[1] )) );
       calcParts[ 1 << 1 ].insert( CalcPartsValueType(card[2], Type2Str( card[2] )) );
       calcParts[ 1 << 0 ].insert( CalcPartsValueType(card[3], Type2Str( card[3] )) );
    }
 
    void SetTargetPoint( int n )
    {
       target_point = n;
    }
 
    std::vector<std::string> GetAnswer()
    {
       std::vector<std::string> ret;
       Calc( sub_collection - 1 );
 
       typedef std::multimap<int, std::string>::iterator MapIter;
       std::pair<MapIter, MapIter> iterPair = 
       		calcParts[sub_collection - 1].equal_range( target_point );
       for ( MapIter it = iterPair.first; it != iterPair.second; ++it )
       {
           ret.push_back( it->second );
       }
       return ret;
    }
 
private:
    // 计算子集合的能计算得到的值
    void Calc( int sub_coll )
    {
       if ( sub_coll <= 0 || sub_coll >= sub_collection )
       {
           return;
       }
 
       if ( !calcParts[sub_coll].empty() )
       {
           return;
       }
 
       // 获得所有子集合
       std::set<int> setSubColl;
       int sub_coll_val = 0;
       GetSubColl( sub_coll, 0, sub_coll_val, setSubColl );
 
       // 子集合配对
       std::vector< std::pair<int, int> > subUnion;
       while ( !setSubColl.empty() )
       {
           std::set<int>::iterator iter = setSubColl.begin();
           int u1 = *iter;
           setSubColl.erase( iter );
 
           int u2 = sub_coll - u1;
           iter = setSubColl.find( u2 );
           if ( iter != setSubColl.end() )
           {
              subUnion.push_back( std::make_pair(u1, u2) );
              setSubColl.erase( iter );
           }
       }
 
       // 计算每一组配对的子集合,两个集合的值两两运算
       for ( int i=0; i<(int)subUnion.size(); ++i )
       {
           Calc( subUnion[i].first );
           Calc( subUnion[i].second );
 
           std::multimap<int, std::string>::iterator lhs_it 
           		= calcParts[subUnion[i].first].begin();
           for ( ; lhs_it != calcParts[subUnion[i].first].end(); ++lhs_it )
           {
              std::pair< const int, std::string > & lhs = *lhs_it;
              std::multimap<int, std::string>::iterator rhs_it 
              		= calcParts[subUnion[i].second].begin();              
              for ( ; rhs_it != calcParts[subUnion[i].second].end(); ++rhs_it )
              {
                  std::pair< const int, std::string > & rhs = *rhs_it;
                 
                  // +
                  int val = lhs.first + rhs.first;
                  std::string expr = std::string("( ")+lhs.second+ " + " +rhs.second+" )";
                  calcParts[ sub_coll ].insert( CalcPartsValueType(val, expr) );
                 
                  // -
                  val = lhs.first - rhs.first;
                  expr = std::string("( ") + lhs.second + " - " + rhs.second + " )";
                  calcParts[ sub_coll ].insert( CalcPartsValueType(val, expr) );
 
                  val = rhs.first - lhs.first;
                  expr = std::string("( ") + rhs.second + " - " + lhs.second + " )";
                  calcParts[ sub_coll ].insert( CalcPartsValueType(val, expr) );
 
                  // *
                  val = lhs.first * rhs.first;
                  expr = std::string("( ") + lhs.second + " * " + rhs.second + " )";
                  calcParts[ sub_coll ].insert( CalcPartsValueType(val, expr) );
 
                  // /
                  if ( rhs.first != 0 && (lhs.first % rhs.first == 0) )
                  {
                     val = lhs.first / rhs.first;
                     expr = std::string("( ") + lhs.second + " / " + rhs.second + " )";
                     calcParts[ sub_coll ].insert( CalcPartsValueType(val, expr) );
                  }
 
                  if ( lhs.first != 0 && (rhs.first % lhs.first == 0) )
                  {
                     val = rhs.first / lhs.first;
                     expr = std::string("( ") + rhs.second + " / " + lhs.second + " )";
                     calcParts[ sub_coll ].insert( CalcPartsValueType(val, expr) );
                  }
              }
           }
       }
    }
 
   
    void GetSubColl( int n, int step, int& val, std::set<int>& vec )
    {// n最大为二进制的
       if ( step == card_count )
       {
           if ( val != 0 && val != n )
           {
              vec.insert( val );
           }
           return;
       }
 
       int ibit = (1 << step);
       if ( n & ibit )
       {
           val |= ibit;
           GetSubColl(n, step+1, val, vec);
 
           val &= ~ibit;
           GetSubColl(n, step+1, val, vec);
       }
       else
       {
           GetSubColl(n, step+1, val, vec);
       }
    }
 
    template<typename T>
    std::string Type2Str( T const& t )
    {
        std::string ret;
       try
       {
           ret = boost::lexical_cast<std::string>(t);
       }
       catch (...)
       {
       }
       return ret;
    }
 
private:
    // 纸牌数目
    static const int card_count        = 4;
    // 子集合的个数,包括(0000)和(1111)
    static const int sub_collection    = (1 << card_count);
 
    int target_point;
 
    // 纸牌的值: 1 ~ 13
    int                             card[card_count];
   
	// 记录各个子集合的值~sub_collection-1,使用map来代替multimap则可以减枝加速
    std::multimap<int, std::string>    calcParts[sub_collection];
    typedef std::multimap<int, std::string>::value_type CalcPartsValueType;
};