トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

ダブリング

[アルゴリズム]

ダブリング

ダブリング(Doubling?)で検索しても、いい資料が出てこない

  アルゴリズム

  • 以下のような構造があるとする
    • サイズ n の配列 T

T%5Bn%5D+%3D+%5Cbigl%7B+1%2C+2%2C+3%2C+4%2C+5%2E%2E%2En+%5Cbigr%7D+

愚直な方法

    • 配列の指す先は以下のように求められる
      • 1回ループ

T%5BT%5Bx%5D%5D+

      • 2回ループ

T%5BT%5BT%5Bx%5D%5D%5D+

      • Rubyでやってみる
T = [0, 1, 2, 3, 4].shuffle
puts T.to_s
N = 3

puts "...itarate suffix of array indices"
T1  = T[N]
puts "T1 = T[N] (#{T[N]})"
T2  = T[T[N]]
puts "T2 = T[T[N]] (#{T[T[N]]})"
T3  = T[T[T[N]]]
puts "T3 = T[T[T[N]]] (#{T[T[T[N]]]})"
T4  = T[T[T[T[N]]]]
puts "T4 = T[T[T[T[N]]]] (#{T[T[T[T[N]]]]})"
  • 出力
    • 当然ちゃんと行き先がわかる
[3, 1, 0, 2, 4]
...itarate suffix of array indices
T1 = T[N] (2)
T2 = T[T[N]] (0)
T3 = T[T[T[N]]] (3)
T4 = T[T[T[T[N]]]] (2)

ダブリング

  • 累乗したやつは同じになるやろ!という話。ほんとか?

T%5F1%5Bk%5D+%3D+T%5Bk%5D+

T%5F2%5Bk%5D+%3D+T%5F1%5BT%5F1%5Bk%5D%5D+

T%5F4%5Bk%5D+%3D+T%5F2%5BT%5F1%5Bk%5D%5D+

T%5F8%5Bk%5D+%3D+T%5F4%5BT%5F4%5Bk%5D%5D+

      • Rubyでやってみる
T = [3, 1, 0, 2, 4]

def doubling(array, n)
    src = array.dup
    dst = (0...array.length).to_a
    
    0.upto(n) do
        for e in dst.dup
            dst[src[e]] = e
        end
    end
    dst
end

T1 = doubling(T,1)
T2 = doubling(T,2)
T4 = doubling(T2,1)
お名前: コメント: