排队问题

queue_problem.rb

# == Question:
# 12 people stand in two rows, 6 per row. People in each row must be
# arranged by their height and person in the second row must be taller 
# than the one up front. Well, how many kinds of arrangement can be?
#
# == Solution:
# Suppose that person1 to person12 are marked by their height ascent
# We find the following rules:
# 1. Person at the first position of row 1 must be person1
# 2. Person at the second positon of row 1 must be in person2...person3, and person
#    at the third postion of row 1 must be in person3...person5, so that person at
#    position i of row 1 must be in personi...person(2 * i - 1)
# 3. Provided that the arrangement of row 1 is complete, there are only one arrangement
#    kind for row 2, for the remaining 6 people must be arranged by their height ascent
#
# So we can simply use backtracking method to solve this problem
#
#
#

def build_matrix(n)
  matrix = []
  i = 1
  while i <= n/2
    list = (i..(2 * i - 1)).to_a
    matrix << list
    i += 1
  end
  matrix
end

def trackback(counter, list, l, matrix, max)
  if (l == matrix.size)
    counter[0] += 1
  else
    matrix[l].each do |item|
      list[l] = item
      if list[l] > max
        trackback(counter, list , l + 1, matrix, list[l])
      end
    end
  end
end

def count(n)
  matrix = build_matrix(n)
  counter = [0]
  list = []
  trackback(counter, list, 0, matrix, 0)
  counter[0]
end

if __FILE__ == $0
  n = 12
  puts "count -> #{count(n)}"
end