Routine sometimes not returning what i expect

ruby-talk
1

As part of my first-ever submission to the ruby quiz, I wrote (translated from Python, really) a recursive routine to return all n-combinations of an array. So that:

combinations([1, 2, 3], 2)

would return

[[1, 2], [1, 3], [2, 3]]

and combinations([1, 2, 3], 2, false)

would return

[[1, 2], [1, 3], [2, 3], [2, 1], [3, 1], [3, 2]]

My original code was as follows (with some stupid corrections):

def combinations sequence, n, unique=true
  return [] if n == 0
  return sequence if n == 1
  result = []

  0.upto(sequence.length - 1) do |i|
    sub_sequence = sequence[(i + 1)..-1]
    sub_sequence += sequence[0..i] if not unique

    combinations(sequence[(i + 1)..-1], n - 1).each do |smaller|
      result << [sequence[i]] + smaller
    end
  end

  result
end

But this gives a "TypeError: can't convert Fixnum into Array", from the line "result << [sequence[i]] + smaller". After a few minutes of scratching my head, it became clear that sometimes the result of combinations(...) was an Array (which is expected) and sometimes it was of type whatever the array elements were (which is unexpected), whenever the array would be a singleton.

I ended up changing it to "result << ([sequence[i]] + [smaller]).flatten", but after I turned it in I realized that won't do - I'd want the code to handle cases where elements of the array are themselves arrays. I added the check "smaller = [smaller] if smaller.class != Array", but it doesn't *seem* like I should have to do that.

Where am I going wrong here?

Best,
James Cunningham

2

Okay. It occurs to me that I was wrong in two respects.

Even with the change of adding "smaller = [smaller] if smaller.class != Array", I still get weird flattening.

combinations([1, 2, [3, 4]], 2)

should return

[[1, 2], [1, [3, 4]], [2, [3, 4]]]

but instead returns

[[1, 2], [1, 3, 4], [2, 3, 4]]

Also, combinations([1, 2, 3], 2, false) doesn't do what I'd expect: as far as I can tell it should collect all 2-permutations, but it has the same effect as combinations([1, 2, 3], 2).

For reference, here's the Python code that seems to work in the way I describe:

def combinations(sequence, n, unique=True):
    if not n: yield

    for i in range(len(sequence)):
        sub_sequence = sequence[i + 1:]
        if not unique: sub_sequence += sequence[:i]

        for smaller in combinations(sub_sequence, n - 1, unique):
            yield [sequence[i]] + smaller

Best,
James

···

On 2006-12-19 22:10:13 -0500, James Cunningham <jameshcunningham@gmail.com> said:

As part of my first-ever submission to the ruby quiz, I wrote (translated from Python, really) a recursive routine to return all n-combinations of an array. So that:

combinations([1, 2, 3], 2)

would return

[[1, 2], [1, 3], [2, 3]]

and combinations([1, 2, 3], 2, false)

would return

[[1, 2], [1, 3], [2, 3], [2, 1], [3, 1], [3, 2]]

My original code was as follows (with some stupid corrections):

def combinations sequence, n, unique=true
  return if n == 0
  return sequence if n == 1
  result =

  0.upto(sequence.length - 1) do |i|
    sub_sequence = sequence[(i + 1)..-1]
    sub_sequence += sequence[0..i] if not unique

    combinations(sequence[(i + 1)..-1], n - 1).each do |smaller|
      result << [sequence[i]] + smaller
    end
  end

  result
end

But this gives a "TypeError: can't convert Fixnum into Array", from the line "result << [sequence[i]] + smaller". After a few minutes of scratching my head, it became clear that sometimes the result of combinations(...) was an Array (which is expected) and sometimes it was of type whatever the array elements were (which is unexpected), whenever the array would be a singleton.

I ended up changing it to "result << ([sequence[i]] + [smaller]).flatten", but after I turned it in I realized that won't do - I'd want the code to handle cases where elements of the array are themselves arrays. I added the check "smaller = [smaller] if smaller.class != Array", but it doesn't *seem* like I should have to do that.

Where am I going wrong here?

Best,
James Cunningham

3

Hi --

As part of my first-ever submission to the ruby quiz, I wrote (translated from Python, really) a recursive routine to return all n-combinations of an array. So that:

combinations([1, 2, 3], 2)

would return

[[1, 2], [1, 3], [2, 3]]

and combinations([1, 2, 3], 2, false)

would return

[[1, 2], [1, 3], [2, 3], [2, 1], [3, 1], [3, 2]]

My original code was as follows (with some stupid corrections):

def combinations sequence, n, unique=true
  return if n == 0
  return sequence if n == 1
  result =

  0.upto(sequence.length - 1) do |i|
    sub_sequence = sequence[(i + 1)..-1]
    sub_sequence += sequence[0..i] if not unique

    combinations(sequence[(i + 1)..-1], n - 1).each do |smaller|
      result << [sequence[i]] + smaller
    end
  end

  result
end

But this gives a "TypeError: can't convert Fixnum into Array", from the line "result << [sequence[i]] + smaller". After a few minutes of scratching my head, it became clear that sometimes the result of combinations(...) was an Array (which is expected) and sometimes it was of type whatever the array elements were (which is unexpected), whenever the array would be a singleton.

I ended up changing it to "result << ([sequence[i]] + [smaller]).flatten", but after I turned it in I realized that won't do - I'd want the code to handle cases where elements of the array are themselves arrays. I added the check "smaller = [smaller] if smaller.class != Array", but it doesn't *seem* like I should have to do that.

Where am I going wrong here?

Best,
James Cunningham

Okay. It occurs to me that I was wrong in two respects.

Even with the change of adding "smaller = [smaller] if smaller.class != Array", I still get weird flattening.

combinations([1, 2, [3, 4]], 2)

should return

[[1, 2], [1, [3, 4]], [2, [3, 4]]]

but instead returns

[[1, 2], [1, 3, 4], [2, 3, 4]]

Also, combinations([1, 2, 3], 2, false) doesn't do what I'd expect: as far as I can tell it should collect all 2-permutations, but it has the same effect as combinations([1, 2, 3], 2).

For reference, here's the Python code that seems to work in the way I describe:

def combinations(sequence, n, unique=True):
  if not n: yield

  for i in range(len(sequence)):
      sub_sequence = sequence[i + 1:]
      if not unique: sub_sequence += sequence[:i]

      for smaller in combinations(sub_sequence, n - 1, unique):
          yield [sequence[i]] + smaller

Here's a slightly modified version of your Ruby version. Part of the
problem in yours was that you were assigning to sub_sequence but then
throwing it away and calling combinations recursively on a different
sub-array of sequence.

def combinations(sequence, n, unique=true)
   return if n == 0
   return sequence if n == 1

   result =

   sequence.each_with_index do |e,i|
     sub_sequence = sequence[(i + 1)..-1]
     sub_sequence.concat(sequence[0...i]) if not unique
     combinations(sub_sequence, n - 1, unique).each do |smaller|
       result << [e] + [smaller]
     end
   end

   result
end

David

···

On Wed, 20 Dec 2006, James Cunningham wrote:

On 2006-12-19 22:10:13 -0500, James Cunningham <jameshcunningham@gmail.com> > said:

--
Q. What's a good holiday present for the serious Rails developer?
A. RUBY FOR RAILS by David A. Black (http://www.manning.com/black\)
    aka The Ruby book for Rails developers!
Q. Where can I get Ruby/Rails on-site training, consulting, coaching?
A. Ruby Power and Light, LLC (http://www.rubypal.com)

4

[snip]
Here's a slightly modified version of your Ruby version. Part of the
problem in yours was that you were assigning to sub_sequence but then
throwing it away and calling combinations recursively on a different
sub-array of sequence.

Erm, I think what you mean is that *all of my problem was that I was being an idiot". Yes, that seems to be it.

def combinations(sequence, n, unique=true)
   return if n == 0
   return sequence if n == 1

   result =

   sequence.each_with_index do |e,i|
     sub_sequence = sequence[(i + 1)..-1]
     sub_sequence.concat(sequence[0...i]) if not unique
     combinations(sub_sequence, n - 1, unique).each do |smaller|
       result << [e] + [smaller]
     end
   end

   result
end

David

def combinations sequence, n, unique=true
  return if n == 0
  return sequence if n == 1
  result =

  0.upto(sequence.length - 1) do |i|
    sub_sequence = sequence[(i + 1)..-1]
    sub_sequence += sequence[0..i] if not unique

    combinations(sub_sequence, n - 1, unique).each do |smaller|
      result << [sequence[i]] + [smaller]
    end
  end

  result
end

This works perfectly now, but yours is far prettier, so I shall use it. Thank you!

Best,
James

···

On 2006-12-19 23:46:41 -0500, dblack@wobblini.net said:

5

I took my own stab at this problem, but I think David's version came out prettier:

def combinations(sequence, n, unique = true)
   return Array.new if n == 0
   return sequence if n == 1

   (0...sequence.length).inject(Array.new) do |result, i|
     sub_sequence = sequence[(i + 1)..-1]
     sub_sequence.concat(sequence[0...i]) unless unique
     combinations(sub_sequence, n - 1, unique).each do |smaller|
       result << [sequence[i]] + [smaller]
     end
     result
   end
end

James Edward Gray II

···

On Dec 19, 2006, at 10:46 PM, dblack@wobblini.net wrote:

Hi --

On Wed, 20 Dec 2006, James Cunningham wrote:

On 2006-12-19 22:10:13 -0500, James Cunningham >> <jameshcunningham@gmail.com> said:

As part of my first-ever submission to the ruby quiz, I wrote (translated from Python, really) a recursive routine to return all n-combinations of an array. So that:
combinations([1, 2, 3], 2)
would return
[[1, 2], [1, 3], [2, 3]]
and combinations([1, 2, 3], 2, false)
would return
[[1, 2], [1, 3], [2, 3], [2, 1], [3, 1], [3, 2]]
My original code was as follows (with some stupid corrections):
def combinations sequence, n, unique=true
  return if n == 0
  return sequence if n == 1
  result =

  0.upto(sequence.length - 1) do |i|
    sub_sequence = sequence[(i + 1)..-1]
    sub_sequence += sequence[0..i] if not unique

    combinations(sequence[(i + 1)..-1], n - 1).each do |smaller|
      result << [sequence[i]] + smaller
    end
  end

  result
end
But this gives a "TypeError: can't convert Fixnum into Array", from the line "result << [sequence[i]] + smaller". After a few minutes of scratching my head, it became clear that sometimes the result of combinations(...) was an Array (which is expected) and sometimes it was of type whatever the array elements were (which is unexpected), whenever the array would be a singleton.
I ended up changing it to "result << ([sequence[i]] + [smaller]).flatten", but after I turned it in I realized that won't do - I'd want the code to handle cases where elements of the array are themselves arrays. I added the check "smaller = [smaller] if smaller.class != Array", but it doesn't *seem* like I should have to do that.
Where am I going wrong here?
Best,
James Cunningham

Okay. It occurs to me that I was wrong in two respects.

Even with the change of adding "smaller = [smaller] if smaller.class != Array", I still get weird flattening.

combinations([1, 2, [3, 4]], 2)

should return

[[1, 2], [1, [3, 4]], [2, [3, 4]]]

but instead returns

[[1, 2], [1, 3, 4], [2, 3, 4]]

Also, combinations([1, 2, 3], 2, false) doesn't do what I'd expect: as far as I can tell it should collect all 2-permutations, but it has the same effect as combinations([1, 2, 3], 2).

For reference, here's the Python code that seems to work in the way I describe:

def combinations(sequence, n, unique=True):
  if not n: yield

  for i in range(len(sequence)):
      sub_sequence = sequence[i + 1:]
      if not unique: sub_sequence += sequence[:i]

      for smaller in combinations(sub_sequence, n - 1, unique):
          yield [sequence[i]] + smaller

Here's a slightly modified version of your Ruby version. Part of the
problem in yours was that you were assigning to sub_sequence but then
throwing it away and calling combinations recursively on a different
sub-array of sequence.

def combinations(sequence, n, unique=true)
  return if n == 0
  return sequence if n == 1

  result =

  sequence.each_with_index do |e,i|
    sub_sequence = sequence[(i + 1)..-1]
    sub_sequence.concat(sequence[0...i]) if not unique
    combinations(sub_sequence, n - 1, unique).each do |smaller|
      result << [e] + [smaller]
    end
  end

  result
end