## 2018年12月30日日曜日

### Algorithm - Python - アナグラム狂(ハッシュ関数、素数、衝突、文字列、辞書の基本、ハッシング)

コード(Emacs)

Python 3

```#!/usr/bin/env python3
from sympy import primerange, prevprime

primes = list(primerange(1, 102))

def char_to_prime(ch: chr) -> int:
return primes[ord(ch) - 97]

def prime_hash(s: str) -> int:
if len(s) == 0:
return 1
return char_to_prime(s[0]) + prime_hash(s[1:])

def anagrams(corpus: list, n: int = 30) -> list:
p = prevprime(n)
l = [[] for _ in range(n)]
for word in corpus:
l[prime_hash(word) % p].append(word)
return l

def print_anagrams(anagrams: list):
for i, anagram in enumerate(anagrams, 1):
print(f'{i}: {anagram}')

if __name__ == '__main__':
corpus = ['ate', 'but', 'eat', 'tub',
'abed', 'mace', 'acre', 'abut', 'mean', 'bade', 'abet', 'care',
'tabu', 'bead', 'beat', 'race', 'acme', 'beta', 'came']
for n in range(20, 30):
print(f'n = {n}')
l = anagrams(corpus, n)
print_anagrams(l)
```

```\$ ./sample2.py
n = 20
1: []
2: []
3: []
4: ['mace', 'mean', 'acme', 'came']
5: ['acre', 'care', 'race']
7: []
8: []
9: []
10: ['ate', 'eat']
11: []
12: []
13: ['abet', 'beat', 'beta']
14: []
15: []
16: ['but', 'tub']
17: []
18: ['abut', 'tabu']
19: []
20: []
n = 21
1: []
2: []
3: []
4: ['mace', 'mean', 'acme', 'came']
5: ['acre', 'care', 'race']
7: []
8: []
9: []
10: ['ate', 'eat']
11: []
12: []
13: ['abet', 'beat', 'beta']
14: []
15: []
16: ['but', 'tub']
17: []
18: ['abut', 'tabu']
19: []
20: []
21: []
n = 22
1: []
2: []
3: []
4: ['mace', 'mean', 'acme', 'came']
5: ['acre', 'care', 'race']
7: []
8: []
9: []
10: ['ate', 'eat']
11: []
12: []
13: ['abet', 'beat', 'beta']
14: []
15: []
16: ['but', 'tub']
17: []
18: ['abut', 'tabu']
19: []
20: []
21: []
22: []
n = 23
1: []
2: []
3: []
4: ['mace', 'mean', 'acme', 'came']
5: ['acre', 'care', 'race']
7: []
8: []
9: []
10: ['ate', 'eat']
11: []
12: []
13: ['abet', 'beat', 'beta']
14: []
15: []
16: ['but', 'tub']
17: []
18: ['abut', 'tabu']
19: []
20: []
21: []
22: []
23: []
n = 24
1: []
3: []
4: []
5: []
6: []
7: ['mean']
8: []
9: []
10: []
11: ['but', 'tub']
12: ['acre', 'care', 'race']
13: ['abut', 'tabu']
14: []
15: ['mace', 'acme', 'came']
16: []
17: ['ate', 'eat']
18: []
19: []
20: ['abet', 'beat', 'beta']
21: []
22: []
23: []
24: []
n = 25
1: []
3: []
4: []
5: []
6: []
7: ['mean']
8: []
9: []
10: []
11: ['but', 'tub']
12: ['acre', 'care', 'race']
13: ['abut', 'tabu']
14: []
15: ['mace', 'acme', 'came']
16: []
17: ['ate', 'eat']
18: []
19: []
20: ['abet', 'beat', 'beta']
21: []
22: []
23: []
24: []
25: []
n = 26
1: []
3: []
4: []
5: []
6: []
7: ['mean']
8: []
9: []
10: []
11: ['but', 'tub']
12: ['acre', 'care', 'race']
13: ['abut', 'tabu']
14: []
15: ['mace', 'acme', 'came']
16: []
17: ['ate', 'eat']
18: []
19: []
20: ['abet', 'beat', 'beta']
21: []
22: []
23: []
24: []
25: []
26: []
n = 27
1: []
3: []
4: []
5: []
6: []
7: ['mean']
8: []
9: []
10: []
11: ['but', 'tub']
12: ['acre', 'care', 'race']
13: ['abut', 'tabu']
14: []
15: ['mace', 'acme', 'came']
16: []
17: ['ate', 'eat']
18: []
19: []
20: ['abet', 'beat', 'beta']
21: []
22: []
23: []
24: []
25: []
26: []
27: []
n = 28
1: []
3: []
4: []
5: []
6: []
7: ['mean']
8: []
9: []
10: []
11: ['but', 'tub']
12: ['acre', 'care', 'race']
13: ['abut', 'tabu']
14: []
15: ['mace', 'acme', 'came']
16: []
17: ['ate', 'eat']
18: []
19: []
20: ['abet', 'beat', 'beta']
21: []
22: []
23: []
24: []
25: []
26: []
27: []
28: []
n = 29
1: []
3: []
4: []
5: []
6: []
7: ['mean']
8: []
9: []
10: []
11: ['but', 'tub']
12: ['acre', 'care', 'race']
13: ['abut', 'tabu']
14: []
15: ['mace', 'acme', 'came']
16: []
17: ['ate', 'eat']
18: []
19: []
20: ['abet', 'beat', 'beta']
21: []
22: []
23: []
24: []
25: []
26: []
27: []
28: []
29: []
\$
```

この例だと、nが23までの場合に非アナグラムの衝突があり、nが24以上の場合に衝突が無くなることを確認できた。