同じものを含む順列の問題をPythonで解いてみた。

Python

　同じものを含む順列の問題をPythonで解いてみました。(^_^;

「MATHEMATICS」の11文字から4文字を取りだして1列に並べる方法は何通りあるか？

　Pythonでは、同じものを含む順列を生成させようとするとダブってしまうようなのでJavaから翻訳して作ってみました。(^_^;
　ちなみに、Pythonのitertools.permutationsより倍ぐらい遅いですが、同じものを含む順列や辞書式順列の生成にも使えます。

　JavaからPythonへの翻訳で苦労したとこは、たとえば、下のような場合、Javaではforループを抜けた後のカウンター変数 i の値は10になりますが、Pythonの場合そうはならないようで、それになかなか気づけず原因不明のエラーに悩まされてしまいました。(^_^;

    int i;
    for(i=0; i< 10; i++)
        ;
    System.out.println(i);    // 10

　Pythonの場合、これだと、ループを抜けた後のカウンター変数 i の値は9になります。

    for i in range(10):
        pass
    print(i) # 9

　それで、ループを抜けた後のカウンター変数 i の値を10にするには次のように書かなければなりませんでした。(^_^;

    for i in range(10):
        pass
    else: i+=1
    print(i) # 10

※参考URL
●同じものを含む順列をJavaで解いてみた。(2)
●同じものを含む順列の問題をPythonで解いてみた。(2)
●同じものを含む順列の問題を十進BASICで解いてみた。
●同じものを含む順列の問題をVisual Basicで解いてみた。

● PermSame1.py

# coding: UTF-8
# PermSame1.py

from time import time

# 順列生成
def nextPerm(p, n, r):
    if r <= 0 or n < r : return False
    i = j = 0 
    for i in range(r+1,n):
        for j in range(i,r,-1):
            if not 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 not p[i-1] >= p[i]: break
    else: i-=1
    if i==0: return False
    for j in range(n-1,i,-1):
        if not 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 main():
    pass # code goes here
    tm=time()  # Timer Start

    p = list('MATHEMATICS')
    r=4
    count=0
    for q in genPerm(p,r):
##        print(q[:r])
        count+=1
    print(u"計: "+str(count))

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

if __name__ == '__main__':
    main()

●実行結果

計: 2454
Runtime : 0.053 [sec]