## 2018年12月29日土曜日

### Algorithm - Python - アナグラム狂(カスタムソート(クイックソート)、辞書の基本、ハッシング)

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

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)
```

```\$ ./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
__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
abet
care
tabu
beat
race
acme
beta
came
--------------------------------------------------
abed
mace
acme
came
acre
race
care
eat
ate
abet
beat
beta
mean
tub
but
tabu
abut
\$
```