知恵袋で見つけた赤玉と白玉の組分けの問題をPythonで解いてみた。

赤玉が１０個、白玉が９０個、計１００個の玉をA,B,C,Dのボックスに１０個ずつ分ける。同じ色の玉は区別しないとして、玉の入れ方は何通りあるか。

　初め、「set(itertools.permutations(p))」で同じものを含む順列を生成させてやってみましたが、rが8個目ぐらいから急に減速するので途中で諦めてしまいました。(^_^;
　そこで、前回はJavaで解きましたが、今回は以前、JavaからPythonに翻訳して作ったgenPerm(p,r)関数を使ってPythonで解いてみました。(^_^;
　なんか、あっさり解けてしまいましたが、なぜ「set(itertools.permutations(p))」じゃ、上手くいかないのかは謎です。恐らく、同じものも異なるものとして順列を生成しているからなのかな。(^_^;
　ちなみに、以前のnextPerm(p,n,r)関数は、なんかバグがあったみたいなので修正しておきました。(^_^;

● RWBalls2.py

# coding: UTF-8
# RWBalls2.py

# 順列生成
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 main():
    from time import time
    tm=time()  # Timer Start

    total = 0
    for n in range(10+1):
        s = 'r'*n+'|||'
        subTotal = 0
        for p in genPerm(list(s)):    # 同じものを含む順列
            subTotal+=1
        total+=subTotal
        print("%13s :%5d"%(s,subTotal))

    print("%11s :%5d"%(u"合計",total))
    tm=time()-tm  # Timer Stop
    print("Runtime : %.3f [sec]"%tm)

if __name__ == '__main__':
    main()

●実行結果

          ||| :    1
         r||| :    4
        rr||| :   10
       rrr||| :   20
      rrrr||| :   35
     rrrrr||| :   56
    rrrrrr||| :   84
   rrrrrrr||| :  120
  rrrrrrrr||| :  165
 rrrrrrrrr||| :  220
rrrrrrrrrr||| :  286
         合計 : 1001
Runtime : 0.016 [sec]

※参考URL
●知恵袋で見つけた赤玉と白玉の組分けの問題をJavaで解いてみた。(2)
●同じものを含む順列の問題をPythonで解いてみた。