順列の2008番目 - わさっきhb

takehikomという文字列の文字を並び替えてできる文字列(takehikom自体を含む)のうち，辞書順で2008番目にくる文字列を求めなさい．

一つ一つ文字列を作るのも手間なので，もう少し問題を一般化してから，それを求めるRuby スクリプトを書くことにします．

以下の処理をするプログラムを作りなさい．
入力: 文字列s，正整数i
出力: sの文字を並び替えてできる文字列(s自体を含む)の集合のうち，辞書順でi番目の文字列

なお，文字列の中に同一文字があっても，正しく動くようにします．
さっそく，プログラムです．

#!/usr/bin/env ruby

# permutation2.rb

$KCODE='u'
require 'strscan'

class Permutation
  # コンストラクタ
  def initialize(str = 'ABCD')
    @original = str
    @seed = str.split(//u).sort
    @seed_s = @seed.join('')
  end

  # 階乗を求める
  def factorial(num)
    (1..num).inject(1) {|result, i| result * i}
  end

  # 順列の総数を求める
  def total(str = @seed_s)
    t = factorial(str.length)
    ss = StringScanner.new(str)
    while !ss.eos?
      t = t / factorial(ss.scan(/(.)\1*/u).length)
    end
    t
  end

  # 辞書順でpos番目の文字列を求める
  def sequence(pos)
    if pos <= 0 or pos > total
      raise "out of range"
    end
    pos -= 1

    @seed.uniq.each do |c|
      seed2_s = @seed_s.sub(/#{c}/, '')
      total2 = total(seed2_s)
      if pos < total2
        return c.to_s + Permutation.new(seed2_s).sequence(pos + 1)
      end
      pos -= total2
    end
    return ""
  end
end

if __FILE__ == $0
  str = ARGV.shift || 'ABCD'
  pos = (ARGV.shift || 10).to_i
  puts Permutation.new(str).sequence(pos)
end

動作確認．なお，permutation1.rb というファイルもあるのですが未公開です．

$ ruby permutation2.rb takehikom 2008
aeokmkith

プログラムの解説ですが，辞書順でpos番目の文字列を求めるメソッドsequenceが肝心なところです．一般に「〜番目」は1オリジン*1ですが，処理するにあたり「pos -= 1」として，0オリジンにしておきます*2．こうすると，例えば与えられた文字列が"ABCD"として順列を作ると，

Aから始まる文字列の位置は0〜5
Bから始まる文字列の位置は6〜11
Cから始まる文字列の位置は12〜17
Dから始まる文字列の位置は18〜23

となります．先頭を取り出すと，0, 6, 12, 18と，等差数列になっていますが，これは，

Aから始まる文字列の総数は，Aを取り除いたBCDを並べ替えてできる文字列の数，すなわち6
Bから始まる文字列の総数は，Bを取り除いたACDを並べ替えてできる文字列の数，すなわち6
Cから始まる文字列の総数は，Cを取り除いたABDを並べ替えてできる文字列の数，すなわち6
Dから始まる文字列の総数は，Dを取り除いたABCを並べ替えてできる文字列の数，すなわち6

だからです．
"AAB" や "takehikom" ("aehikkmot")のように，文字列の中に同一文字があっても，考え方は同じです．もとの文字列が "AAB" のときは，

Aから始まる文字列の位置は(ABを並び替えるのだから2通りで)，0〜1
Bから始まる文字列の位置は(AAを並び替えるのだから1通りで)，2

となります．このとき，2番目のAから始まる文字列というのは，考えません．先頭に来ることのできる文字は，sequenceメソッドの中で「@seed.uniq.each」として，重複なく1つずつ取り出しています．
そして，「先頭に置く1文字を取り除いた文字列を並べ替えてできる文字列の数」は，totalメソッドに，残りの文字列を引数に与えれば，求められますね．
ということで例えば，デフォルト入力の「ABCDを並べ替えてできる10番目の文字列」は，

番目を0オリジンで9として，
Aから始まる文字列かというと，total("BCD") = 6 をposから引いても0以上なので，そうではなく(posは6引いておく)，
Bから始まる文字列かというと，total("ACD") = 6 をposから引くことができないので，これが当たりで，
ACD を並べ替えてできる3+1番目になる文字列を再帰的に求め，Bと結合すれば出来上がり

となります．最後に「+1」をしているのは，メソッドの引数としては，位置は1オリジンだからです．

*1:http://d.hatena.ne.jp/takehikom/20080101/1199137523

*2:常に1オリジンで処理することもできます．その際，「if pos < total2」にも変更が必要です．