From: dblack@...
Date: 2006-12-20T13:46:41+09:00
Subject: Re: routine sometimes not returning what i expect

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


David

-- 
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)