## 2018年11月29日木曜日

### Algorithm - Python - 招かれざる客(最大選択肢、重み、メモリー使用量の最適化、リストの連結、しらみつぶしの数え上げと符号化の組合わせ)

コード(Emacs)

Python 3

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

dislike_pairs = [['Alice', 'Bob'], ['Bob', 'Eve']]
guests = [('Alice', 2), ('Bob', 6), ('Cleo', 3), ('Don', 10), ('Eve', 3)]

def combinations(n: int, guests: list) -> list:
all_combinations = []
for i in range(2 ** n):
num = i
combinations = []
for j in range(n):
if num % 2 == 1:
combinations = [guests[n - 1 - j]] + combinations
num //= 2
all_combinations.append(combinations)
return all_combinations

def is_good(combination: list, name1: str, name2: str) -> bool:
names = [name for name, _ in combination]
return not (name1 in names and name2 in names)

all_combinations: list, dislike_pairs: list) -> list:
all_good_combinations = []
for combination in all_combinations:
good = True
for a, b in dislike_pairs:
if not is_good(combination, a, b):
good = False
break
if good:
all_good_combinations.append(combination)
return all_good_combinations

def get_weight(combination: list) -> int:
return sum([weight for _, weight in combination])

def invite_dinner(guests: list, dislike_pairs: list) -> None:
''' メモリーの使用量を最適化していない版
>>> invite_dinner(guests, dislike_pairs)
Optimum Solution: [('Bob', 6), ('Cleo', 3), ('Don', 10)]
'''
all_combinations = combinations(len(guests), guests)
all_combinations, dislike_pairs)
invite = max(all_good_combinations, key=get_weight)
print(f'Optimum Solution: {invite}')

def invite_dinner_optimized(guests: list, dislike_pairs: list) -> None:
''' メモリーの使用量を最適化した版
>>> invite_dinner_optimized(guests, dislike_pairs)
Optimum Solution: [('Bob', 6), ('Cleo', 3), ('Don', 10)]
'''
n = len(guests)
invite = []
invite_weight = 0
for i in range(2 ** n):
num = i
combination = []
for j in range(n):
if num % 2 == 1:
combination = [guests[n - 1 - j]] + combination
num //= 2
good = True
for a, b in dislike_pairs:
if not is_good(combination, a, b):
good = False
break
if good:
weight = get_weight(combination)
if weight > invite_weight:
invite = combination
invite_weight = weight
print(f'Optimum Solution: {invite}')

if __name__ == '__main__':
import doctest
doctest.testmod()
```

```\$ ./sample1.py -v
Trying:
invite_dinner(guests, dislike_pairs)
Expecting:
Optimum Solution: [('Bob', 6), ('Cleo', 3), ('Don', 10)]
ok
Trying:
invite_dinner_optimized(guests, dislike_pairs)
Expecting:
Optimum Solution: [('Bob', 6), ('Cleo', 3), ('Don', 10)]
ok
__main__
__main__.combinations
__main__.get_weight
__main__.is_good
2 items passed all tests:
1 tests in __main__.invite_dinner
1 tests in __main__.invite_dinner_optimized
2 tests in 7 items.
2 passed and 0 failed.
Test passed.
\$
```