I’m working on some of the CtCI (Cracking the Coding Interview) questions (9.4 - return all subsets of a set) and have run into a strange problem. Below is: (1) the code, (2) the spec, and (3) the output. Notice that first of all, the result gets overlaid, not appended to and that second, the each_index block is only executed once.
It looks to me as if the recursion is fouled up and values are getting overlaid… I must have done something really strange :=)
FYI… I know there are easier ways to do this in Ruby with the repeated_combination() method; I just watend to try it without that method, similar to what I might have had to do with Java.
(1) the code
def return_subsets_raw
@result_raw = []
ss_raw(@set)
@result_raw.uniq
end
def ss_raw set
puts "set: #{set}"
@result_raw << set
return if set.size == 1
puts "result: #{@result_raw}"
set.each_index do |i|
tmp = set
tmp.delete_at i
puts "(#{i}) - tmp: #{tmp}; result: #{@result_raw}"
ss_raw(tmp)
end
end
(2) the spec
it "returns all subsets for a set of three elements" do
set = Subsets.new [1,2,3]
set.__send__(method).should =~ [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
end
(3) the output
set: [1, 2, 3]
result: [[1, 2, 3]]
(0) - tmp: [2, 3]; result: [[2, 3]] <=== What happened to previous value?
set: [2, 3]
result: [[2, 3], [2, 3]]
<=== Where's the (1) repitition?
(0) - tmp: [3]; result: [[3], [3]]
set: [3]
…
2) Subsets returns all subsets for a set of three elements
Failure/Error: set.__send__(method).should =~ [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
expected collection contained: [[1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
actual collection contained: [[3]]
the missing elements were: [[1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3]]
Edit. If I simply remove the recursive call (the ss_raw(tmp) inside the each_index loop), then the each_index occurs twice, but the value of @result_raw is still somehow overlaid. Here’s the output from that scenario, again for an input of [1,2,3]:
set: [1, 2, 3]
result: [[1, 2, 3]]
(0) - tmp: [2, 3]; result: [[2, 3]]
(1) - tmp: [2]; result: [[2]]
1) Subsets returns all subsets for a set of three elements
Failure/Error: set.__send__(method).should =~ [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
expected collection contained: [[1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
actual collection contained: [[2]]
the missing elements were: [[1], [1, 2], [1, 2, 3], [1, 3], [2, 3], [3]]
Answer: This last set of results gave me the key to the problem. I had thought that tmp and set were two different variables, but they were actually just two different names pointing to the same storage space. By changing
tmp = set
to
temp = set.clone
everything now works as expected. Try it out in pry:
a = [1,2,3]
a = b
a .delete_at 2
a and b will both equal [1,2]