お気楽 Python3 プログラミング超入門

●キュー

キュー (queue) は待ち行列とか先入れ先出し (FIFO : first-in, first-out) と呼ばれるデータ構造
キューの説明は拙作のページ「Python 入門第 6 回: キュー」を参照
Python の場合、リストの末尾にデータを追加 (append()) し、先頭からデータを取り出す (pop(0)) とキューの動作になる
append() の動作は高速だが、pop(0) は要素の移動が必要になるため時間がかかる
Python の標準ライブラリにはキューに適したデータ構造 deque が用意されている
deque は「両端キュー」のことで、「デック」とか「ディーキュー」と呼ばれる
先頭および末尾のどちらからでもデータの追加と取り出しが高速に行える
deque はクラスで、モジュール collections にある
主なメソッド

deque([iterable, [maxlen]]), deque の生成

maxlen は deque の最大長
maxlen を省略、または None にすると、大きさの制限はなくなる (可変長)
maxlen を超えた場合、データを追加した反対側からデータが取り除かれる

d.append(x), d.appendleft(x), データ x の追加
d.pop(), d.popleft(), データの取り出し
d.extend(iter), d.extendleft(iter), iter から要素を取り出して deque に追加
d.rotate(n = 1), deque を右に n 回転する (負の場合は左回転)
d.reverse(), deque を反転する
d.clear(), deque を空にする
len(d), deque の要素数を返す
d[i] のように添え字のアクセスもできるが、先頭と末尾以外のアクセスは時間がかかる
詳しい説明はリファレンスマニュアル 8.3. collections - deque を参照

>>> from collections import deque
>>> for x in range(4): d.append(x)
...
>>> d
deque([0, 1, 2, 3])
>>> for _ in range(4): print(d.popleft())
...
0
1
2
3
>>> d
deque([])
>>> d.extend(range(1, 10))
>>> d
deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> len(d)
9
>>> d.reverse()
>>> d
deque([9, 8, 7, 6, 5, 4, 3, 2, 1])
>>> d.rotate(3)
>>> d
deque([3, 2, 1, 9, 8, 7, 6, 5, 4])

ディーキューは循環配列 (リングバッファ) や連結リストを使って簡単に実装できる
双方向リストによる実装は拙作のページ「Algorithms with Python: 連結リストとキュー」を参照
ここではリングバッファを使った簡単な実装例を示す

#
# deque.py : リングバッファによるディーキューの実装
#
#            Copyright (C) 2018 Makoto Hiroi
#
class Deque:
    def __init__(self, size):
        self.buff = [None] * size
        self.front = 0
        self.rear = 0
        self.cnt = 0

    # 先頭からデータを取り出す
    def pop_front(self):
        if self.cnt == 0:
            raise IndexError("Deque is empty")
        x = self.buff[self.front]
        self.front += 1
        self.cnt -= 1
        if self.front == len(self.buff):
            self.front = 0
        return x
    
    # 末尾からデータを取り出す
    def pop_back(self):
        if self.cnt == 0:
            raise IndexError("Deque is empty")
        self.rear -= 1
        self.cnt -= 1
        if self.rear < 0:
            self.rear = len(self.buff) - 1
        return self.buff[self.rear]

    # 末尾にデータを追加        
    def push_back(self, x):
        if self.cnt == len(self.buff):
            # 先頭からデータを取り出して捨てる
            self.pop_front()
        self.buff[self.rear] = x
        self.rear += 1
        self.cnt += 1
        if self.rear == len(self.buff):
            self.rear = 0
    
    # 先頭にデータを追加する
    def push_front(self, x):
        if self.cnt == len(self.buff):
            # 末尾からデータを取り出して捨てる
            self.pop_back()
        self.front -= 1
        self.cnt += 1
        if self.front < 0:
            self.front = len(self.buff) - 1
        self.buff[self.front] = x

    # ジェネレータ
    def each(self):
        i = self.front
        c = self.cnt
        while c > 0:
            yield self.buff[i]
            i += 1
            c -= 1
            if i == len(self.buff): i = 0

    # 空か？
    def is_empty(self): return self.cnt == 0

    # 空にする
    def clear(self):
        self.front = 0
        self.rear = 0
        self.cnt = 0

    # 要素数を返す
    def __len__(self): return self.cnt

    # 表示
    def __repr__(self):
        s = 'Deque('
        if self.cnt > 0:
            for x in self.each():
                s += '{}, '.format(x)
            s = s[:-2]
        s += ')'
        return s

if __name__ == '__main__':
    # 簡単なテスト
    d = Deque(8)
    print(d)
    print(d.is_empty())
    print(len(d))
    for x in range(4): d.push_back(x)
    print(d)
    print(d.is_empty())
    print(len(d))
    for x in range(4, 8): d.push_front(x)
    print(d)
    print(d.is_empty())
    print(len(d))
    for _ in range(4): print(d.pop_front())
    print(d)
    print(d.is_empty())
    print(len(d))
    for _ in range(4): print(d.pop_back())
    print(d)
    print(d.is_empty())
    print(len(d))
    for x in range(10): 
        d.push_back(x)
        print(d)
    for x in range(10, 12):
        d.push_front(x)
        print(d)

Deque()
True
0
Deque(0, 1, 2, 3)
False
4
Deque(7, 6, 5, 4, 0, 1, 2, 3)
False
8
7
6
5
4
Deque(0, 1, 2, 3)
False
4
3
2
1
0
Deque()
True
0
Deque(0)
Deque(0, 1)
Deque(0, 1, 2)
Deque(0, 1, 2, 3)
Deque(0, 1, 2, 3, 4)
Deque(0, 1, 2, 3, 4, 5)
Deque(0, 1, 2, 3, 4, 5, 6)
Deque(0, 1, 2, 3, 4, 5, 6, 7)
Deque(1, 2, 3, 4, 5, 6, 7, 8)
Deque(2, 3, 4, 5, 6, 7, 8, 9)
Deque(10, 2, 3, 4, 5, 6, 7, 8)
Deque(11, 10, 2, 3, 4, 5, 6, 7)

●プライオリティキュー

プライオリティキュー (priority queue) は「優先度つき待ち行列」のこと
優先度つき待ち行列は、データに優先度をつけておいて、優先度の高いデータから取り出す
詳しい説明は拙作のページ「Algorithms with Python: 二分木とヒープ」を参照
リストをプライオリティキューとして扱う関数がモジュール heapq に用意されている
デフォルトの動作は最小ヒープ (値が小さいほど優先順位が高い)
基本的な操作関数

hepapush(heap, x), heap に x を追加
heappop(heap), heap からデータを取り出す
heapify(xs), リスト xs をヒープ (プライオリティキュー) に変換する

詳細はライブラリリファレンス 8.5. heapq — ヒープキューアルゴリズムを参照

>>> from heapq import *
>>> a = []
>>> for x in [5,6,4,7,3,8,2,9,1]: heappush(a, x)
...
>>> a
[1, 2, 3, 4, 6, 8, 5, 9, 7]
>>> for _ in range(9): print(heappop(a))
...
1
2
3
4
5
6
7
8
9
>>> a
[]
>>> a = [9,8,7,6,5,4,3,2,1]
>>> heapify(a)
>>> a
[1, 2, 3, 6, 5, 4, 7, 8, 9]
>>> for _ in range(9): print(heappop(a))
...
1
2
3
4
5
6
7
8
9

●bytes と bytearray

bytes はバイトシーケンスを表す immutable なデータ型
バイトは 0 以上 256 未満の整数
bytearray は mutable なバイトシーケンス
どちらもシーケンスの操作が可能 (bytearray は mutable な操作も可)
bytes のリテラル表記は b'...' のように文字列リテラルの前に b を付ける
コンストラクタ bytes(), bytearray() も用意されている

bytes(), 空のバイトシーケンスを生成する
bytes(n), 長さ n のバイトシーケンスを生成する (要素は 0)
bytes(iterable), iterable をバイトシーケンスに変換する
bytes(bytes-like-object), bytes-like-object をバイトシーケンスに変換する
bytearray() でも同じことができる

>>> a = b'12345678'
>>> a
b'12345678'
>>> a[0]
49
>>> a[7]
56
>>> a[2:6]
b'3456'
>>> bytes(10)
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
>>> bytes(range(10))
b'\x00\x01\x02\x03\x04\x05\x06\x07\x08\t'
>>> bytearray(10)
bytearray(b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00')
>>> b = bytearray(a)
>>> b
bytearray(b'12345678')
>>> b[0] = ord('a')
>>> b
bytearray(b'a2345678')

メソッド str.encode(encoding='utf-8') は文字列 str を bytes に変換する
メソッド bytes.decode(encoding='utf-8') は bytes を str に変換する
整数値を bytes に変換するにはメソッド to_bytes() を使う
逆に、bytes を整数値に変換するには整数 (int) のクラスメソッド from_bytes() を使う

num.to_bytes(length, byteorder)
int.from_bytes(bytes, byteorder)

byteorder は 'big' (ビッグエンディアン) または 'little' (リトルエンディアン)

>>> a = 'あいうえお'
>>> b = a.encode()
>>> b
b'\xe3\x81\x82\xe3\x81\x84\xe3\x81\x86\xe3\x81\x88\xe3\x81\x8a'
>>> b.decode()
'あいうえお'
>>> a = 97
>>> a.to_bytes(1, 'big')
b'a'
>>> int.from_bytes(b'a', 'big')
97

このほかにも、文字列と同様の操作を行うメソッドが多数用意されている
詳細はリファレンスマニュアル 4.8. バイナリシーケンス型を参照

●array

Python の標準ライブラリには、数値型配列を表すクラス array がモジュール array に用意されている
リストと同様の操作が可能だが、同じデータ型の要素しか格納することができない
コンストラクタは array(typecode, [initializer])
initializer はリスト、bytes-like object、iterable なオブジェクト
typecode は次の文字で指定する (大文字は無符号整数)

b, B, 8 bit 整数
h, H, 16 bit 整数
i, I, 32 bit 整数
l, L, 32 bit 整数
q, Q, 64 bit 整数
f, 単精度浮動小数点数
d, 倍精度浮動小数点数
実際には処理系によって異なる (上記は M.Hiroi が使用している処理系の場合)
要素のサイズはインスタンス変数 itemsize に格納されている

>>> import array
>>> a = array.array('l', range(8))
>>> a
array('l', [0, 1, 2, 3, 4, 5, 6, 7])
>>> a[0]
0
>>> a[7]
7
>>> a[5] *= 100
>>> a
array('l', [0, 1, 2, 3, 4, 500, 6, 7])
>>> a.append(1000)
>>> a
array('l', [0, 1, 2, 3, 4, 500, 6, 7, 1000])
>>> a.pop()
1000
>>> a
array('l', [0, 1, 2, 3, 4, 500, 6, 7])

変換用のメソッド

tolist(), fromlist(xs), array とリストの変換
tobytes(), frombytes(s), array と bytes-like object の変換
tofile(f), fromfile(f, n), ファイル f への書き込み、データを n 個読み込む
byteswap(), エンディアンの変更

詳細はライブラリリファレンス 8.7. array — 効率のよい数値アレイを参照

>>> a = array.array('l', [1, 2, 3, 4])
>>> a
array('l', [1, 2, 3, 4])
>>> a.tolist()
[1, 2, 3, 4]
>>> b = a.tobytes()
>>> b
b'\x01\x00\x00\x00\x02\x00\x00\x00\x03\x00\x00\x00\x04\x00\x00\x00'
>>> c = array.array('l')
>>> c.frombytes(b)
>>> c
array('l', [1, 2, 3, 4])
>>> with open('test.dat', 'wb') as f:
...     a.tofile(f)
...
>>> d = array.array('l')
>>> d
array('l')
>>> with open('test.dat', 'rb') as f:
...     d.fromfile(f, 4)
...
>>> d
array('l', [1, 2, 3, 4])

●ソート

Python でデータをソートするには、リストのメソッド sort() か、関数 sorted() を使う

xs.sort(key = None, reverse = False) => None
sorted(iterable, key = None, reverse = False) => sorted_list

sort() はリストをインプレースでソートする (リストは破壊的に修正される)
sorted() は iterable からソート済みのリストを生成する
キーワード引数 key は関数で、要素を比較する前に呼び出され、その結果を使ってソートする
キーワード引数 reverse に True を指定すると、逆順にソートする
ソートの使い方は Python のドキュメント『ソート HOW TO』が参考になる

>>> a = [5, 6, 4, 7, 3, 8, 2, 9, 1, 0]
>>> a.sort()
>>> a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> a.sort(reverse=True)
>>> a
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
>>> sorted(a)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> a
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
>>> b = [('foo', 1), ('bar', 2), ('baz', 3), ('oops', 4)]
>>> b.sort(key = lambda x: x[0])
>>> b
[('bar', 2), ('baz', 3), ('foo', 1), ('oops', 4)]
>>> b.sort(key = lambda x: x[1])
>>> b
[('foo', 1), ('bar', 2), ('baz', 3), ('oops', 4)]
>>> sorted(b, key = lambda x: x[0])
[('bar', 2), ('baz', 3), ('foo', 1), ('oops', 4)]
>>> b
[('foo', 1), ('bar', 2), ('baz', 3), ('oops', 4)]

モジュール operator には便利なアクセサ関数が用意されている

itemgetter(n), n 番目の要素を取り出す関数を生成する
attrgetter(name), 属性 name の値を取り出す関数を生成する
methodcaller('name' [, args, ...]), メソッド name を呼び出す関数を生成する
name を呼び出すとき、引数 args が渡される

>>> from operator import itemgetter, attrgetter, methodcaller
>>> f1 = itemgetter(1)
>>> f1([1, 2, 3, 4, 5])
2
>>> a = [('foo', 1), ('bar', 2), ('baz', 3), ('oops', 4)]
>>> sorted(a, key = itemgetter(0))
[('bar', 2), ('baz', 3), ('foo', 1), ('oops', 4)]
>>> sorted(a, key = itemgetter(1))
[('foo', 1), ('bar', 2), ('baz', 3), ('oops', 4)]
>>> class Pair:
...     def __init__(self, x, y):
...         self.fst = x
...         self.snd = y
...     def get_fst(self): return self.fst
...     def get_snd(self): return self.snd
...     def __repr__(self): return 'Pair({},{})'.format(self.fst, self.snd)
...
>>> b = list(map(lambda xs: Pair(xs[0], xs[1]), a))
>>> b
[Pair(foo,1), Pair(bar,2), Pair(baz,3), Pair(oops,4)]
>>> sorted(b, key = attrgetter('fst'))
[Pair(bar,2), Pair(baz,3), Pair(foo,1), Pair(oops,4)]
>>> sorted(b, key = attrgetter('snd'))
[Pair(foo,1), Pair(bar,2), Pair(baz,3), Pair(oops,4)]
>>> sorted(b, key = methodcaller('get_fst'))
[Pair(bar,2), Pair(baz,3), Pair(foo,1), Pair(oops,4)]
>>> sorted(b, key = methodcaller('get_snd'))
[Pair(foo,1), Pair(bar,2), Pair(baz,3), Pair(oops,4)]

sort() や sorted() は安定なソート
ソートキーが等しい場合、入力された順番が崩れないソートのこと

  元のデータ      安定なソート    不安定なソート

  (123, 'abc')    (123, 'abc')    (789, 'abc')
  (456, 'def')    (789, 'abc')    (123, 'abc')
  (789, 'abc')    (456, 'def')    (456, 'def')

                図 : ソートの安定性

2 番目の要素をキーにソートした場合、1 行目と 3 行目はソートキーが等しい
安定なソートであればソート結果が 1, 3, 2 の順番になり、入力時の位置関係が保たれる
不安定なソートはソート結果が、たとえば 3, 1, 2 の順番となり、入力時の位置関係が崩れる
itemgetter() や attrgetter() で複数の引数を指定すると、値が等しい場合、次の引数で指定した要素を比較する

>>> a = [('foo', 1), ('bar', 3), ('bar', 2), ('bar', 1), ('baz', 4)]
>>> sorted(a, key = itemgetter(0))
[('bar', 3), ('bar', 2), ('bar', 1), ('baz', 4), ('foo', 1)]
>>> sorted(a, key = itemgetter(0, 1))
[('bar', 1), ('bar', 2), ('bar', 3), ('baz', 4), ('foo', 1)]

●bisect

モジュール bisect には、二分探索を使ってソート済みのリストを操作する関数が用意されている

bisect_left(xs, x, lo=0, hi=len(xs)), リスト xs に x を挿入する位置を返す (同じ値がある場合は左端)
bisect_right(xs, x, lo=0, hi=len(xs)), リスト xs に x を挿入する位置を返す (同じ値がある場合は右端)
bisect(xs, x, lo=0, hi=len(xs)), bisect_right() と同じ
insort_left(xs, x, lo=0, hi=len(xs)), リスト xs に x を挿入 (同じ値がある場合は左端に挿入)
insort_right(xs, x, lo=0, hi=len(xs)), リスト xs に x を挿入 (同じ値がある場合は右端に挿入)
insort(xs, x, lo=0, hi=len(xs)), insort_right() と同じ

>>> from bisect import *
>>> a = [1, 1, 2, 2, 2, 3, 3, 3, 3, 4]
>>> bisect_left(a, 2)
2
>>> bisect(a, 2)
5
>>> insort_left(a, 2)
>>> a
[1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4]
>>> insort(a, 2)
>>> a
[1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4]

値の有無を二分探索で調べる場合、bisect_left() の位置にある要素が値と等しいかチェックすればよい

>>> def bsearch(xs, x):
...     i = bisect_left(xs, x)
...     return len(xs) != i and xs[i] == x
...
>>> a
[1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4]
>>> bsearch(a, 1)
True
>>> bsearch(a, 2)
True
>>> bsearch(a, 3)
True
>>> bsearch(a, 4)
True
>>> bsearch(a, 5)
False
>>> bsearch(a, 0)
False

●簡単なプログラム (4)

問題やプログラム (アルゴリズム) の説明は下記ページを参照してください。

Puzzle DE Programming

約数
循環小数
分割数

Julia Language Programming

カッコ列
カッコ列の総数
カッコ列と二分木
平方根 (めのこ平方)
集合の分割

#
# sample04.py : 簡単なプログラム (4)
#
#               Copyright (C) 2018 Makoto Hiroi
#
import functools, math

# 最大公約数 (モジュール math に gcd() がある)

# 末尾再帰
def gcd_rec(a, b):
    if b == 0: return a
    return gcd_rec(b, a % b)

# 繰り返し
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

# 最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)

print("----- gcd -----")
print(gcd_rec(12345678, 123456789))
print(gcd_rec(1234321, 12345654321))
print(gcd(12345678, 123456789))
print(gcd(1234321, 12345654321))
print(functools.reduce(gcd, [123, 12345, 12345678]))
print("----- lcm -----")
print(lcm(5, 7))
print(lcm(14, 35))
print(functools.reduce(lcm, range(2, 21)))
print(functools.reduce(lcm, range(2, 31)))

# 平方根 (ニュートン法)
def sqrt(x):
    def init(x, s = 1.0):
        while s < x:
            s *= 2.0
            x /= 2.0
        return s
    if x < 0:
        raise ValueError('sqrt domain error')
    p = init(x) if x > 1.0 else 1.0
    while True:
        q = (p + x / p) / 2
        if q >= p: break
        p = q
    return p

print('----- sqrt -----')
print(sqrt(0.5))
print(sqrt(2))
print(sqrt(3))
print(sqrt(4))
print(sqrt(5))
print(math.sqrt(0.5))
print(math.sqrt(2))
print(math.sqrt(3))
print(math.sqrt(4))
print(math.sqrt(5))

# めのこ平方
def isqrt(n):
    def isqrt_sub(n, m):
        while n >= m:
            n -= m
            m += 2
        return m // 2
    if n < 100:
        return isqrt_sub(n, 1)
    else:
        m = 10 * isqrt(n // 100)
        return isqrt_sub(n - m * m, 2 * m + 1)

print('----- isqrt -----')
print(isqrt(6789))
print(isqrt(123456789))
print(isqrt(1234567890))

#
# 素因数分解
#
def factorization(n):
    def factor_sub(n, m):
        c = 0
        while n % m == 0:
            c += 1
            n //= m
        return c, n
    #
    buff = []
    c, m = factor_sub(n, 2)
    if c > 0: buff.append((2, c))
    c, m = factor_sub(m, 3)
    if c > 0: buff.append((3, c))
    x = 5
    while m >= x * x:
        c, m = factor_sub(m, x)
        if c > 0: buff.append((x, c))
        if x % 6 == 5:
            x += 2
        else:
            x += 4
    if m > 1: buff.append((m, 1))
    return buff

#
# 約数の個数
#
def divisor_num(n):
    a = 1
    for _, x in factorization(n):
        a *= x + 1
    return a

print('----- divisor_num -----')
print(divisor_num(24))
print(divisor_num(12345678))
print(divisor_num(123456789))
print(divisor_num(1234567890))
print(divisor_num(1111111111))

#
# 約数の合計値
#

# σ(p, n) の計算
def div_sum_sub(p, n):
    a = 0
    while n > 0:
        a += p ** n
        n -= 1
    return a + 1

def divisor_sum(n):
    a = 1
    for p, q in factorization(n):
        a *= div_sum_sub(p, q)
    return a

print('----- divisor_sum -----')
print(divisor_sum(24))
print(divisor_sum(12345678))
print(divisor_sum(123456789))
print(divisor_sum(1234567890))
print(divisor_sum(1111111111))

#
# 約数
#

# p ^ q の約数を求める
def divisor_sub(p, q):
    a = []
    for i in range(0, q + 1):
        a.append(p ** i)
    return a

def divisor(n):
    xs = factorization(n)
    ys = divisor_sub(xs[0][0], xs[0][1])
    for p, q in xs[1:]:
        ys = [x * y for x in divisor_sub(p, q) for y in ys]
    return sorted(ys)

print('----- divisor -----')
print(divisor(24))
print(divisor(12345678))
print(divisor(123456789))
print(divisor(1234567890))
print(divisor(1111111111))

#
# 循環小数
#

# 探索 (リストのメソッド index() は ValueError が送出される)
def position(n, xs):
    for i, x in enumerate(xs):
        if x == n: return i
    return -1

# 循環小数 m/n = ([...],[...])
def repdec(m, n):
    xs = []
    ys = []
    while True:
        p = m // n
        q = m % n
        if q == 0:
            ys.append(p)
            return ys, [0]
        else:
            x = position(q, xs)
            if x >= 0:
                ys.append(p)
                return ys[:x+1], ys[x+1:]
            xs.append(q)
            ys.append(p)
            m = q * 10

# 循環小数を分数に直す
def from_repdec(xs, ys):
    # 有限小数の部分を分数に直す
    p0 = functools.reduce(lambda a, x: a * 10 + x, xs, 0)
    q0 = 10 ** (len(xs) - 1)
    # 循環節を分数に直す
    p1 = functools.reduce(lambda a, x: a * 10 + x, ys, 0)
    q1 = (10 ** len(ys) - 1)
    # 有限小数 + 循環節
    a = q0 * q1
    b = q1 * p0 + p1
    c = gcd(a, b)
    return b // c, a // c

print('----- repdec, from_repdec -----')
for x in range(2, 12):
    xs = repdec(1, x)
    print(xs)
    print(from_repdec(*xs))
xs = repdec(355, 113)
print(xs)
print(from_repdec(*xs))

#
# カッコ列
#
def kakko(f, n):
    def kakko_sub(x, y, a):
        if x == y == n:
            f(a)
        else:
            if x < n:
                kakko_sub(x + 1, y, a + '(')
            if y < x:
                kakko_sub(x, y + 1, a + ')')
    kakko_sub(0, 0, '')

print('----- kakko -----')
kakko(print, 3)
kakko(print, 4)

#
# カタラン数
#
def catalan_num(n):
    table = [1] * n
    for i in range(1, n):
        for j in range(i, n):
            table[j] += table[j - 1]
    return table[-1]

print('----- Catalan number -----')
for x in range(1, 11):
    print(catalan_num(x))
print(catalan_num(50))
print(catalan_num(100))

#
# カッコ列と二分木
#

# 葉
class Leaf:
    def __repr__(self): return 'Leaf'

# 節
class Node:
    def __init__(self, l, r):
        self.left = l
        self.right = r
    def __repr__(self):
        return 'Node({}, {})'.format(self.left, self.right)

# 二分木をカッコ列に変換
def kakko_from_tree(tree):
    def sub(tree):
        if isinstance(tree, Leaf):
            return ')'
        else:
            return '(' + sub(tree.left) + sub(tree.right)
    s = sub(tree)
    return s[:-1]

# カッコ列を二分木に変換
def kakko_to_tree(s):
    def sub(i):
        if len(s) <= i:
            return Leaf(), i
        elif s[i] == ')':
            return Leaf(), i + 1
        elif s[i] == '(':
            l, j = sub(i + 1)
            r, k = sub(j)
            return Node(l, r), k
        else:
            raise Exception('kakko_to_tree: illegal char')
    return sub(0)[0]

def test(s):
    print(s)
    t = kakko_to_tree(s)
    print(t)
    u = kakko_from_tree(t)
    print(u)

print('----- kakko to tree, kakko from tree -----')
kakko(test, 3)

#
# 分割数
#
def part_num(n, k):
    if n == 1 or k == 1:
        return 1
    if n < 0 or k < 1:
        return 0
    else:
        return part_num(n - k, k) + part_num(n, k - 1)

def partition_number(n):
    return part_num(n, n)

# 動的法による高速化
def partition_number_fast(n):
    table = [1] * (n + 1)
    for k in range(2, n + 1):
        for m in range(k, n + 1):
            table[m] += table[m - k]
    return table[n]

# 整数の分割
def part_int_sub(n, k, a):
    if n == 0:   print(a)
    elif n == 1: print(a + [1])
    elif k == 1: print(a + [1] * n)
    else:
        if n >= k:
            part_int_sub(n - k, k, a + [k])
        part_int_sub(n, k - 1, a)

def partition_of_int(n): part_int_sub(n, n, [])

print('----- partition number -----')
for x in range(1, 11): print(partition_number(x))
print(partition_number_fast(1000))
print(partition_number_fast(2000))
print(partition_number_fast(4000))
partition_of_int(5)
partition_of_int(6)
partition_of_int(7)

#
# 集合の分割
#
def part_sub(f, ls, a):
    if not ls:
        f(a)
    else:
        for i in range(len(a)):
            a[i].append(ls[0])
            part_sub(f, ls[1:], a)
            a[i].pop()
        a.append([ls[0]])
        part_sub(f, ls[1:], a)
        a.pop()

def partition_of_set(f, ls):
    part_sub(f, ls[1:], [[ls[0]]])

print('----- partition of set -----')
partition_of_set(print, [1,2,3])
partition_of_set(print, [1,2,3, 4])

----- gcd -----
9
121
9
121
3
----- lcm -----
35
70
232792560
2329089562800
----- sqrt -----
0.7071067811865475
1.414213562373095
1.7320508075688772
2.0
2.23606797749979
0.7071067811865476
1.4142135623730951
1.7320508075688772
2.0
2.23606797749979
----- isqrt -----
82
11111
35136
----- divisor_num -----
8
24
12
48
16
----- divisor_sum -----
60
27319968
178422816
3211610688
1246404096
----- divisor -----
[1, 2, 3, 4, 6, 8, 12, 24]
[1, 2, 3, 6, 9, 18, 47, 94, 141, 282, 423, 846, 14593, 29186, 43779, 87558,
 131337, 262674, 685871, 1371742, 2057613, 4115226, 6172839, 12345678]
[1, 3, 9, 3607, 3803, 10821, 11409, 32463, 34227, 13717421, 41152263, 123456789]
[1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90, 3607, 3803, 7214, 7606, 10821, 11409,
 18035, 19015, 21642, 22818, 32463, 34227, 36070, 38030, 54105, 57045, 64926, 68454,
 108210, 114090, 162315, 171135, 324630, 342270, 13717421, 27434842, 41152263,
 68587105, 82304526,  123456789, 137174210, 205761315, 246913578, 411522630,
 617283945, 1234567890]
[1, 11, 41, 271, 451, 2981, 9091, 11111, 100001, 122221, 372731, 2463661, 4100041,
 27100271, 101010101, 1111111111]
----- repdec, from_repdec -----
([0, 5], [0])
(1, 2)
([0], [3])
(1, 3)
([0, 2, 5], [0])
(1, 4)
([0, 2], [0])
(1, 5)
([0, 1], [6])
(1, 6)
([0], [1, 4, 2, 8, 5, 7])
(1, 7)
([0, 1, 2, 5], [0])
(1, 8)
([0], [1])
(1, 9)
([0, 1], [0])
(1, 10)
([0], [0, 9])
(1, 11)
([3], [1, 4, 1, 5, 9, 2, 9, 2, 0, 3, 5, 3, 9, 8, 2, 3, 0, 0, 8, 8, 4, 9, 5, 5, 7, 5,
 2, 2, 1, 2, 3, 8, 9, 3, 8, 0, 5, 3, 0, 9, 7, 3, 4, 5, 1, 3, 2, 7, 4, 3, 3, 6, 2, 8,
 3, 1, 8, 5, 8, 4, 0, 7, 0, 7, 9, 6, 4, 6, 0, 1, 7, 6, 9, 9, 1, 1, 5, 0, 4, 4, 2, 4,
 7, 7, 8, 7, 6, 1, 0, 6, 1, 9, 4, 6, 9, 0, 2, 6, 5, 4, 8, 6, 7, 2, 5, 6, 6, 3, 7, 1,
 6, 8])
(355, 113)
----- kakko -----
((()))
(()())
(())()
()(())
()()()
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
----- Catalan number -----
1
2
5
14
42
132
429
1430
4862
16796
1978261657756160653623774456
896519947090131496687170070074100632420837521538745909320
----- kakko to tree, kakko from tree -----
((()))
Node(Node(Node(Leaf, Leaf), Leaf), Leaf)
((()))
(()())
Node(Node(Leaf, Node(Leaf, Leaf)), Leaf)
(()())
(())()
Node(Node(Leaf, Leaf), Node(Leaf, Leaf))
(())()
()(())
Node(Leaf, Node(Node(Leaf, Leaf), Leaf))
()(())
()()()
Node(Leaf, Node(Leaf, Node(Leaf, Leaf)))
()()()
----- partition number -----
1
2
3
5
7
11
15
22
30
42
24061467864032622473692149727991
4720819175619413888601432406799959512200344166
1024150064776551375119256307915896842122498030313150910234889093895
[5]
[4, 1]
[3, 2]
[3, 1, 1]
[2, 2, 1]
[2, 1, 1, 1]
[1, 1, 1, 1, 1]
[6]
[5, 1]
[4, 2]
[4, 1, 1]
[3, 3]
[3, 2, 1]
[3, 1, 1, 1]
[2, 2, 2]
[2, 2, 1, 1]
[2, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]
[7]
[6, 1]
[5, 2]
[5, 1, 1]
[4, 3]
[4, 2, 1]
[4, 1, 1, 1]
[3, 3, 1]
[3, 2, 2]
[3, 2, 1, 1]
[3, 1, 1, 1, 1]
[2, 2, 2, 1]
[2, 2, 1, 1, 1]
[2, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1]
----- partition of set -----
[[1, 2, 3]]
[[1, 2], [3]]
[[1, 3], [2]]
[[1], [2, 3]]
[[1], [2], [3]]
[[1, 2, 3, 4]]
[[1, 2, 3], [4]]
[[1, 2, 4], [3]]
[[1, 2], [3, 4]]
[[1, 2], [3], [4]]
[[1, 3, 4], [2]]
[[1, 3], [2, 4]]
[[1, 3], [2], [4]]
[[1, 4], [2, 3]]
[[1], [2, 3, 4]]
[[1], [2, 3], [4]]
[[1, 4], [2], [3]]
[[1], [2, 4], [3]]
[[1], [2], [3, 4]]
[[1], [2], [3], [4]]

Python3 Programming

お気楽 Python3 プログラミング超入門

●キュー

●プライオリティキュー

●bytes と bytearray

●array

●ソート

●bisect

●簡単なプログラム (4)