This script works but keeps timing out with longer inputs. How can I improve its speed? [Ruby]

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 = 0
test = people.permutation.to_a
test.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
  end
end

p count

Anyways, 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]).chomp
people = 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  array[-1] || array[-1] > t
    return without
  else
    with = subgen(array[0..-2], count+=1, t = array[-1])
    return [with, without].max
  end
end

current = 0
a_i.each_with_index do |item, j|
  test = a_i[j..-1]
  current = [current, subgen(test)].max
end

p current

This has been thoroughly tested and works, but there has to be a way to make it faster. Any ideas?

So, you are generating every possible permutations of the array, which is a O(n!) operation. This is huge.

I think this can be done with an O(n²) algorithm. I would do :

• create an array containing the pairs, ordered by the first value

• create another one containing the pairs, ordered by the second value

• create a third array containing, for each index of the first array, the index in the second array where we can find the corresponding value.

• find every subset of this third array whose values are in ascending order.

The result is the length of the biggest subset.

Example

first array | second array | third array
------------+--------------+------------
15,176      | 102,6        | 7
39,47       | 123,37       | 3
44,168      | 72,43        | 6
65,97       | 39,47        | 4
72,43       | 65,97        | 2
90,163      | 90,163       | 5
102,6       | 44,168       | 0
123,37      | 15,176       | 1
191,189     | 191,189      | 8

The ascending subsets are :

• 7 8

• 3 6 8

• 3 4 5 8

• 6 8

• 4 5 8

• 2 5 8

• 5 8

• 0 1 8

• 1 8

• 8

The biggest subset is (3 4 5 8), and its size is 4.

Complexity

The sorts can be done with O(n log n)
The creation of the third array is O(n²)
To find the subset, I think we can do that with O(n²) (I'm not sure about that)

So, the whole thing should be O(n²).

The algorithm for finding the ascending subsets is not trivial. I'm sure it will be fun to implement !

StackExchange Code Review Q#6861, answer score: 5