Routine sometimes not returning what i expect

Ruby
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 C.

2

On 2006-12-19 22:10:13 -0500, James C.
[email protected] said:

and combinations([1, 2, 3], 2, false)
result = []
result
[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 C.

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