Skip to content

Instantly share code, notes, and snippets.

@shaobin0604
Created October 26, 2009 16:04
Show Gist options
  • Save shaobin0604/218756 to your computer and use it in GitHub Desktop.
Save shaobin0604/218756 to your computer and use it in GitHub Desktop.
排队问题
# == 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment