James Gray
12/20/2006 1:49:00 PM
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