[注：Image by Dave Francis from Pixabay]

题目

有 A, B, C, D 和 E 共5个运动员，在一次比赛中，已知E肯定不是第二名或第三名，他们相互进行推测：
A 说，E 一定是第一名；
B 说，我是第二名；
C 说，A 是最后一名；
D 说，C 不是第一名；
E 说，D 是第一名；
结果只有实际排名第一和第二名的运动员猜对了，其他人都猜错了。
请编写一个程序，求出这5个运动员的名次。

这个问题的常规思路其实很简单，把所有情况排列组合，有顺序，一共

种情况，再遍历校验条件是否符合。所以，难点在于，怎么用编程实现这个排列组合。

解法一：投机取巧+粗暴遍历

/**
 * 排列组合问题可以用二叉树来简单描述
 * 思路：创建二叉树，遍历二叉树，条件校验
 */
const origin = ["A", "B", "C", "D", "E"];
let output = [];
for (let i = 12345; i <= 54321; i++) {
    // TODO
    // 可以优化成寻找下一个比 12345 大的排列组合
    const temp = [Math.floor(i / 10000), Math.floor(i / 1000 % 10), Math.floor(i / 100 % 10), Math.floor(i / 10 % 10), i % 10];
    if (isValid(temp)) {
        // 校验
        check(temp);
    } else {
        continue;
    }
}
console.log(output);

function check(members) {
    if (members[1] === 5 || members[2] === 5) {
        return;
    }
    const list = [members[0] === 5, members[1] === 2, members[4] === 1, members[0] !== 3, members[0] === 4];
    if (list[members[0] - 1] && list[members[1] - 1] && !list[members[2] - 1] && !list[members[3] - 1] && !list[members[4] - 1]) {
        const res = [];
        members.forEach(x => {
            res.push(origin[x - 1]);
        })
        output.push(res);
    }
}

function isValid(arr) {
    let hash = {};
    for (let i in arr) {
        if (hash[arr[i]] || arr[i] > 5 || arr[i] === 0) {
            return false;
        }
        hash[arr[i]] = true;
    }
    return true;
}

解法二：根据推论去反校验

假设都对，推互斥

function genPermutations(arr) {
    const result = [];

    function innerArr(temArr) {
        for (let i = 0, len = arr.length; i < len; i++) {
            if (temArr.length == len - 1) {
                if (temArr.indexOf(arr[i]) < 0) {
                    result.push(temArr.concat(arr[i]));
                }
                continue;
            }
            if (temArr.indexOf(arr[i]) < 0) {
                innerArr(temArr.concat(arr[i]));
            }
        }
    }
    innerArr([]);
    return result;
}

var permutations = genPermutations([1, 2, 3, 4, 5])

function answer(arr, fun) {
    // 已知E肯定不是第二名或第三名
    arr = arr.filter(n => n[4] !== 2 && n[4] !== 3);
    const result = arr.filter(fun)
    if (result.length === 1) {
        console.log("正确答案为", result);
    } else {
        console.log("错误猜想");
    }
}

// 第一种组合
// A说，E一定是第一名；=> E = 1，A = 2 D = 1,
answer(permutations, n => n[4] == 1 && n[0] == 2 && n[3] == 1)


// 第二种组合
// E说，D是第一名; => E = 2, D = 1,
answer(permutations, n => n[4] == 2 && n[3] == 1)

//  第三种组合
//  B说，我是第二名、C说，A是最后一名；=> B = 2 C=1 A==5 E!=1  D != 1
// =>  B = 2 C=1 A==5
answer(permutations, n => n[1] == 2 && n[2] == 1 && n[0] == 5)

// 第四种组合 
// D说，C不是第一名 
// E说，D是第一名；
// D ==2 => C!=1  B != 2 E!=1  A !=5
answer(permutations, n => n[3] == 2 && n[2] != 1 && n[1] != 2 && n[4] != 1 && n[0] != 5);

不用程序直接推导

本来一个很简单的题，被编程搞得这么麻烦，就想知道如果自己算就要多久，果然不超过五分钟，就有了下面的结果：

┓( ´∀` )┏