#!/usr/bin/env ruby
# encoding: UTF-8
# Solution to Project Euler problem 106
# Author: David J. Oftedal.
# Find the number of pairs of subsets that have to be checked according to rule i. in the problem in order to
# determine if a set is a special sum set.
# Pick all combinations of n elements from the array.
class SelectN
include Enumerable
def initialize(array, n, required)
@array = array
@n = n
@required = required
end
def each
if @n <= 0
yield []
else
@array.each do |element|
next if @required != nil && @required != element
array = @array.dup
array.delete_if{|n| n < element} if @required == nil
array.delete(element)
array.select_n(@n-1, nil).each {|combination| combination << element; yield combination}
end
end
end
end
class Array
def select_n(n, required=nil) return SelectN.new(self, n, required) end
def subsets
sets = []
(1...length).each do |len|
self.select_n(len).each {|set| sets << set}
end
return sets
end
def subsetpairs
pairs = []
sets = self.subsets
sets.each do |set1|
set1 = set1.sort
sets.each do |set2|
set2 = set2.sort
next if set2 == set1 || [set1, set2] != [set1, set2].sort
next if set2.select{|n| set1.index(n) != nil}.count != 0
pairs << [set1, set2]
end
end
return pairs
end
# Assume the following:
# 1) Only pairs of the same length need to be checked, as other pairs are eliminated by rule ii.
# 2) Pairs where, when sorted, every element of one is less than or equal to every element in the other,
# do not need to be checked.
def need_checking?
set1 = self[0].sort
set2 = self[1].sort
return false if set1.length != set2.length
set1, set2 = [set1, set2].min, [set1, set2].max
set1.each_index {|i| return true if set1[i] > set2[i]}
return false
end
end
count1 = 0
count2 = 0
(1..12).to_a.subsetpairs.each do |subset|
count2 +=1 if subset.need_checking?
count1 +=1
end
puts "Number of non-overlapping subset pairs of sets of length 12: " << count1.to_s << "."
puts "Number of pairs that had to be checked for equality: " << count2.to_s << "."