From: James Edward Gray II <james@...>
Date: 2006-12-20T22:48:35+09:00
Subject: Re: routine sometimes not returning what i expect

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

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