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

問題解決のPythonプログラミング
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Python 3.7 (プログラミング言語)

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の17章(アナグラム狂)、練習問題(問題2)を取り組んでみる。

コード(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)

入出力結果(Terminal, cmd(コマンドプロンプト), Jupyter(IPython))

$ ./sample2.py
n = 20
1: []
2: []
3: []
4: ['mace', 'mean', 'acme', 'came']
5: ['acre', 'care', 'race']
6: ['abed', 'bade', 'bead']
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']
6: ['abed', 'bade', 'bead']
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']
6: ['abed', 'bade', 'bead']
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']
6: ['abed', 'bade', 'bead']
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: []
2: ['abed', 'bade', 'bead']
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: []
2: ['abed', 'bade', 'bead']
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: []
2: ['abed', 'bade', 'bead']
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: []
2: ['abed', 'bade', 'bead']
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: []
2: ['abed', 'bade', 'bead']
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: []
2: ['abed', 'bade', 'bead']
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以上の場合に衝突が無くなることを確認できた。