【Ruby】【アルゴリズム】文字列の回転。メモリ富豪Ver、メモリ貧乏Ver、再帰Ver、お手玉Ver、回転の回転Ver、

　
■post summary
study about algorithm.the question is "rotation the string".
ex) method("abcdef", 3) -> "defabc"
　

問題

文字列の回転を考えます。
method("abcdef", 3) -> "defabc"

メモリ富豪

一行で書けます。

def brock_reverse_no1(str, n)
  (str[0,n], str[n, str.length-n] = str[n, str.length-n], str[0,n]).join("")
end
p brock_reverse_no1("abcdef",3)

メモリ貧乏

一つずつ要素を入れ替えていくのは、バブルソートの実装をヒントに。

def brock_reverse_no2(str, n)
  n.times do |i|
    (str.length - 1).times do |j|
      str[j], str[j+1] = str[j+1], str[j]
    end
  end
  str
end
p brock_reverse_no2("abcdef",3)

再帰

文字列を、回転する要素aとそれ以外b のabに分ける。
a＜bの場合、b= b1 + b2 と分ける（b2の長さ = aの長さ）
このとき文字列は a b1 b2　と表現できる。そして、aとb2 を入れ替える。
そうすると、aは正しい場所に来ているので、残りのb2 b1 を同様に入れ替えていく。

考え方は、クイックソート（pivotを使ったソート）を参考に。

def change_same_size_block(start_index, end_index, pivot, str)
  left_block_size = pivot - start_index + 1
  right_block_size = end_index - pivot
  ok = (left_block_size == right_block_size)
  target_size = [left_block_size, right_block_size].min
  str[start_index, target_size], str[-target_size, target_size] = str[-target_size, target_size], str[start_index, target_size]
  return str if ok
  if left_block_size == target_size
    return change_same_size_block(start_index, end_index-target_size, pivot, str) 
  else
    return change_same_size_block(start_index+target_size, end_index, pivot, str) 
  end
end
def brock_reverse_no4(str, n)
  change_same_size_block(0, str.length-1, n-1, str)
end
p brock_reverse_no4("abcdefgh", 6)

お手玉

メモリ貧乏Verだと計算量が n*文字列長になってしまう。
隣り合う要素で入れ替えるのではなく、「最終的に正しい場所の要素と交換」することで
メモリ消費を抑え、計算量も文字列長だけになる。

この実装がややこしかったよ。

def brock_reverse_no5(str, quantity)
  change_ch(0, quantity, str)
end
def change_ch(start_index, quantity, str)
  count_change = (str.length - start_index - 1) / quantity
  count_change.times do |i|
    str[start_index + quantity*i], str[start_index + quantity*i + quantity] = str[start_index + quantity*i + quantity], str[start_index + quantity*i]
  end
  last_changed = start_index + quantity*count_change
  next_state = (last_changed + quantity) % str.length
  return str if next_state == 0
  str[last_changed], str[next_state] = str[next_state], str[last_changed]
  return change_ch(next_state, quantity, str)
end
p brock_reverse_no5("0123456789", 3)

回転の回転

一番スマートな方法。
左の要素をさかさまにして、右の要素をさかさまにして、最後に全体をさかさまにすると、求める文字列！！

class String
  def _reverse(i, j)
    loop do
      break if i >= j
      self[i], self[j] = self[j], self[i]
      i += 1 ; j -= 1
    end
    self
  end
end
def brock_reverse_no3(str, n)
  str._reverse(0, n-1)._reverse(n, str.length-1)._reverse(0, str.length-1)
end
p brock_reverse_no3("abcdef",3)