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

Best,
James