順列を順番にすべて

いきなりですが問題です．順列の2008番目 - わさっきの続編です．

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

コードです．

#!/usr/bin/env ruby

# permutation3.rb

$KCODE='u'
require 'strscan'

class Permutation
  include Enumerable

  # コンストラクタ
  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_takehikom(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
  def total_trotr(str = @seed_s)
    # http://d.hatena.ne.jp/takehikom/20080313/1205355908#c1205825580
    h = Hash.new {|h, k| h[k] = 0}
    a = str.split(//u).inject(h) {|h, e| h[e] += 1; h}.map{|k,v| v}
    a.inject(factorial(str.length)) {|re, e| re / factorial(e)}
  end
  alias :total :total_takehikom

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

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

  # 辞書順に取り出す
  def each
    1.upto(total) do |i|
      yield(sequence(i))
    end
    self
  end
end

if __FILE__ == $0
  str = ARGV.shift || 'ABCD'
  pos = ARGV.shift.to_i
  p = Permutation.new(str)

  if pos > 0
    # 第2引数があれば，辞書順でその値の番目にある文字列のみ
    puts p.sequence(pos)
  else
    # 第2引数がなければ，番目つきで順に出力
    p.each_with_index do |str2, i|
      printf("%6d : %s\n", i + 1, str2)
    end
  end
end

小さな修正点として，sequenceの中のposは常に1オリジンにしています．それと，http://d.hatena.ne.jp/takehikom/20080313/1205355908#c1205825580の提案を取り入れました．
さて，文字列を順にすべて取り出すのは，Enumerableを使えばよさそうに思えたのですが，eachメソッドの定義の仕方でいいのが思いつかず，添付ライブラリを見てみました…set.rbから，要所を抜き出してみます．

class Set
  include Enumerable

  def each
    @hash.each_key { |o| yield(o) }
    self
  end

なるほど，クラス定義の中で「include Enumerable」と書き，eachメソッドは，順に取り出すブロック付きメソッド呼び出しで，中を「yeild(オブジェクト)」とすればいいのですね．
ということで，上述のコードになりました．
実行時間ですが，「ruby permutation3.rb takehiko | wc」で計ると，31秒．次に

  alias :total :total_takehiko

を

  alias :total :total_trotr

に置き換えてから，同じコマンドを実行すると，55秒．
あれれ，trotrさんのコードのほうが，ライブラリを使わない分，効率がいいと思っていたら，そうはならなかったので，驚きでした．添付ライブラリstrscanの威力ということでしょうか．あるいは，trotrさんのコードを使うのなら，文字列処理ではなく配列処理にして，「split(//u)」*1を消すことで，時間短縮できるかもしれません．
さて，このプログラムの出力結果が正しいことを確認しないといけませんね．また後日に．

*1:提案コードは「split(//)」でした．比較すると，「split(//u)」のほうが少し時間がかかりますが，増加分は1%に満たないものです．