偶尔看到一到智力题，开始没有想到好的解题方法，直接用python暴力得出答案。用到数字排列组合的方法，在这里记录一下。
题目：
五位学生A,B,C,D,E,参加一场比赛。某人预测比赛结果的顺序是ABCDE,结果没有猜对任何一个名次，也没有猜中任何一对相邻的名次（意即某两个人实际上名次相邻，而在此人的猜测中名次也相邻，且先后顺序相同），另一个人预测比赛结果为DAECB,结果猜对了两个名次，同时还猜中了两对相邻的名次。现在，试着找出真正的顺序！
python解题
穷举所有可能的比赛结果
这里有三种方法，循环，递归，itertools模块。其实itertools模块就是用递归实现的。
- 循环
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))
- 递归
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))))
- 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。