源于《三個變態(tài)的循環(huán)》第一題

原文鏈接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也決定不去。
那么最后究竟有哪幾個人參加了會議呢？

題外話

最開始在上面的原文論壇回答一個小伙伴的提問，后來換了幾家公司原代碼已經(jīng)找不到了，下面的代碼是之后整理過的代碼。今年2月份的時候在CSDN博客上看到被人收集并且標記為原創(chuàng)，感覺自己的東西被人偷去了一樣難受，于是又整理了一份。

推理

從4，5兩個條件出發(fā)A，D互斥同時C，D互斥（當然這里有一定歧義，只要1人參加可以理解為必須選1人參加或者理解為要么1人參加要么兩個都不參加，因為這里沒有強調(diào)必須去。）

• 假設(shè)D參加，那么A，C不參加，根據(jù)條件(1)B就必須參加 得到BD
  再根據(jù)條件(3)要求BC要么同去要么同不去，所以C也必須去，得到BCD，與條件(5)相矛盾，所以D是肯定無緣參加了。
• D不參加根據(jù)條件(6)得到E也不參加， 那么條件(2)中AEF就排除掉E 得到AF
• 回到上面提的歧義，如果理解為后一種的話那AF可以滿足所有條件， 如果理解為前一種的話D不參加C就必須參加 得到ACF， 再回到條件(3)可知B也必須去 最終得到ABCF
• 那么最終的人選是ABCF 或者再算上歧義的結(jié)果AF

轉(zhuǎn)換成程序的基本思路是找出6人所有可能的組合，然后根據(jù)1~6這6個條件一個一個判斷是否滿足，找出完全滿足條件的組合即可。應(yīng)該也有更好的思路不用進行組合，先假定6人都去然后再根據(jù)條件進行排除。

1. 獲取所有組合
   得到A，B，C，D，E，F(xiàn)，AB，AC，AD，AE，AF...ABCDEF這樣的全組合，可以使用遞歸法(回溯)，也可以使用一維數(shù)組。
   下面是使用一維數(shù)組的方法。

    /**
     * 組合不排列
     * @param items
     * @return 數(shù)組中所有可能的組合
     */
    public static String[] combination(String[] items) {
        int n = items.length, index = 0, _n = n;
        // 每個人都有兩種狀態(tài),要么去,要么不去所以總共的組合就有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;
    }

2. 得到組合遍歷每個組合判斷是否全部滿足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;
    }

后來整理的時候發(fā)現(xiàn)這些判斷有很多冗余，比如分支1，2，4都有str.contains("A")，就想辦法把它們提出去只調(diào)有一次，判斷也可以演化為邏輯運算，比如條件(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;
    }

改為之后發(fā)現(xiàn)為何不將非判斷改為與判斷呢？這樣就可以將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函數(shù)就可以運行了。

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);
            }
        }
    }

當然，運行結(jié)果與上面推論的一樣，

下一個目標是不拉出所有組合直接處理。