find one-to-one mapping algorithm

reduce_mapping.rb

def reduce_mapping1(f, a=nil)
  _f = a ? a.map{|i|f[i-1]}.uniq : f.map{|i|f[i-1]}.uniq # 最初のループならfのuniqをとる、２周目以降ならreduceしたaのuniqをとる
  a_size = a ? a.size : f.size # reduceしたaのサイズ(最初はfのサイズ)
  a_size > _f.size ? reduce_mapping1(f, _f.sort) : _f.sort # reduceできたら再帰、できなかったらその配列をソートして返す
end
# 最大n-1回計算するのでO(n)はn
# かぶりが多いと早い、かぶり少ないと遅い

def reduce_mapping2(f)
  n=f.size # 写像の要素数
  s=[*1..n] # 部分集合S
  c=[] # カウンタ
  q=[] # キュー
  n.times { c << 0 } # カウンタを0で初期化
  [*1..n].each { |i| c[f[i-1]-1] += 1 } # カウンタを用意（写像の到達数を要素ごとに計算している）
  [*1..n].each { |i| q<<i if c[i-1] == 0 } # キューを用意（到達する写像のない要素）
  while q.size>0 do
    qi=q.pop # 最後のキューを取り出す
    s.delete_at(qi-1) # 到達しない要素を削除
    c[f[qi-1]-1] -= 1 # 削除した要素から到達する要素のカウンタを1減らす
    q.push(f[qi-1]) if c[f[qi-1]-1] == 0 # 到達する写像がなくなったらその要素をキューにいれる
  end
  s
end
# 写像によってはうまく処理できない問題がある
# 削除した要素の到達先が削除した要素より大きい場合delete_atで削除できなくて残ってしまう
# delete_atできないときはdeleteで直接消したほうがいいかも
# 最大n-1回計算するのでO(n)はn
# かぶりが多いと遅い、かぶり少ないと早い

@f=[3,1,1,5,5,4,6]
p reduce_mapping1(@f) # => [1, 3, 5]
p reduce_mapping2(@f) # => [1, 3, 5]