読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

Rubyで任意の順列の次を求める

next_permutation in Ruby

他言語にはnext_permutationがあるのにRubyに無いのはけしからん、ということでnext_permutationを実装しました。 比較可能なオブジェクトからなる配列を渡すだけです。O(n)なので[*1..n]の全順列をiterateする場合はArrayのpermutationの方が圧倒的に速いです。4倍の差がある。あくまでも途中から次のやつ知りたい時専用です。あと、向こうは配列の中のオブジェクトの大小を見ていないのも違う所。 bsearch_indexを使っているので、ちょっと古いRubyだとmethod_missingになりそう。その時はary.each_with_index.bsearch{...}.lastなんかで取り出せばOK。

#!ruby
#O(n)
def next_perm(ary)
    size=ary.size
    return nil if size<2
    #後ろから順に数値が減少する箇所を探す
    idx=nil
    (size-2).downto(0){|i|
        if ary[i]<ary[i+1]
            idx=i
            break
        end
    }
    #条件を満たす箇所が見つからない場合は、後ろから昇順(前からは降順)になっているので最後の順列
    return nil unless idx

    #idxより右側を順列と考えると、左から降順ということは、このpermutationでは大きくなれない
    #したがって、ary[idx],b=ary[idx+1...size]を"繰り上げ"処理する必要がある
    #実際には、bからary[idx]の次に大きいものを見つけ(idxでary[idx]が下がっているのでかならず見つかる)
    #ary[idx]と場所を交換しbをsortすれば良い
    ary[idx+1...size]=ary[idx+1...size].reverse
    jdx=ary[idx+1...size].bsearch_index{|v|ary[idx]<v}
    ary[idx],ary[idx+1+jdx]=ary[idx+1+jdx],ary[idx]
    ary
end

ちなみにGoogle Code Jan Round 1B 2009 B. The Next Numberもこれを使えばほぼ一発です。

def solve(str)
  a=str.chars.map(&:to_i)
  np=next_perm(a.dup)
  if np
    return np*""
  else
    ls="0"
    ls+=a.pop.to_s while a.last==0
    return a.pop.to_s+ls+(a.sort*"")
  end
end