## 2018年12月10日月曜日

### Algorithm - Python - おびただしい女王(アメリカズ・ゴット・タレント、forループを再帰関数に変換、再帰プロシージャーによるしらみつぶし探索)

コード(Emacs)

Python 3

```#!/usr/bin/env python3

def is_good(combination: list, candidates: list, candidates_talents: list,
all_talents: list) -> bool:
for talent in all_talents:
cover = False
for candidate in combination:
candidate_talents = candidates_talents[candidates.index(candidate)]
if talent in candidate_talents:
cover = True
if not cover:
return False
return True

def recursive_combination(
j: int, n: int, num: int, candidates: list, combination: list) -> list:
if j == n:
return combination
if num % 2 == 1:
combination = [candidates[n - 1 - j]] + combination
num //= 2
return recursive_combination(j + 1, n, num, candidates, combination)

def small_solution(i: int, candidates: list, n: int, candidates_talents: list,
talents: list, hire: list) -> list:
if i == 2 ** n:
return hire
combination = recursive_combination(0, n, i, candidates, [])
if is_good(combination, candidates, candidates_talents, talents) and \
len(combination) < len(hire):
return small_solution(i + 1, candidates, n, candidates_talents, talents,
combination)
return small_solution(i + 1, candidates, n, candidates_talents, talents,
hire)

def hire_for_show(candidates: list,
candidates_talents: list,
talents: list) -> None:
'''
>>> hire_for_show(candidates, candidate_talents, talents)
Optimum Solution: ['Aly', 'Cal', 'Eve']
>>> hire_for_show(candidates2, candidate_talents2, talents2)
Optimum Solution: ['A', 'B', 'D']
'''
hire = small_solution(0, candidates, len(candidates), candidates_talents,
talents, candidates[:])
print(f'Optimum Solution: {hire}')

if __name__ == '__main__':
import doctest
talents = ['Sing', 'Dance', 'Magic', 'Act', 'Flex', 'Code']
candidates = ['Aly', 'Bob', 'Cal', 'Don', 'Eve', 'Fay']
candidate_talents = [['Flex', 'Code'],
['Dance', 'Magic'],
['Sing', 'Magic'],
['Sing', 'Dance'],
['Dance', 'Act', 'Code'],
['Act', 'Code']]
talents2 = list(range(1, 10))
candidates2 = [chr(ord('A') + i) for i in range(7)]
candidate_talents2 = [[4, 5, 7],
[1, 2, 8],
[2, 4, 6, 9],
[3, 6, 9],
[2, 3, 9],
[7, 8, 9],
[1, 3, 7]]
globs = locals()
globs.update({'talents': talents,
'candidates': candidates,
'candidate_talents': candidate_talents,
'talents2': talents2,
'candidates2': candidates2,
'candidate_talents2': candidate_talents2})
doctest.testmod(globs=globs)
```

```\$ ./sample4.py -v
Trying:
hire_for_show(candidates, candidate_talents, talents)
Expecting:
Optimum Solution: ['Aly', 'Cal', 'Eve']
ok
Trying:
hire_for_show(candidates2, candidate_talents2, talents2)
Expecting:
Optimum Solution: ['A', 'B', 'D']
ok
__main__
__main__.is_good
__main__.recursive_combination
__main__.small_solution
1 items passed all tests:
2 tests in __main__.hire_for_show
2 tests in 5 items.
2 passed and 0 failed.
Test passed.
\$
```