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

せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【Ruby】【アルゴリズム】重複を含む要素の順列(非数値もOK)

重複を含む順列

重複を含む要素のすべての順列を求める

(例)
"3331"→1333,3133,3313,3331
"aab"→aab,aba,baa

たとえば "aabb" だったら4!/(2!*2!) で6通り。

 
コードで書くとこういう感じ。
使った要素はフラグを立てて、使っていない要素を配列につめていく。
 
重複順列は、これ以上簡単な書き方はないと思うんだけど、、
どうかなー。
 

def _permutation(arr, candidate, answers, isused)
  if candidate.length == arr.length
    a = candidate.join("")
    answers << a if !answers.include?(a)
    return
  end
  (0...arr.length).each do |i|
    tmp = candidate.dup
    _isused = isused.dup
    if _isused[i] == 0
      tmp << arr[i] 
      _isused[i] = 1
      _permutation(arr, tmp, answers, _isused)
    end
  end
  answers
end
def permutation(input)
  arr = input.split("")
  return _permutation(arr, [] ,[],Array.new(arr.size, 0))
end
p permutation("aabb")

 
■実行結果

["aabb", "abab", "abba", "baab", "baba", "bbaa"]

 
これくらいならさくさく書けるようになってきたー。