Here is my solution. Its not the most beautiful thing in the world, but
its effective.
···
-----------------------------------------
def weirdo_exhaustive(from, max)
puts "none found" and return 0 if max < 70
(from..max).each do |num|
if num % 2 == 0
list, sum= [], 0
(1...num).each do |div|
list << div and sum += div if num % div == 0
end
puts "==" + num.to_s if sum > num and has_sum(num, list) == false
end
end
end
def has_sum(num, array)
if array.is_a? Integer then return false end
sum = 0
array.each do |val| sum += val end
if sum === num then return true end #this next line saves a BUNCH of checks.
if sum < num then return false end
array.each do |removeme|
copy = array.dup
copy.delete(removeme)
if copy.size > 1 and has_sum(num, copy) == true then return true
end
end
return false
end
----------------------------------------
It took a good number of optimizations that make it less pretty, but
much faster. The first time I ran it it took 4 hours to reach 1,000.
Its faster than that now, but its still somewhere around O(3^n).
SO... I thought of a way to speed up the algorithm a lot! So, with a
*few* more optimizations, here's the weirdo_fast algorithm.
def weirdo_fast(max)
list = [ 70,836,4030,5830,7192,7912,9272,10792,17272,45356,73616, #
83312,91388,113072,243892,254012,338572,343876,388076, #
519712,539744,555616,682592,786208,1188256,1229152,1713592, #
1901728,2081824,2189024,3963968 ]
list.each do |num|
puts num if num <= max
end
if max > list[list.size-1] then weirdo_exhaustive(list[list.size-1],
max) end
end
A little faster, eh? It will start exhaustively searching if your max
is out of its range.... but I warn you, my computer has been
calculating 3963970 for the last 24 hours. And, not the range up to it,
just that number. Remember, its 3^3963970 = 62_286_091_158_062_773_000
which takes a minute to calculate. Well, with my other optimizations,
its a tad faster than that.... a tad.
I'm interested to see if anyone else found a much better way to test
for has_sum(num, array). It seems to me like there must be a clever
mathematical trick for getting the job done. Or perhaps the only clever
way is my "fast" algorithm. But, that's not even that clever.
Here is my solution. Its not the most beautiful thing in the world, but
its effective.
--
Simon Strandgaard
# Weird Numbers
# Simon Strandgaard <neoneye@gmail.com>
def divisors(value)
ary =
(value/2).times do |i|
div = i + 1
ary << div if value % div == 0
end
ary
end
$bits =
32.times do |bit|
$bits << 2 ** bit
end
def has_subset_equal_to(divs, value)
pairs = divs.zip($bits)
1.upto(2 ** divs.size - 1) do |i|
sum = 0
pairs.each{|div,b| sum+=div if (i&b)>0 }
return true if sum == value
end
false
end
def find_weird_numbers(range_min, range_max)
ary =
range_min.upto(range_max) do |value|
divs = divisors(value)
sum = divs.inject(0){|a,b|a+b}
ary << [value, divs] if sum > value
end
res =
ary.each do |value, divs|
if !has_subset_equal_to(divs, value)
puts "##{value} is a WEIRD NUMBER"
res << value
else
puts "##{value} is nothing"
end
end
p res
end
def weirdo_fast(max)
list = [ 70,836,4030,5830,7192,7912,9272,10792,17272,45356,73616, #
83312,91388,113072,243892,254012,338572,343876,388076, #
519712,539744,555616,682592,786208,1188256,1229152,1713592, #
1901728,2081824,2189024,3963968 ]
list.each do |num|
puts num if num <= max
end
if max > list[list.size-1] then weirdo_exhaustive(list[list.size-1],
max) end
end
The Quiz was real fun and I spent quite a lot of time on it. Below
source is rather easy, but believe me I tried lots of different ways
(such as dynamic binary knapsacks etc.), most of them suck because they
need to many method calls.
The code takes about 30 seconds to find all Weird Numbers up to 10_000:
70, 836, 4030, 5830, 7192, 7912, 9272.
The code doesn't scale rather well, the caches would need to be
optimized for that.
=end
class Integer
# 70, 836, 4030, 5830, 7192, 7912, 9272, 10430
def weird?
!has_semiperfect? && !weird2?
end
SEMIPERFECT = {nil => 'shortcut'}
def weird2?(divisors=proper_divisors)
return true if divisors.any? { |x| SEMIPERFECT[x] }
if brute(self, divisors)
SEMIPERFECT[self] = true
else
false
end
end
Here is my solution (it's optimized for statistics not for speed).
I don't use things like someone tried all odd numbers up to 10**18
because doesn't change the algorithm.. I'll use that in my speed
optimized version..
class Integer
$prime_factors = Hash.new # we cache prime factors...
def prime_factors position = -1
if cached = $prime_factors[self] # cached?
return cached # yes
end
if self == 1 # we have 1 we are done
return $prime_factors[self]=[] # return no factors
elsif position<0 # we havn't reached factor 5 yet
if self&1 == 0 # test factor 2
return $prime_factors[self]=[2,*(self>>1).prime_factors]
elsif self%3 == 0 # and factor 3
return $prime_factors[self]=[3,*(self/3).prime_factors]
end
end
loop do
position+=6 # increment position by 6
if position*position > self # we have a prime number return it
return $prime_factors[self]=[self]
elsif (quo,rem = divmod(position)) and rem.zero? # test 6n-1
return $prime_factors[self]=[position,*quo.prime_factors(position-6)]
elsif (quo,rem = divmod(position+2)) and rem.zero? # and 6n+1
return $prime_factors[self]=[position+2,*quo.prime_factors(position-6)]
end
end
end
def distinct_prime_factors # rle encode the prime factors
distinct_prime_fac = Hash.new{0} # setup the hash
prime_factors.each do |prime_factor| # fill it
distinct_prime_fac[prime_factor]+=1
end
distinct_prime_fac.to_a.sort_by{|(fac,count)|fac} # and return it as sorted array
end
def divisors # get the divisors (not needed for divisor sum)
divs = [] # store divisors here
n = 1 # start with 1
loop do
break if n*n > self # done
if (qua,rem = divmod(n)) and rem.zero? # test for division
divs << qua # add divisors
divs << n
end
n+=1
end
divs.uniq.sort[0..-2] # we don't want self
end
def semi_perfect? deficient=false # final test
cached_abundance = abundance
return deficient if cached_abundance < 0 # deficient return the argument
return true if cached_abundance == 0 # perfect => semi perfect too
possible_values = {0=>true} # store all possible values in a hash
divs = self.divisors # get the divisors
div_sum_left = divs.inject(0){|a,b|a+b} # get the divisor sum
pos_2 = div_sum_left - self # this is a possibility too
divs.reverse.each do |div| # for each divisor
possible_values.keys.each do |value| # and each possible value
if value+div_sum_left < self # check wether it can reach the number with the divisors left
possible_values.delete(value) # if not delete the number (huge speedup)
end
new_value = value+div # we create a new possible value including the divisor
if new_value == self or new_value == pos_2 # if it is the number it's semi perfect
return true
elsif new_value < self # if it's less than the number it could be semi perfect
possible_values[new_value]=true # add it to the possiblities
end # if it's more than the value we can ignore it
end
div_sum_left-=div # the current divisor isn't left anymore
end
false # we found no way to compose the number using the divisors
end
def restricted_divisor_sum # uses the formular from wikipedia
distinct_prime_factors.map do |(fac,count)|
comm_sum = 1
comm_mul = 1
count.times do
comm_sum += (comm_mul*=fac)
end
comm_sum
end.inject(1){|a,b|a*b}-self
end
def perfect? # perfect numbers have the form 2**(n-1)*(2**n-1) where n is prime (and small )
return false if self&1 == 1 # it isn't known weather there are odd perfect numbers.. but it's irrelevant for my algorithm
doubled = self * 2 # the perfect number is a triangular number of the form (n*(n+1))/2
doubled_root = Math.sqrt(doubled).floor # if we double it and take the floored square root we get n
return false unless doubled == doubled_root*(doubled_root+1) # if we don't get n it isn't perfect
doubled_root_string = (doubled_root+1).to_s(2) # from the first line we know n+1 has to be of the form 2**n
return false unless doubled_root_string.count('1')==1 # we check that here
return false unless (doubled_root_string.size-1).prime_factors.size == 1 # and n ha to be a prime
return false unless self.abundance == 0 # if it passes all the earlier test we check it using the abundance
true # and if it passes it's perfect
end
def abundance
self.restricted_divisor_sum-self
end
end
require 'benchmark'
max_num = Integer(ARGV.shift||'1000') rescue 1000 # read a number from the command line
new_semi_perfects = [] # store semi perfect numbers that can't be constructed using other semi perfect numbers
STDOUT.sync = true
puts "Weird Numbers Up To #{max_num}:"
if test_num == next_record #stat
recorded_times << [Benchmark.times,Time.now] #stat
next_record = record_nums_left.shift #stat
end #stat
if test_num.perfect? # it's perfect
new_semi_perfects << test_num
perfect_count += 1 #stat
next
end
do_next = false
new_semi_perfects.each do |semi_per|
if test_num % semi_per == 0 # is it possible to compose the current number using a semi-perfect number?
do_next = true # yes
composed_semi_perfect_count += 1 #stat
break
end
end
next if do_next
# no
case test_num.semi_perfect? nil # we don't care about deficient numbers
when true # but we care about semi perfects
new_semi_perfects << test_num
new_semi_perfect_count += 1 #stat
when false # and even more about abundand non semi perfects
puts test_num
weird_count += 1 #stat
else #stat
deficient_count += 1 #stat
end
def plot(plot_data,max,step)
22.downto(0) do |k|
res = ""
res = form_float(max) if k == 22
while res.size != plot_data.size
val = plot_data[res.size]
lower_range = k*step
res << ( val >= lower_range ? (val < lower_range+step ? '#' : ':') : ' ' )
end
puts res
end
end
I've got an optimization I haven't seen anyone else use yet. My
solution is roughly 20% faster than Ryan's.
The trick is that any number of the form k*(2^m)*p where m > 1 and p
is a prime such that 2 < p < 2^(m+1) is semiperfect (according to
wikipedia). This rules out many numbers, and its cheaper than a
thorough search of subsets.
#!/usr/bin/ruby
def weird(max)
primes = sieve(max*2)
70.step(max,2){|n|
puts n if weird?(n,primes)
}
end
def weird?(n,primes)
divs = divisors(n)
abund = divs.inject(0){|a,b| a+b} - n
return false if abund <= 0
return false if spfilter(n,primes)
return false if divs.include? abund
smalldivs = divs.reverse.select{|i| i < abund}
not sum_in_subset?(smalldivs,abund)
end
def sum_in_subset?(lst,n) #p [lst,n]
return false if n < 0
return true if lst.include? n
return false if lst.size == 1
first = lst.first
rest = lst[1..-1]
sum_in_subset?(rest, n-first) or sum_in_subset?(rest,n)
end
def divisors(n)
result = []
sr = Math.sqrt(n).to_i
(2 .. sr).each {|d|
if n.modulo(d) == 0
result << d
end
}
return [1] if result.empty?
hidivs = result.map {|d| n / d }.reverse
if hidivs[0] == result[-1]
[1] + result + hidivs[1..-1]
else
[1] + result + hidivs
end
end
def spfilter(n,primes)
m = 0
save_n = n
while n[0]==0
m += 1
n >>= 1
end
return false if m == 0
low = 2
high = 1 << (m+1)
primes.each {|p|
return false if p > high
if p > low
return true if n%p == 0
end
}
raise "not enough primes while checking #{save_n}"
end
# Sieve of Eratosthenes
def sieve(max_prime)
candidates = Array.new(max_prime,true)
candidates[0] = candidates[1] = false
2.upto(Math.sqrt(max_prime)) {|i|
if candidates[i]
(i+i).step(max_prime,i) {|j| candidates[j] = nil}
end
}
result = []
candidates.each_with_index {|prime, i| result << i if prime }
result
end
I have a solution for the "effectively useless" basket. It's a naive
algorithm, and I haven't yet received a number above 70 from it.
The advantages are that it's straightforward idiomatic Ruby, and core of the
algorithm is expressed about as tersely as Martin's definition. And I like
my ArraySubsetList class.
class Fixnum
def divisors
(1..self).select {|i| self % i == 0 }
end
end
module Enumerable
def sum
inject(0) {|m, o| m + o }
end
end
class Array
def subsets
ArraySubsetList.new(self)
end
end
class ArraySubsetList
def initialize(array) @array = array
end
def [](index)
return nil unless (0...size) === index
ret = [] @array.size.times {|i| ret << @array[i] if index[i] == 1 }
ret
end
def each
size.times {|bits| yield self[bits] }
end
include Enumerable
def size
1 << @array.size
end
alias length size
end
def wierd_numbers_up_to(max)
ret = []
for n in 1..max
# A weird number is defined as a number, n, such that the sum of all
its divisors
# (excluding n itself) is greater than n, but no subset of its
divisors sums up to
# exactly n.
divs = n.divisors
divs.delete i
if divs.sum > i &&
divs.subsets.select {|subset| subset.sum == i }.empty?
ret << i
yield i if block_given?
end
end
ret
end
if $0 == __FILE__
if ARGV.size == 1 && (ARGV[0].to_i rescue 0) > 0
wierd_numbers_up_to(ARGV[0].to_i) {|n| puts n }
else
puts "usage: #$0 n\n Find all weird numbers less than n"
end
end
# Break early version, checking if a number is weird
def weird_number(n)
d = r = s = nil
sum = 0
subset_sums = Hash.new
subset_sums[0] = true
for d in 1...n
next unless n % d == 0
# Calculate sum of all divisors
sum += d
# Calculate sums for all subsets
subset_sums.keys.each do | s |
return false if s + d == n
subset_sums[s + d] = true
end
end
sum > n
end
def weird_numbers(range)
range.select { | n | weird_number(n) }
end
I was starting to do that... I was building my HTTP object, and I
noticed how hard it was going to be to parse...... so I said screw it,
I'll make it easier.
I don't know, I think this is cheating. Plus he is missing a bunch of
weird numbers in his list.
Ryan
···
On 12/4/05, James Edward Gray II <james@grayproductions.net> wrote:
On Dec 4, 2005, at 7:27 AM, Hampton wrote:
> SO... I thought of a way to speed up the algorithm a lot! So, with a
> *few* more optimizations, here's the weirdo_fast algorithm.
>
> -------------------------------------------------------
>
> def weirdo_fast(max)
> list = [ 70,836,4030,5830,7192,7912,9272,10792,17272,45356,73616, #
> 83312,91388,113072,243892,254012,338572,343876,388076, #
> 519712,539744,555616,682592,786208,1188256,1229152,1713592, #
> 1901728,2081824,2189024,3963968 ]
> list.each do |num|
> puts num if num <= max
> end
> if max > list[list.size-1] then weirdo_exhaustive(list[list.size-1],
> max) end
> end
>
> -----------------------------------------------------
>
> A little faster, eh?
Bingo.
I was actually thinking of screen scraping them from on of the
encyclopedias mentioned in the quiz thread, but I like this even better.
Here's my solution. It looks pretty close to others. Not too fast, but
it gets the job done. I think after I get a chance to look at other
solutions I can write a some of this better.
class Integer
def divisors
divs = []
1.upto(Math.sqrt(self).to_i) do |i|
divs += [i ,self/i].uniq if (self%i == 0)
end
divs.sort.reverse #reverse speeds things up a bit
end
def weird?
divs = self.divisors - [self]
return false if divs.sum < self
divs.each_combination do |comb|
return false if comb.sum == self
end
return true
end
end
class Array
def each_combination
(2**self.length).times do |comb|
curr = []
self.length.times do |index|
curr << self[index] if(comb[index] == 1)
end
yield curr
end
end
Same here - I tried a bunch of stuff, but the code ended up being rather
slow, so I discarded it. It's still rather slow
N = ARGV[0].to_i
# precalculate the list of primes
def primes_to(n)
sieve = (0..n).to_a
2.upto(n) {|i|
next unless sieve[i]
(i*i).step(n, i) {|j| sieve[j] = nil}
}
sieve[2..-1].compact
end
PRIMES = primes_to(N)
# helper method
class Array
def bsearch(n)
i = 0
j = size - 1
k = (i+j)/2
while i < k
if at(k) > n
j = k
elsif at(k) < n
i = k
else
return k
end
k = (i+j)/2
end
return i
end
end
# factorisation routines - find the prime factors, then combine them to get a
# list of all factors
def prime_factors(x)
pf = Hash.new {|h, k| h[k] = 0}
PRIMES.each {|p|
break if p > x
while x % p == 0
pf[p] += 1
x /= p
end
}
pf
end
def expand_factors(f, pf)
return f if pf.empty?
p, n = pf.shift
powers = [p]
(n-1).times { powers << p * powers[-1] }
g = f.dup
powers.each {|i| f.each {|j| g << i*j } }
expand_factors(g, pf)
end
def factors(n)
a = expand_factors([1], prime_factors(n)).sort
a.pop
a
end
# and finally, the weirdness test
def weird?(n)
fact = factors(n)
···
Christian Neukirchen <chneukirchen@gmail.com> wrote:
#!ruby
=begin
The Quiz was real fun and I spent quite a lot of time on it. Below
source is rather easy, but believe me I tried lots of different ways
(such as dynamic binary knapsacks etc.), most of them suck because they
need to many method calls.
#
# test for abundance (sum(factors(n)) > n)
sum = fact.inject {|a, i| a+i}
return false if sum < n # weird numbers are abundant
# now the hard part
partials = [0]
fact.each {|f|
if sum < n
# discard those partials that are lower than the sum of all remaining
# factors
i = partials.bsearch(n-sum)
return false if partials[i] == (n-sum)
partials = partials[(i+1)..-1]
end
sum -= f # sum of all remaining factors
temp =
partials.each {|p|
j = f + p
break if j > n
l = n - j
next if l > sum
return false if (j == n) or (l == sum)
temp << j
}
# handwriting a merge sort didn't help :-/
partials = partials.concat(temp).sort.uniq
}
return true
end
def all_weird(n)
weird =
# odd numbers are not weird (unproven but true for all n < 10^17)
2.step(n, 2) {|i| weird << i if weird?(i) }
weird
end
Wow, I got a lot from looking at the other solutions. Thanks especially
to Ed, Ryan, Jannis and Christian. I see that the single biggest
performance gain comes from using a recursive sum_in_subset? method such
as that found in Ed's solution. I've borrowed from his code for this
fairly simple and straightforward resubmission. It doesn't perform as
well as the faster solutions, but it's much, much faster than my first
submission.
#!/usr/bin/env ruby
···
#
# Ruby Quiz Weird Numbers solution.
# Uses recursive sum_in_subset? approach borrowed from
# other solutions.
#
class Integer
def weird?
divisors = self.divisor_list
abundancy = divisors.inject { |total,x| total += x } - self
return false unless abundancy > 0
smalldivisors = divisors.reverse.select { |j| j <= abundancy }
return false if sum_in_subset?(smalldivisors, abundancy)
return true
end
def sum_in_subset?(list, target)
return false if target < 0
return true if list.include?(target)
return false if list.length == 1
first = list.first
rest = list[1..-1]
sum_in_subset?(rest, target-first) or sum_in_subset?(rest, target)
end
def divisor_list
list = []
(1..Math.sqrt(self).to_i).each do |x|
if self % x == 0
list << x
list << (self / x) unless x == 1 or (self / x) == x
end
end
return list.sort
end
end
####################
unless ARGV.length == 1
puts "Usage: #{$0} <max_value>"
end
max_value = ARGV.shift.to_i
(1..max_value).each { |n| puts n if n.weird? }
I was impressed when I started going through 1..1000 in under 15
seconds, so this is much slower than others report. I'm just going to
tell myself you all have much faster computers, and go to bed.
# returns each subset, in turn. Returns nil when there are no more
def succ
if @combo == nil or @combo == @set[-@num_elements..-1]
return nil if (@num_elements +=1) > @set.length @combo = @set[0,@num_elements]
else
index = (1..@num_elements).find {|i| @combo[-i] < @set[-i]} @combo[-index, index] = @set[@map[@combo[-index]], index]
end @combo
end
def find
while(x = succ)
break if yield x
end
x
end
end
class Integer
def proper_divisors
return if self < 2
div = Set.new [1]
2.upto(Math.sqrt(Float.induced_from(self)).to_i) {|i|
quotient, modulus = self.divmod(i)
div.merge([i,quotient]) if modulus.zero?
}
div.to_a.sort
end
def abundant?
self > 11 and [0].concat(proper_divisors).inject {|sum,n| sum += n}
self
end
def semiperfect?
return nil if self < 6
subsets = Subsets.new(proper_divisors, 2)
subsets.find {|subset| [0].concat(subset).inject {|sum,n| sum += n}
== self }
end
def weird?
self > 69 and abundant? and not semiperfect?
end
end
n = gets.strip
exit if n =~ /\D/ or n !~ /[^0]/
p (1..n.to_i).find_all {|i| i.weird? }
Here is my solution. It is pretty fast, but not quite as fast as
Rob's. For example his takes 6.797 seconds to calculate all weird
numbers up to 50000, whereas mine takes 7.375. Our solutions are quite
similar. Some of the other solutions are REALLY SLOW though. Probably
one of the biggest optimizations was using the square root of a given
number to calculate half the divisors, then use those to get the other
half. For example if 2 is a divisor of 14, then so is 14/2 = 7. For
big numbers this can be a massive speed-up.
Ryan
class Array
def sum
inject(0) do |result, i|
result + i
end
end
end
class Integer
def weird?
# No odd numbers are weird within reasonable limits.
return false if self % 2 == 1
# A weird number is abundant but not semi-perfect.
divisors = calc_divisors
abundance = divisors.sum - 2 * self
# First make sure the number is abundant.
if abundance > 0
# Now see if the number is semi-perfect. If it is, it isn't weird.
# First thing see if the abundance is in the divisors.
if divisors.include?(abundance)
false
else
# Now see if any combination sums of divisors yields the abundance.
# We reject any divisors greater than the abundance and reverse the
# result to try and get sums close to the abundance sooner.
to_search = divisors.reject{|i| i > abundance}.reverse
sum = to_search.sum
if sum == abundance
false
elsif sum < abundance
true
else
not abundance.sum_in_subset?(to_search)
end
end
else
false
end
end
def calc_divisors
res=[1]
2.upto(Math.sqrt(self).floor) do |i|
if self % i == 0
res << i
end
end
res.reverse.each do |i|
res << self / i
end
res
end
def sum_in_subset?(a)
if self < 0
false
elsif a.include?(self)
true
else
if a.length == 1
false
else
f = a.first
remaining = a[1..-1]
(self - f).sum_in_subset?(remaining) or sum_in_subset?(remaining)
end
end
end
end
if $0 == __FILE__
if ARGV.length < 1
puts "Usage: #$0 <upper limit>"
exit(1)
end
puts "Weird numbers up to and including #{ARGV[0]}:"
70.upto(ARGV[0].to_i) do |i|
puts i if i.weird?
end
end
Plus he is missing a bunch of weird numbers in his list.
I haven't compared the Array in question with the posted sequences. Perhaps it's not very complete. Let me ask you this though, since we're talking about this: Which is easier to debug, the sequence list or a broken calculation solution?
Didn't the solution also brute force answers when it left its list of known numbers?
One last question: How well does your presumably fast solution do when it goes beyond the listed sequence? Does it still find lots of answers, quickly?
I'm really not trying to be mean here and I apologize if I'm coming off that way.
I think what Hampton hit on is a simple cache optimization. It's fast and very effective. I don't think we should be so quick to toss it out as a viable approach...
James Edward Gray II
···
On Dec 4, 2005, at 11:29 AM, Ryan Leavengood wrote:
Here's mine.
I started out with very straightforward programming, but ended up
making it muddier as I optimized. I also implemented a bunch of
functions that I figured I could probably find alread written if I
looked, but I figured they were good exercises : Integer#factors,
Integer#divisors, Array#all_combinations....
I thought it was pretty fast, especially compared to my initial
implementation. Then I timed Ryan's on my machine... Oh well. I
enjoyed the challenge.
-Adam
···
---
class Integer
def weird?
(d = divisors).pop #remove self (which is always last)
d.sum > self &&
!d.quick_find_subset_with_sum(self) && #weed out most
!d.find_subset_with_sum(self) #confirm the rest
end
def divisors
factors.all_combinations.uniq.inject([]){|result,combo|
result << combo.product
}.sort.uniq
end
def factors
value, candidate = self, 3
factors = [1]
while value % 2 == 0
factors << 2
value /= 2
end
while candidate <= Math.sqrt(value)
while value % candidate == 0
factors << candidate
value /= candidate
end
candidate += 2
end
factors << value if value != 1
factors
end
end
class Array
def product
inject(1){|p,v| p*v}
end
def sum
inject(0){|s,v| s+v}
end
def all_combinations
ComboIndexGenerator.new(self.size).inject([]) {|result, index_set|
result << values_at(*index_set)
}
end
#this was my first attempt, which was straightforward,
# but slow as heck for large sets
def slow_find_subset_with_sum n
return nil if sum < n
all_combinations.each {|set|
return set if set.sum == n
}
nil
end
#this is my second attempt which is fast but misses some subsets. #but it is useful for quickly rejecting many non-weird numbers.
def quick_find_subset_with_sum n
a = self.sort.reverse
sum,set = 0,[]
a.each {|e|
if (sum+e <= n)
sum+=e
set<<e
end
return set if sum == n
}
nil
end
#this one works pretty quickly... #it never tests subsets which are less than the sum, #and keeps track of sets it has already calculated
def find_subset_with_sum n
possibilities, seen = [self],{}
until possibilities.empty?
candidate = possibilities.pop
diff = candidate.sum - n
return candidate if diff == 0
break if diff < 0
candidate.each_with_index{|e,i|
break if e > diff
new_cand = (candidate.dup)
new_cand.delete_at(i)
return new_cand if e == diff
possibilities << new_cand if !seen[new_cand]
seen[new_cand]=true
}
end
nil
end
end
#this class generates an all the possible combinations of n items #it returns an array with the next combination every time you call #next
class ComboIndexGenerator
include Enumerable
def initialize nitems @n = nitems @max = 2**@n
@val=0
end
def to_a
return nil if @val==@max
(0..@n).inject([]){|a,bit| a<<bit if @val[bit]==1; a}
end
def next
@val+=1 if @val<@max
to_a
end
def each &b
yield to_a
while (n=self.next)
yield n
end
end
end
if $0 == __FILE__
if ARGV.length < 1
puts "Usage: #$0 <upper limit>"
exit(1)
end
puts "Weird numbers up to and including #{ARGV[0]}:"
70.upto(ARGV[0].to_i) do |i|
puts i if i.weird?
end
end
def sum_in_subset?(a)
if self < 0
false
elsif a.include?(self)
true
else
if a.length == 1
false
else
f = a.first
remaining = a[1..-1]
(self - f).sum_in_subset?(remaining) or sum_in_subset?(remaining)
end
end
end
end
nice and speedy.. mine is awful and slow.
···
On 12/4/05, Ryan Leavengood <leavengood@gmail.com> wrote:
