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
