CodeIQ GemString問題のコード

結城浩さんのCodeIQ「The Essence of Programming」

https://codeiq.jp/ace/yuki_hiroshi/

のGemString問題の解答用のrubyのコードです。

# abbbbcddddeefggg = [1,4,1,4,2,1,3] # eagcdfbe <== goal # ---------------------------------------------------------------- # ---------------------------------------------------------------- # allcomb([3,1,2],4) => [[3,1,0],[3,0,1],[2,1,1],[2,0,2],[1,1,2]] # 重複するものも含む素材個数リストstlから、計sum個の素材セットを選んで列挙する。 def allcomb(stl,sum) if sum<0 [] elsif stl.length<=1 if stl[0]<sum [] elsif sum==0 [[0]] else [[sum]] end else ans=[] l=stl.length-1 for i in (0..stl[0]) j=stl[0]-i sans=allcomb(stl[1..l],sum-j) if sans!=[] sans.each{|x| ans << [j]+x } else [] end end ans end end # ---------------------------------------------------------------- # fact(n)=n! 階乗 def fact(n) if n<=1 1 else n*fact(n-1) end end # ---------------------------------------------------------------- # allperm([2,1,2],5) => "aabcc"から5個以下を選んでの順列の総数を返す。 def allperm(stl,mxn) ans=0 for i in (0..mxn) allcomb(stl,i).each{|x| div=1 x.each{|m| div=div*fact(m) } ans=ans+fact(i)/div } end ans end # allperms([2,1,2]) => "aabcc"から部分順列の総数を返す。 def allperms(stl) maxl=0 stl.each{|x| maxl=maxl+x } allperm(stl,maxl) end # ---------------------------------------------------------------- # 素材から、素材集と素材個数リストを返す。 def pattlst(gems) p gems glst=[] gcnt=[] gems.each_char{|c| if !glst.include?(c) glst<<c gcnt<<gems.count(c) end } [glst,gcnt] end </pre> <pre> # ---------------------------------------------------------------- def gemsindex(gem,pat,gal) if gal.length<1 0 else cars=gal[0] cdrs=gal[1..-1] cidx=gem.index(cars) p [cars,cdrs,cidx] ans=0 if cidx>0 for i in (0..cidx-1) tmpat=pat.clone tmpat[i]=tmpat[i]-1 ans=ans+allperms(tmpat) end end ans=ans+1 pat[cidx]=pat[cidx]-1 ans+gemsindex(gem,pat,cdrs) end end # ---------------------------------------------------------------- # 走らせるとこ。サンプルと本題と # ---------------------------------------------------------------- gems='aaabcc' goal='caba' gpat=pattlst(gems) gemm=gpat[0] pats=gpat[1] p gemm,pats p gemsindex(gemm,pats,goal) # ---------------------------------------------------------------- gems='abbbbcddddeefggg' goal='eagcdfbe' gpat=pattlst(gems) gemm=gpat[0] pats=gpat[1] p gemm,pats p gemsindex(gemm,pats,goal) # 実行結果 # 〜------------------------------------ results 10:15:48 u "aaabcc" ["a", "b", "c"] [3, 1, 2] ["c", "aba", 2] ["a", "ba", 0] ["b", "a", 1] ["a", "", 0] 144 "abbbbcddddeefggg" ["a", "b", "c", "d", "e", "f", "g"] [1, 4, 1, 4, 2, 1, 3] ["e", "agcdfbe", 4] ["a", "gcdfbe", 0] ["g", "cdfbe", 6] ["c", "dfbe", 2] ["d", "fbe", 3] ["f", "be", 5] ["b", "e", 1] ["e", "", 4] 5578864439

タグ：Ruby CodeIQ 順列組合せ