偶尔看到一到智力题,开始没有想到好的解题方法,直接用python暴力得出答案。用到数字排列组合的方法,在这里记录一下。

题目:

五位学生A,B,C,D,E,参加一场比赛。某人预测比赛结果的顺序是ABCDE,结果没有猜对任何一个名次,也没有猜中任何一对相邻的名次(意即某两个人实际上名次相邻,而在此人的猜测中名次也相邻,且先后顺序相同),另一个人预测比赛结果为DAECB,结果猜对了两个名次,同时还猜中了两对相邻的名次。现在,试着找出真正的顺序!


python解题

穷举所有可能的比赛结果

这里有三种方法,循环,递归,itertools模块。其实itertools模块就是用递归实现的。

  1. 循环
lst = ['a', 'b', 'c', 'd', 'e']
num = []
for i in lst:
    for j in lst:
        for k in lst:
            for n in lst:
                for m in lst:
                    if i != j and i != k and i != n and i != m and j != k and j != n and j != m and k != n and k != m and n != m:
                        num.append(i+j+k+n+m)
print(len(num))
  1. 递归
def perms(elements):
    if len(elements) <=1:
        yield elements
    else:
        for perm in perms(elements[1:]):
            #print(perm)
            for i in range(len(elements)):
                #print(elements[0:1])
                yield perm[:i] + elements[0:1] + perm[i:]

lst = ['a', 'b', 'c', 'd', 'e']
print(len(list(perms(lst))))
  1. Itertools模块
from itertools import permutations
list_num = ['a', 'b', 'c', 'd', 'e']
result = []
for num in list(permutations(list_num, 4)):
    a = ''
    for i in range(len(num)):
        a += num[i]
    result.append(a)
print(len(result))

根据题目中的限制条件进行筛选

直接看代码注释,这里不详细解释了。

from itertools import permutations
## 得出所有的排列组合
def all_num(lst):
    result = []
    for num in list(permutations(lst)):
        x = ''
        for i in range(len(num)):
            x += num[i]
        yield x
## 排除ABCDE的比赛结果        
def rule1(i):
    if i[0] != 'a' and i[1] != 'b' and i[2] != 'c' and i[3] != 'd' and i[4] != 'e':
        return i
## 排除ABCDE结果的相邻情况      
def rule2(n):
    for i in range(4):
        if n[i:i+2] == 'ab' or n[i:i+2] == 'bc' or n[i:i+2] == 'cd' or n[i:i+2] == 'de':
            break
    else:
        return n
## 得出DAECB比赛结果的相邻情况       
def rule_num(num):
    lsts = []
    for i in range(4):
        lsts.append(num[i:i+2])
    return lsts
## 在结果中对比DAECB的相邻情况               
def rule3(n, lsts):
    a = 0
    for i in range(4):
        if n[i:i+2] in lsts:
            a += 1
    if a == 2:
        print(n)

def main():
    lst = ['a', 'b', 'c', 'd', 'e']
    num = 'daecb'
    lsts = rule_num(num)

    for t in list(all_num(lst)):
        n = rule1(t)
        if n:
            m = rule2(n)
            if m:
                rule3(m, lsts)    

main()
ecbad       ## 明显不对,可以排除
edacb       ## 最终结果

所以最终结果就是:EDACB

正确解法

事后仔细想了一下,其实这道题没有那么复杂。主要从DAECB这个比赛结果入手,这个结果猜对了两个名次和两对相邻的名次,可以得出一定不会有3个连续的正确,两个相邻的名次一定是两两分开的。也就是DA,AE,EC,CB,其中两个是正确的组合。因为不会有3个连续的正确,而一共是5个人比赛,所以正确的两个相邻的组合只能为DA,EC或DA,CB或AE,CB这三种组合。排除DAECB这个一定错误的结果,又需要保证有两个正确的名次,就只能有下面四种可能:DABEC、DACBE、EDACB、AEDCB。最后根据ABCDE全部错误的信息,可以得出最终答案为EDACB。