バックトラック版

　先日、バックトラックによらない麻雀の待ちを探索するPythonコードを張っておいたが、しばらくして、なんだかバックトラックのプログラムが書けないのではないかと思い、バックトラック版も書いた。ここに張っておく。
　計算量とか薀蓄とかその他どうでもよさそうなことはまた後ほど書く。今はSchemeで書いてみたいと思っている。
　因みに、このプログラムは可能な全組合せについて判定するようにしてある。全データカバレッジテストとでもいうのかな。しかしながら、全組合せが幾つあるのか手計算できずにいる（笑）。また、プロセス実行時間を簡単に計れないシステムを考慮して、実行の最初と最後に時間を出力している。10万行以上出力されるので、先頭行と最後の行を比較して処理時間を出してくれ。
　λ式を使えば、もっと短いプログラムになりそうな気がするが、後ほど考えてみよう。

#-------------------------------------------------------------------------------
# Name:        Ready Hand Judgement
# Purpose:     To judge wheather a hand in mahjong is ready or not
#
# Author:      Matthew
#
# Version:     0.2
# Created:     14/04/2010
# Copyright:   (c) Matthew 2010
# Licence:     GPL Ver. 3
#-------------------------------------------------------------------------------
#!/usr/bin/env python

import sys
from datetime import datetime, date, time

def check_ready(hand):
    hand = sorted(list(hand))

    # waiting for the only tile for a pair
    bfr = []
    for i in hand:
        waiting = '[%1s]'%(i)
        if waiting in bfr: continue
        rest = hand[:]
        rest.remove(i)
        search(rest, waiting, [])
        bfr.append(waiting)

    # waiting for the middle in a sequence
    bfr = []
    for i in hand:
        j = int(i)
        if str(j + 2) in hand:
            waiting = '[%1d%1d]'%(j, j + 2)
            if waiting in bfr: continue
            rest = hand[:]
            rest.remove(i)
            rest.remove(str(j + 2))
            search(rest, waiting, [])
            bfr.append(waiting)

    # waiting for either of two gates and
    # waiting for three or seven the tile
    bfr = []
    for i in hand:
        j = int(i)
        if str(j + 1) in hand:
            waiting = '[%1d%1d]'%(j, j + 1)
            if waiting in bfr: continue
            rest = hand[:]
            rest.remove(i)
            rest.remove(str(j + 1))
            search(rest, waiting, [])
            bfr.append(waiting)

    # waiting for a triplet
    bfr = []
    for i in hand:
        if hand.count(i) > 1:
            waiting = '[%1s%1s]'%(i, i)
            if waiting in bfr: continue
            rest = hand[:]
            rest.remove(i)
            rest.remove(i)
            search(rest, waiting, [])
            bfr.append(waiting)

def show_ready(elements, waiting):
    for i in elements:
        sys.stdout.write(i)
    sys.stdout.write(waiting)
    sys.stdout.write('\n')

def search(rest, waiting, elements):
    # show ready hands
    if not rest:
        if len(elements) == 4 or len(elements) == 6:
            show_ready(elements, waiting)
        return

    # head or pair(included in elements)
    r, t = rest[:], rest[0]
    if r.count(t) == 2:
        elements.append('(%1s%1s)'%(t, t))
        r.remove(t)
        r.remove(t)
        search(r, waiting, elements)
        elements.pop()

    # triplet
    r, t = rest[:], rest[0]
    if r.count(t) > 2:
        elements.append('(%1s%1s%1s)'%(t, t, t))
        r.remove(t)
        r.remove(t)
        r.remove(t)
        search(r, waiting, elements)
        elements.pop()

    # sequence
    r, t = rest[:], rest[0]
    if str(int(t) + 1) in r and str(int(t) + 2) in r:
        elements.append('(%1s%1s%1s)'%(t, str(int(t) + 1), str(int(t) + 2)))
        r.remove(t)
        r.remove(str(int(t) + 1))
        r.remove(str(int(t) + 2))
        search(r, waiting, elements)
        elements.pop()

# a kind of homogeneous product generator
def hp(list, counter, n):
    if n == 0: return [[]]
    tuples = []
    for i, x in enumerate(list):
        if counter[i] > 0:
            counter[i] -= 1
            tuples.extend([[x] + l for l in hp(list[i:], counter[i:], n - 1)])
    return tuples

def main():
    pass

if __name__ == '__main__':
    main()

# data coverage test
print datetime.now()
c = hp([1, 2, 3, 4, 5, 6, 7, 8, 9], [4, 4, 4, 4, 4, 4, 4, 4, 4], 13)
for i in c:
    check_ready("".join(map(str, i)))
print datetime.now()