swap_way.rb

# coding: utf-8

# swap([0,1,2], 0, 2)
# => [2, 1, 0]
def swap(v, n, m)
  v2 = v.dup
  v2[m] = v[n]
  v2[n] = v[m]
  v2
end

# swap_way_generator([3,1,0,2])
# => [[0, 2], [0, 3]]
def swap_way_generator(target,i=0)
  i >= target.length ? [] :
    target[i] == i ? swap_way_generator(target,i+1) :
      swap_way_generator(swap(target,i,target[i]),i) + [[i,target[i]]]
end

# apply_swap_way([0,1,2,3],[[0, 2], [0, 3]])
def apply_swap_way(init,swap_way)
  swap_way.reduce(init){|acc,(n,m)| swap(acc,n,m)}
end



# 解説

# swap関数だけを使って[0,1,2,3]を[3,1,0,2]にするには
# どのような順序でswapすれば良いかを考える関数を考えます。

# まずは配列の要素２つを入れ替えるswap関数を作りましょう。
# 出来たようです。
# swap([0,1,2], 0, 2)
# 実行すると [2, 1, 0] が返ってきます。
# 0番目の要素と2番目の要素が入れ替わっていますね。

# 次にメインとなる、swapの順序を考える関数swap_way_generatorを作ります。
# 出来たようです。
# swap_way_generator([3,1,0,2])
# 実行すると [[0, 2], [0, 3]] が返ってきます。
# これはまず0番目と2番目、次に0番目と3番目をswapしろ、そうすれば
# [0,1,2,3]は[3,1,0,2]になる。と言っています。本当でしょうか？

# 検証してみましょう。先の関数が返した結果に従って、配列をswapする
# apply_swap_way関数を作ります。
# 出来たようです。
# apply_swap_way([0,1,2,3], [[0, 2], [0, 3]])
# 実行すると[3,1,0,2]が返ってきます。
# swap関数だけで目的の配列にすることが出来ました。やったー！