数え上げよう（順列編）

順列を数え上げる場合、n個の置換を生成する関数を作って、組み合わせを生成する関数から呼ぶことにする。手抜きですね。

require "Combination"

class Permutation
  def Permutation.each(ary)
    case ary.size
    when 1
      yield ary
    when 2
      yield ary
      yield ary.reverse
    else
      for i in 0...ary.size
        for j in 0...ary.size
          if i > j
            a = ary.clone
            b = a.slice!(i)
            c = a.slice!(j)
            Permutation.each(a) do |item|
              yield [b,c] + item
            end
          elsif i < j
            a = ary.clone
            c = a.slice!(j)
            b = a.slice!(i)
            Permutation.each(a) do |item|
              yield [b,c] + item
            end
          end
        end
      end
    end
  end

  def Permutation.eachSeq(n,k)
    if n < k
      return
    end
    Combination.eachSet(n,k) do |c|
      Permutation.each(c) do |a|
        yield a
      end
    end
  end
end

n=4 k=2 のときは、 を意味していて、 [0,1] から [3,2] までのように 0 から 3 までの数字から 2 つ取り出す方法を配列に並べて出力します。順序は辞書式ではありません。

Permutation.eachSeq(4,2) do |c|
  p c
end

[0, 1]
[1, 0]
[0, 2]
[2, 0]
[1, 2]
[2, 1]
[0, 3]
[3, 0]
[1, 3]
[3, 1]
[2, 3]
[3, 2]

パフォーマンスは

n = 15
k = 5
count = 0
t = Time.now
Permutation.eachSeq(n,k) do |c|
  count += 1
end
p Time.now - t
p count

Intel Core2 2.13GHz Linux ruby1.8.6 で

5.735
360360

でした。36万の列挙に5.7秒。手抜きしているので遅いですな。