5
\$\begingroup\$

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 << wt.index(item)
end

def 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
  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?

\$\endgroup\$
3
  • \$\begingroup\$ On my machine, the first code takes 10.776s while the second one takes 0.005s. That's 2000x faster ! \$\endgroup\$ – barjak Dec 18 '11 at 22:01
  • \$\begingroup\$ @barjak It is incredibly faster! but I think it can still be made faster. For long lists subgen gets called a lot and I wonder if there is a way to reduce that some how. I've been reading about memoization but I can't figure out how to apply it to my new script. \$\endgroup\$ – Sean Lerner Dec 19 '11 at 3:31
  • \$\begingroup\$ I realized that your problem seems to be somewhat similar to the longest common subsequence problem. \$\endgroup\$ – barjak Feb 17 '12 at 10:49
5
\$\begingroup\$

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 !

\$\endgroup\$
0
1
\$\begingroup\$

The code below follows the known rule: use the simplest possible algorithm, unless some code-probing bottleneck analysis (with your particular data) proves it insufficiently fast.

So, it basically uses the algorithm you first gave, plus @barjak's indices, and his insights both into what you are doing, and into the fact that combinations are as good as permutations, after they are both sorted. Also:

  • Since finding the largest is the goal, it starts with the largest and works smaller so it can stop as soon as it finds the first one.
  • It converts the numbers so it can work with the faster binary instead of strings.
  • It doesn't convert the huge enumerable (of combinations or even permutations) into an array, which stores everything in memory and could cause a paging slowdown, but individually checks its entries.
  • Using Ruby library methods when possible (mostly written in C), rather than our own Ruby code, speeds up execution.

The Ruby library 'makes no guarantees about the order in which the combinations are yielded', so at first I didn't trust it to keep the order of the indices when giving combinations of them, but I put in such a further algorithmic optimization to avoid sorting by height for every combination.

Also, I bail out as soon as I find the weights out of order, rather than sort the entire combination's worth. But still it will be O(n!) because, almost n times, it checks almost n!/(n-k)!k! combinations, each of length k. And, it still takes a long time: 16 seconds at just 22 pairs (with my setup). 19 pairs takes 2 seconds.

I found your description, 'the largest possible number of choices with the guidelines that each selected array has to have both numbers smaller than the previous selection' somewhat hard to interpret. So, I read your code instead, and came up with:

Problem: drawing from a set of integer 2-tuples, find the length of the longest subset which can strictly increase in both variables.

For your test data, I got 4 also.

def print_time
  p Time.new.sec
end

def increasing?(array, indices)
  f = array.at indices.first
  skip_first = 1
# Compare adjacent pairs.
  (skip_first...indices.length).reduce(f) do |memo,i|
    each = array.at indices.at i
    return false unless memo < each # Bail out quickly.
    each # Slide the pair.
  end
  true
end

def search
# Get filename.
  ##fn = ARGV.at 0

# Read string containing parenthesized pairs of numbers.
  ##paren = File.read fn
# Or, use test string.
  ##paren = '(15, 176) (65, 97) (72, 43) (102, 6) (191, 189) (90, 163) (44, 168) (39, 47) (123, 37)'
# Or, generate repeatable random numbers.
  srand 0
  n, max = 22, 100000
  paren=(0...n).map{(0..1).map{rand max}}.map{|a,b| "(#{a}, #{b})"}.join ' '
  print_time

# Translate to array syntax.
# Add commas.
  commas = paren.gsub ') (', '),('

# Convert parentheses to brackets.
  brack = commas.tr '()', '[]'
  s = "[ #{brack} ]"

# Convert into pairs of numbers in binary.
  people = eval s

# Pre-sort people by height then weight, which may speed sorting the combinations.
  people = people.sort

# Remove duplicates, which could reduce the length considerably, depending on the data.
  people = people.uniq

# Get single numbers in binary.
  ht = people.map{|e| e.first} # Height.
  wt = people.map{|e| e.last } # Weight.

# Set up indices.
  pl = people.length
  p "N after removing duplicates is #{pl}."
  indices = (0...pl).to_a

  result = 0 # Preserve the result after the block.

# Start from the largest size of subset and go downward.
  decreasing_sizes = (1..pl).to_a.reverse
  decreasing_sizes.each do |size|

# Use combinations instead of permutations.
# Don't produce a big array of combinations, because
# it could be causing slow virtual-memory paging.
# Instead, check each combination when it is supplied.

    indices.combination(size).each do |comb|

# Each combination is sorted already in increasing order by height.
      ## comb = comb.sort{|i,k| (ht.at i) <=> (ht.at k)}

# Check whether the weights are also in increasing order.
      next unless increasing? wt, comb
      w = wt.values_at *comb # Double check.
      next unless w.sort==w

# We have found our first subset, which is increasing in both
# height and weight.
# Therefore, its size is the largest good subset size.
# Report this size and stop.
      result = [size, comb.map{|i| people.at i}]
      throw :result, result
    end
  end
end

length, pairs = catch(:result){ search}
p "One of the longest subsets has length #{length}: #{pairs.inspect}, length #{length}."
print_time
\$\endgroup\$
0
\$\begingroup\$

Best for this is an algorithm similar to Patience sorting. I wrote some Ruby code that processes tens of thousands of pairs in something like a few seconds. You're welcome to write me if you're still interested.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.