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章(アナグラム狂)、練習問題(問題1)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3
from sympy import primerange

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 pivot_partition_clever(lst: list, start: int, end: int) -> int:
    pivot = lst[end]
    bottom = start - 1
    top = end
    done = False
    while not done:
        while not done:
            bottom += 1
            if bottom == top:
                done = True
                break
            if prime_hash(lst[bottom]) > prime_hash(pivot):
                lst[top] = lst[bottom]
                break
        while not done:
            top -= 1
            if top == bottom:
                done = True
                break
            if prime_hash(lst[top]) <= prime_hash(pivot):
                lst[bottom] = lst[top]
                break
    lst[top] = pivot
    return top


def quick_sort(lst: list, start: int, end: int) -> None:
    '''
    >>> corpus = ['ate', 'but', 'eat', 'tub', 'tea']
    >>> quick_sort(corpus, 0, len(corpus) - 1)
    >>> corpus
    ['ate', 'eat', 'tea', 'tub', 'but']
    '''
    if start < end:
        pivot_index = pivot_partition_clever(lst, start, end)
        quick_sort(lst, start, pivot_index - 1)
        quick_sort(lst, pivot_index + 1, end)


def prime_sort(lst: list) -> None:
    '''
    >>> corpus = ['ate', 'but', 'eat', 'tub', 'tea']
    >>> prime_sort(corpus)
    >>> corpus
    ['ate', 'eat', 'tea', 'tub', 'but']
    '''
    quick_sort(lst, 0, len(lst) - 1)


def print_words(words: list) -> None:
    print('-' * 50)
    for word in words:
        print(word)


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

    print(primes)
    corpus = ['ate', 'but', 'eat', 'tub',
              'abed', 'mace', 'acre', 'abut', 'mean', 'bade', 'abet', 'care',
              'tabu', 'bead', 'beat', 'race', 'acme', 'beta', 'came']
    print_words(corpus)
    prime_sort(corpus)
    print_words(corpus)

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

$ ./sample1.py -v
Trying:
    corpus = ['ate', 'but', 'eat', 'tub', 'tea']
Expecting nothing
ok
Trying:
    prime_sort(corpus)
Expecting nothing
ok
Trying:
    corpus
Expecting:
    ['ate', 'eat', 'tea', 'tub', 'but']
ok
Trying:
    corpus = ['ate', 'but', 'eat', 'tub', 'tea']
Expecting nothing
ok
Trying:
    quick_sort(corpus, 0, len(corpus) - 1)
Expecting nothing
ok
Trying:
    corpus
Expecting:
    ['ate', 'eat', 'tea', 'tub', 'but']
ok
5 items had no tests:
    __main__
    __main__.char_to_prime
    __main__.pivot_partition_clever
    __main__.prime_hash
    __main__.print_words
2 items passed all tests:
   3 tests in __main__.prime_sort
   3 tests in __main__.quick_sort
6 tests in 7 items.
6 passed and 0 failed.
Test passed.
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
--------------------------------------------------
ate
but
eat
tub
abed
mace
acre
abut
mean
bade
abet
care
tabu
bead
beat
race
acme
beta
came
--------------------------------------------------
bade
bead
abed
mace
acme
came
acre
race
care
eat
ate
abet
beat
beta
mean
tub
but
tabu
abut
$