同じものを含む組合せの質問をPythonで解いてみた。

　同じものを含む組合せの質問をPythonで解いてみました。(^_^;
　以前、『同じものを含む組合せの質問をJavaで解いてみた。』のとこで書いたJavaのプログラムをPythonに翻訳してみました。(^_^;

● CombSame1.py

# coding: UTF-8
# CombSame1.py

from time import time

# 順列生成
def nextPerm(p, n, r):
    i = j = 0   # bug fix
    if r <= 0 or n < r : return False
    for i in range(r+1,n):
        for j in range(i,r,-1):
            if p[j-1] >= p[j]: break
            p[j], p[j-1] = p[j-1], p[j]

    for i in range(n-1,0,-1):
        if p[i-1] < p[i]: break
    else: i-=1
    if i==0: return False
    for j in range(n-1,i,-1):
        if p[i-1] < p[j]: break
    else: j-=1
    p[i-1], p[j] = p[j], p[i-1]
    j = n-1
    while i < j:
        p[i], p[j] = p[j], p[i]
        i+=1; j-=1
    return True

def genPerm(p,r=0):
    n=len(p)
    if r==0: r=n
    q= p[:]; q.sort()
    while True:
        yield q
        if not nextPerm(q,n,r): break

# 組合せ生成
def nextComb(p, n, r):
    while True:
        if not nextPerm(p,n,r): return False
        for i in range(r-1):
            if p[i]> p[i+1]: break
        else: i+=1
        if i==r-1: break
    return True

def genComb(p,r=0):
    n=len(p)
    if r==0: r=n
    q= p[:]; q.sort()
    while True:
        yield q
        if not nextComb(q,n,r): break

def main():
    pass # code goes here
    tm=time()  # Timer Start

##    p = list('wwrrrbbbb')
    p = list(u'白白赤赤赤青青青青')
    r=5
    count=0
    for q in genComb(p,r):
        count+=1
        print("".join(q[:r]))
    print(u"計: "+str(count))

    tm=time()-tm  # Timer Stop
    print("Runtime : %.3f [sec]"%tm)

if __name__ == '__main__':
    main()

●実行結果

白白赤赤赤
白白赤赤青
白白赤青青
白白青青青
白赤赤赤青
白赤赤青青
白赤青青青
白青青青青
赤赤赤青青
赤赤青青青
赤青青青青
計: 11
Runtime : 0.005 [sec]

※参考URL
http://stackoverflow.com/questions/4978787/how-to-split-a-string-into-array-of-characters-with-python
http://stackoverflow.com/questions/5618878/how-to-convert-list-to-string
http://stackoverflow.com/questions/2612802/how-to-clone-or-copy-a-list-in-python

　ちなみに、組合せの出力が辞書式順序にならなくてもいいから高速で求めたいときは、次のようにすると簡単に求めることが出来ます。(^_^;

● CombSame2.py

# coding: UTF-8
# CombSame2.py

import itertools
from time import time

def main():
    pass # code goes here
    tm=time()  # Timer Start

##    p = list('wwrrrbbbb')
    p = list(u'白白赤赤赤青青青青')
    r=5
    count=0
    for q in list(set(itertools.combinations(p,r))):
        count+=1
        print "".join(q[:r])
    print u"計: "+str(count)

    tm=time()-tm  # Timer Stop
    print "Runtime : %.3f [sec]"%tm

if __name__ == '__main__':
    main()

●実行結果

白白赤赤青
白白青青青
赤赤青青青
白赤赤青青
赤赤赤青青
白青青青青
赤青青青青
白白赤青青
白赤青青青
白白赤赤赤
白赤赤赤青
計: 11
Runtime : 0.000 [sec]

Pythonスタートブック

初めてのPython 第3版

パーフェクトPython (PERFECT SERIES 5)