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

```