# Subset Counter
#
# Finds how many subsets within a set satisfy the condition
#
# "The first n-1 elements sum to the nth element"
#
# Does so by:
#
# 1. Reading in set s.
# 2. Generating all subsets of set s. (writes them out at this point)
# 3. Iterating over all subsets, storing results. (writes found sets to file)
# 4. Displays number of matching subsets found.
#
# The means of generating all subsets is:
#
# Count from 0 to 2^size of set s, and use the bits of each number to
# determine set population.
#
# For example,"001000110" would include 3 elements of a set with 9 members.
# The next umber would be "001000111" and would include a set of 4 elements,
# the successive set. All of these are saved for ease of recalculation in the
# chance that something goes wrong during the counting step.
#
#
# Written because the people at Greplin put a programming problem up on their
# website, by Wyatt Carss, on Sunday October 10th, 2010. (10/10/10 woo)
#
# If you have any questions or comments (particularly, a better algorithm that
# doesn't require 2^sizeof(s) * sizeof(s) steps would be pretty cool), send me
# an email at carss.w@gmail.com
#
# Thanks for reading!
#
# Control for real or test data - set using equal to 'r' or 't' accordingly
r = "real"
t = "test"
using = t # using test data
# Reads integers from a file of the format "1, 2, 3, 4, 5"
#
def get_whole_set_from(filename)
f = File.open(filename)
g = f.gets
f.close
g[g.size-1] = ""
elements = g.split(',').map {|e| e.to_i }
elements.sort! # no guarantee they came in sorted
end
# Utility function which accompanies 'to_binary'
#
def convert_small_binary(num)
if num.class == Fixnum then
if num < 0 or num > 1 then
"error"
else
num.to_s
end
end
end
# Converts a given number to binary.
#
def to_binary(num)
str = ""
if num < 2 then
convert_small_binary(num)
else
str += to_binary(num/2).to_s
str += convert_small_binary(num - (num/2 * 2))
end
end
# Pads a number to a specific length by stuffing leading 0's
#
# somewhat obviously, returns the number as a string.
#
def pad(num, length, debug="off")
while num.to_s.length < length do
num = "0" + num.to_s
end
if debug == "show debug" then
print "Padded num is #{num}"
end
num
end
# Returns bit i of a num of length length
#
def get_bit(i, num, length=num.to_s.size)
# This value is padded out to a given size by supplying leading zeroes.
bit_value = pad(to_binary(num), length)[i].to_i - 0x30
# What the heck is going on there?
#
# A given number is converted to binary in "to_binary(num)", and it is
# padded out to a specified length by "pad(num, length)", which returns
# a string-representation of the number.
#
# We then index position i of that string, and subtract hex-30, yielding
# the literal value 1 or 0 for that number.
#
# Note that 'bit i' is i spots into a bitstring of the /length specified/.
#
#puts ", and a is #{bit_value}"
bit_value
end
# Given a sorted array of integers representing a set, calculates
# all 2^elements.size subsets for it.
#
def generate_subsets_out_of(elements, debug=off)
subsetlist = []
sizeoflist = 2**elements.size
for num in 0 .. sizeoflist-1 do
subset = []
elements.each_index do |i|
if get_bit(i, num, elements.size) == 1 then
subset << elements[i]
end
end
subsetlist << subset
if debug == "show debug" && ((num % 10000) == 0) then
printf("number %d - %.2f%s finished.\n", num, (num/(sizeoflist - 1.0))*100, "%")
end
end
subsetlist
end
# Given an array of sets of sorted, ascending ints, calculates
# how many of those sets satisfy the condition:
#
# "The first n-1 elements sum to the nth element"
#
# Then returns an array of all matching sets.
#
def count_sets_in(subsetlist, debug="off")
count = 0
list_tracker = 0
found_list = []
sizeoflist = subsetlist.size
subsetlist.each do |subset|
sum = 0
subset.each_with_index do |e, i|
if i == subset.size-1 then
if sum == e then
count += 1
if debug == "show debug" then
puts "Subset #{list_tracker} is in. - #{(list_tracker/(sizeoflist - 1.0 + 1.0)) * 100}% finished."
end
found_list << subset
end
else
sum += e
end
end
list_tracker += 1
end
found_list
end
# Writes an array of arrays of numbers to a file.
#
# ex. [[1, 2, 3, 5], [1], [2, 5], [3, 6]]
#
# file 'output':
#
# 1 2 3 5
# 1
# 2 5
# 3 6
#
def write_out(list_of_numbers, outputfile="output")
f = File.open(outputfile, "w")
list_of_numbers.each do |list|
list.each do |element|
f.print "#{element}, "
end
f.print "\n"
end
f.close()
end
# Filenames for this run (see line 10 for definition of using)
filename = using + "_subs"
outfile = using + "_big"
resultsfile = using + "_results"
# Generate a list of all subsets for a given (sorted, ascending) set, then
# find all subsets for which the first n-l elements sum to the nth element.
whole_set = get_whole_set_from filename
all_subsets = generate_subsets_out_of whole_set, "show debug"
write_out all_subsets, outfile
found_list = count_sets_in all_subsets, "show debug"
write_out found_list, resultsfile
puts "I found #{found_list.size} subsets!"