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

同じものを含む順列の問題を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);    

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

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

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

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

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

● 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 tm=time()

p = list('MATHEMATICS')
r=4
count=0
for q in genPerm(p,r):

    count+=1
print(u"計: "+str(count))

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

if name == 'main': main()

●実行結果

計: 2454 Runtime : 0.053 [sec]