TAOCP 7.2.1.1

gistfile1.rb

def function_f(tuple, m)
  c = [-1, -1, 0]
  if tuple.all? {|digit| digit == 0}
    return c[0].abs
  elsif tuple[0] == 1 and tuple[1..-1].all? {|digit| digit == 0}
    return 0
  else
    sum = 0
    tuple.each_index{|i| sum += c[i] * tuple[i] }
    return sum % m
  end
end

def algorithm_s(m, n) #基数 桁数
  # S1 init
  a = Array.new(m**n)

  for j in ((1-n)..0)
      a[j] = 0
  end
  p a
  # a => [0,nil,...,nil,0,..,0]
  k = 1

  # S2 Visit
  while(1) do
    visit =  k-n < 0 && k-1 < 0 ? a[k-n..k-1] :
             k-n < 0 && k-1 >= 0 ? a[k-n..-1] + a[0..k-1] :
             a[k-n..k-1]
    puts 'visit: ' + visit.join()

    break if k == m**n

    # S3
    a[k] = function_f(visit, m)
    k = k + 1
  end
end