辞書順で何番目か（Ruby）

辞書順（lexicographical order）に並べて何番目か、あるはn番目のものは何か。

要素に重複がないとして考える。数列 (1, 2, .... , n) の並べ替えとして解こう。

数列 (a₁, .. , a_n) は辞書順で何番目か。

def number_in_lex_order(ary)
  n = ary.size
  return 1 if n <= 1
  idx = ary.sort.bsearch_index { _1 >= ary[0] }
  (1..n - 1).inject(:*) * idx + number_in_lex_order(ary[1..-1])
end

number_in_lex_order([2, 1, 5, 3, 4])    #=>29

ここでは、数列の左端の数字が、数列を昇順にソートした中で何番目に来るかがわからなければならない。それを i (=idx+1) とすると、そこまでで (n - 1)! * (i - 1) だけ既に（一桁少ない部分）数列が並んでいることになる（ただし n は ary の桁数）。
あとは左端の一桁を落として同じことを（再帰で）求め、すべての和をとってやれば求まる。

文字列などならば、ハッシュで数列に変換するテーブルを作ってやればよい。

str = "MATH"
h = "AHMT".each_char.with_index(1).to_h

number_in_lex_order(str.each_char.map { h[_1] })    #=>14

もっとも、文字列ならば Ruby の柔軟性（？）のおかげで、

number_in_lex_order("MATH".chars)    #=>14

で求まってしまうのだが。

これの逆、つまり辞書順でn番目の数列はどうなるか。この場合、数列の長さ（size）を与えることが必要である。

def nth_sequence_in_lex_order(n, size)
  i = 1
  table = (1..size - 1).map { i *= _1 }
  
  order = (1..size).to_a
  ans = []
  n -= 1
  size.pred.times do
    factorial = table.pop
    i = n / factorial
    n -= i * factorial
    ans << (a = order[i])
    order.delete(a)
    break if n <= 0
  end
  ans.concat(order)
end

やってみる。

nth_sequence_in_lex_order(29, 5)     #=>[2, 1, 5, 3, 4]

よさそうだ。

上と同様に、文字列でもやってみる。これも、ハッシュでテーブルを作り、Hash#invert する。

h = "AHMT".each_char.with_index(1).to_h.invert

nth_sequence_in_lex_order(14, 4).map { h[_1] }.join    #=>"MATH"

これもよさそうだ。

なお、いずれも不正入力には対応していない。