Ruby实现的最短编辑距离计算方法

利用动态规划算法，实现最短编辑距离的计算。

#encoding: utf-8

#author: xu jin

#date: Nov 12, 2012

#EditDistance

#to find the minimum cost by using EditDistance algorithm

#example output:

#  "Please input a string: "

#  exponential

#  "Please input the other string: "

#  polynomial

#  "The expected cost is 6"

#  The result is : 

#    ["e", "x", "p", "o", "n", "e", "n", "-", "t", "i", "a", "l"]

#    ["-", "-", "p", "o", "l", "y", "n", "o", "m", "i", "a", "l"]

p "Please input a string: "

x = gets.chop.chars.map{|c| c}

p "Please input the other string: "

y = gets.chop.chars.map{|c| c}

x.unshift(" ")

y.unshift(" ")

e = Array.new(x.size){Array.new(y.size)}

flag = Array.new(x.size){Array.new(y.size)}

DEL, INS, CHA, FIT = (1..4).to_a  #deleat, insert, change, and fit

 

def edit_distance(x, y, e, flag)

  (0..x.length - 1).each{|i| e[i][0] = i}

  (0..y.length - 1).each{|j| e[0][j] = j}

  diff = Array.new(x.size){Array.new(y.size)}

  for i in(1..x.length - 1) do

    for j in(1..y.length - 1) do

      diff[i][j] = (x[i] == y[j])? 0: 1

      e[i][j] = [e[i-1][j] + 1, e[i][j - 1] + 1, e[i-1][j - 1] + diff[i][j]].min 

      if e[i][j] == e[i-1][j] + 1

        flag[i][j] = DEL 

      elsif e[i][j] == e[i-1][j - 1] + 1

        flag[i][j] = CHA

      elsif e[i][j] == e[i][j - 1] + 1

        flag[i][j] = INS       

      else flag[i][j] = FIT

      end     

    end

  end  

end
out_x, out_y = [], []
def solution_structure(x, y, flag, i, j, out_x, out_y)

  case flag[i][j]

  when FIT

    out_x.unshift(x[i])

    out_y.unshift(y[j])  

    solution_structure(x, y, flag, i - 1, j - 1, out_x, out_y)

  when DEL

    out_x.unshift(x[i])

    out_y.unshift('-')

    solution_structure(x, y, flag, i - 1, j, out_x, out_y)

  when INS

    out_x.unshift('-')

    out_y.unshift(y[j])

    solution_structure(x, y, flag, i, j - 1, out_x, out_y)

  when CHA

    out_x.unshift(x[i])

    out_y.unshift(y[j])

    solution_structure(x, y, flag, i - 1, j - 1, out_x, out_y)

  end

  #if flag[i][j] == nil ,go here

  return if i == 0 && j == 0    

  if j == 0

      out_y.unshift('-')

      out_x.unshift(x[i])

      solution_structure(x, y, flag, i - 1, j, out_x, out_y)

  elsif i == 0

      out_x.unshift('-')

      out_y.unshift(y[j])

      solution_structure(x, y, flag, i, j - 1, out_x, out_y)

  end

end
edit_distance(x, y, e, flag)

p "The expected edit distance is #{e[x.length - 1][y.length - 1]}"

solution_structure(x, y, flag, x.length - 1, y.length - 1, out_x, out_y)

puts "The result is : n  #{out_x}n  #{out_y}"

Ruby实现的3种快速排序算法
刚学Ruby，正巧算法老师鼓励用不熟悉的语言来写算法，我就用Ruby吧~~话说Ruby可真是超厉害，好多凭直觉的方法都可以用。。。。。无限膜拜中。。。。

Ruby一行代码实现的快速排序
defquick_sort(a)returnaifa.size2(x=a.pop)quick_sort(a.select{|i|i=x})+[x]+quick_sort(a.select{|i|ix}):[]endarray=[72,6,57,88,60,42,83,73,42,48,85]pquick_sort(array)#=[6,42,42,48,57,60,72,73,83,85,88]

Ruby实现的最长公共子序列算法
最长公共子序列，LCS，动态规划实现。#encoding:utf-8#author:xujin,4100213#date:Nov01,2012#Longest-Commom-Subsequence#tofindalongestcommomsubsequenceoftwogivencharacterarraysbyusingLCSalg