四根长度为3、两根长度为4、四根长度为7的木棍能围成多少种不同的矩形

问题

四根长度为3、两根长度为4、四根长度为7的木棍能围成多少种不同的矩形。无需每次用完所有木棍。

如果一个矩形经过一系列的如下操作，能得到另一个矩形，则认为这两个矩形相同（同构）：上下翻转、左右翻转、旋转、交换构成矩形的同一条边的几根木棍的顺序。

分析

深度优先搜索。由于共有10根木棍，所以搜索的深度为10。每根木棍穷举其5种状态（0表示没用到这根木棍，1到4表示这根木棍属于矩形的第1到4条边）。穷举空间是5^10=9,765,625，不大，所以中间没有剪枝。

解的消重方法

将构成矩形的4条边的所有木棍按长度递增排序，保证这个序列不重复即可。一条边的尾数和另一条边之间的首数之间要插入一个分隔符’-‘。
先将矩形的4条边按边长递增排序，再将每条边内部的木棍按长度递增排序即可。
假定矩形的四条边依次为e1、e2、e3、e4，其中e1和e3是对边，e2和e4是对边。注意对边的长度相等。
一、如果矩形不是正方形，先将短的两条对边a、b排在前面，长的两条对边c、d在后。
a和b谁在前面，取决于a、b内的最短木棍、最长木棍的长度。也就是按a、b中的各个木棍在数轴上的左右顺序来决定a、b的前后顺序。
比较a、b的Compare()函数的逻辑如下：
1、如果a拥有a和b中最短的那个木棍，那么a在前。因为最短木棍在数轴最左侧。
2、如果a拥有a和b中最长的那个木棍，那么b在前。因为最长木棍在数轴最右侧。
3、如果a、b都拥有最短木棍、最长木棍，那么比较a、b各自拥有的的木棍个数。实际上就是比较a、b各自的单根木棍的平均长度，因为a、b的长度相等。
由于题目中的数字的特殊性，a、b的平均长度相等时，a、b包含的木棍集合也是相同的。代码中用断言验证了这点。
如果题目中的条件换成其他数字，并不一定能保证这点。
c和d谁在前，是类似的。
二、如果矩形是正方形，那么四条边要统一进行排序。排序的原则类似上面a、b进行比较。

实现代码：https://github.com/z16166/CountSquare

和之前搞的计算24点的穷举差不多：https://github.com/z16166/Calc24

原文地址：http://www.cnblogs.com/z16166/p/16927169.html