直接使用穷举法不是一个好的想法，排列数为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
注意：
- 关键点：分治法（并且取消重复计算）、集合表示。
- 如果目标只要一种计算方法，那么计算过程中，如果计算得到相同的结果，其实只要记录一个即可，这样也达到减枝减少计算的效果。
按照该思路写的一个例程：
#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;
};