源于《三个变态的循环》第一题
原文链接http://www.cn-java.com/www1/bbs/viewthread.php?tid=93104&extra=page=1
参加会议:有人邀请A,B,C,D,E,F6个人参加一项会议，这6个人有些奇怪，因为他们有很多要求，已知：
(1).A,B两人至少有1人参加会议。
(2).A,E,F 3人中有2人参加会议。
(3).B和C两人一致决定，要么两人都去，要么两人都不去。
(4).A,D两人中只1人参加会议。
(5).C,D两人中也只要1人参加会议。
(6).如果D不去，那么E也决定不去。
那么最后究竟有哪几个人参加了会议呢？
题外话
最开始在上面的原文论坛回答一个小伙伴的提问，后来换了几家公司原代码已经找不到了，下面的代码是之后整理过的代码。今年2月份的时候在CSDN博客上看到被人收集并且标记为原创，感觉自己的东西被人偷去了一样难受，于是又整理了一份。
推理
从4，5两个条件出发A，D互斥同时C，D互斥（当然这里有一定歧义，只要1人参加可以理解为必须选1人参加或者理解为要么1人参加要么两个都不参加，因为这里没有强调必须去。）
- 假设D参加，那么A，C不参加，根据条件(1)B就必须参加 得到BD
再根据条件(3)要求BC要么同去要么同不去，所以C也必须去，得到BCD，与条件(5)相矛盾，所以D是肯定无缘参加了。 - D不参加根据条件(6)得到E也不参加， 那么条件(2)中AEF就排除掉E 得到AF
- 回到上面提的歧义，如果理解为后一种的话那AF可以满足所有条件， 如果理解为前一种的话D不参加C就必须参加 得到ACF， 再回到条件(3)可知B也必须去 最终得到ABCF
- 那么最终的人选是ABCF 或者再算上歧义的结果AF
转换成程序的基本思路是找出6人所有可能的组合，然后根据1~6这6个条件一个一个判断是否满足，找出完全满足条件的组合即可。应该也有更好的思路不用进行组合，先假定6人都去然后再根据条件进行排除。
- 获取所有组合
得到A，B，C，D，E，F，AB，AC，AD，AE，AF...ABCDEF这样的全组合，可以使用递归法(回溯)，也可以使用一维数组。
下面是使用一维数组的方法。
/**
* 组合不排列
* @param items
* @return 数组中所有可能的组合
*/
public static String[] combination(String[] items) {
int n = items.length, index = 0, _n = n;
// 每个人都有两种状态,要么去,要么不去所以总共的组合就有2^6,
// 但是全部不去这种组合没有意义要去掉
String[] comb = new String[(1 << n) - 1];
System.arraycopy(items, 0, comb, 0, n);
while (++index < n) {
int j = _n;
for (int s = 0, len = n - index; s < len; s++) {
for (int ss = (j - count(n - s - 1, index)); ss < j; ss++) {
comb[_n++] = comb[s] + comb[ss]; // 最好使用StringBuilder
}
}
}
return comb;
}
protected static int count(int p, int c) {
if (p < c) return 0;
if (p == c) return 1;
if (c > p >> 1) c = p - c;
int _p = 1, _c = 1;
for (int i = p, size = (p - c); i > size; i--) _p *= i;
for (int i = 2; i <= c; i++) _c *= i;
return _p / _c;
}
- 得到组合遍历每个组合判断是否全部满足6个条件
最初版是这样子
boolean match(String str) {
// (1).A,B两人至少有1人参加会议。
if (!str.contains("A") && !str.contains("B")) {
return false;
}
// (2).A,E,F3人中有2人参加会议。
if (!((str.contains("A") && str.contains("E"))
|| (str.contains("A") && str.contains("F"))
|| (str.contains("E") && str.contains("F")))) {
return false;
}
// (3).B和C两人一致决定，要么两人都去，要么两人都不去。
if ((str.contains("B") && !str.contains("C"))
|| (!str.contains("B") && str.contains("C"))) {
return false;
}
// (4).A,D两人中只1人参加会议。
if (str.contains("A") && str.contains("D")) {
return false;
}
// (5).C,D两人中也只要1人参加会议。mark: 这里并没有说C,D必须有一人参加
if (str.contains("C") && str.contains("D")) {
return false;
}
// (6).如果D不去，那么E也决定不去。
if (!str.contains("D") && str.contains("E")) {
return false;
}
return true;
}
后来整理的时候发现这些判断有很多冗余，比如分支1，2，4都有str.contains("A")，就想办法把它们提出去只调有一次，判断也可以演化为逻辑运算，比如条件(1)A，B至少1人参加可以改为(a|b) == 1，于是就有了一个改版
boolean match1(String str) {
// 每个人两个信号量1：去，0：不去
int a = str.indexOf('A') > -1 ? 1 : 0
, b = str.indexOf('B') > -1 ? 1 : 0
, c = str.indexOf('C') > -1 ? 1 : 0
, d = str.indexOf('D') > -1 ? 1 : 0
, e = str.indexOf('E') > -1 ? 1 : 0
, f = str.indexOf('F') > -1 ? 1 : 0;
// (1).A,B两人至少有1人参加会议。
if ((a | b) == 0) {
return false;
}
// (2).A,E,F3人中有2人参加会议。
if ((a & e | a & f | e & f) == 0) {
return false;
}
// (3).B和C两人一致决定，要么两人都去，要么两人都不去。
if ((b ^ c) == 1) {
return false;
}
// (4).A,D两人中只1人参加会议。
if ((a & d) == 1) {
return false;
}
// (5).C,D两人中也只要1人参加会议。
if ((c & d) == 1) {
return false;
}
// (6).如果D不去，那么E也决定不去。
if ((~d & e) == 1) {
return false;
}
return true;
}
改为之后发现为何不将非判断改为与判断呢？这样就可以将6个if判断合并为1个判断，最终改为了下面的形式
boolean match2(String str) {
int a = str.indexOf('A') > -1 ? 1 : 0
, b = str.indexOf('B') > -1 ? 1 : 0
, c = str.indexOf('C') > -1 ? 1 : 0
, d = str.indexOf('D') > -1 ? 1 : 0
, e = str.indexOf('E') > -1 ? 1 : 0
, f = str.indexOf('F') > -1 ? 1 : 0;
return ((a | b) // (1).A,B两人至少有1人参加会议。
& (a & e | a & f | e & f) // (2).A,E,F3人中有2人参加会议。
& ~(b ^ c) // (3).B和C两人一致决定，要么两人都去，要么两人都不去。
& ~(a & d) // (4).A,D两人中只1人参加会议。必须去一个就改为 & (a ^ d)
& ~(c & d) // (5).C,D两人中也只要1人参加会议。必须去一个就改为 & (c ^ d)
& ~(~d & e) // (6).如果D不去，那么E也决定不去。
) == 1;
}
最后只需要一个main函数就可以运行了。
public static void main(String[] args) {
// 得到6个人所有的组合
String[] list = combination(new String[] {"A", "B", "C", "D", "E", "F"});
// 判断每种组合是否满足所有的条件
for (String str : list) {
if (match2(str)) {
System.out.println(str);
}
}
}
当然，运行结果与上面推论的一样，
下一个目标是不拉出所有组合直接处理。
网友评论