The script takes a string such as this: (15, 176) (65, 97) (72, 43) (102, 6) (191, 189) (90, 163) (44, 168) (39, 47) (123, 37) and breaks it into an array of arrays. It then computes the largest possible number of choices, with the guideline that each selected array has to have both numbers smaller than the previous selection. For the above string, the right output would be 4.people = File.read(ARGV[0])people = people.sub(\(, '').sub(/\)$/, '').split(\) \()people.map! { |p| p.split(', ') }count = 0test = people.permutation.to_atest.each do |perm|  test_count = 0  perm.each_with_index do |item, i|    test_case = perm[i+1]    unless test_case == nil     test_count += 1 if item[0] > test_case[0] && item[1] > test_case[1]    end  count = [count, test_count].max  endendp countAnyways, it works but is sloooow, especially with longer strings. How can I speed this up? I know the nested loops can be problematic and as the string grows the number of permutations grows. Any advice would be much appreciated. Edit: I am running this on Ruby 1.8.7.Edit: New attempt at the problem/script:people = '(15, 176) (65, 97) (72, 43) (102, 6) (191, 189) (90, 163) (44, 168) (39, 47) (123, 37)'#people = File.read(ARGV[0]).chomppeople = people.sub(\(, '').sub(/\)$/, '').split(\) \()people.map! { |p| p.split(', ').map {|a| a.to_i } }ht = people.sort_by { |h| h[0] }wt = people.sort_by { |w| w[1] }a_i = []ht.each do |item|  a_i << wt.index(item)enddef subgen( array, count=1, t=(array.length+1) )  if array.length == 1    return count  end  without = subgen(array[0..-2], count, t)  if array[0] > array[-1] || array[-1] > t    return without  else    with = subgen(array[0..-2], count+=1, t = array[-1])    return [with, without].max  endendcurrent = 0a_i.each_with_index do |item, j|  test = a_i[j..-1]  current = [current, subgen(test)].maxendp currentThis has been thoroughly tested and works, but there has to be a way to make it faster. Any ideas?
This script works but keeps timing out with longer inputs. How can I improve its speed? [Ruby]
optimization;ruby