← Back to Upcase

Strange results from recursive method


(Jon Seidel) #1

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]


(Ben Orenstein) #2

I really dig that you post your answers when you figure them out.

I think writing up the forum post asking the question is helping you find the answer as well.


(Jon Seidel) #3

Thanks, Ben… and yes: writing it up is very helpful. Just thinking the problem through so that I can clearly describe it helps clarify my thinking and isolate the various elements that are in play. Sorta like a solo pairing session :=)