combination

/*
 *  call-seq:
 *     ary.combination(n) { |c| block }    -> ary
 *     ary.combination(n)                  -> enumerator
 *  
 * When invoked with a block, yields all combinations of length <i>n</i> 
 * of elements from <i>ary</i> and then returns <i>ary</i> itself.
 * The implementation makes no guarantees about the order in which 
 * the combinations are yielded.
 *
 * When invoked without a block, returns an enumerator object instead.
 *     
 * Examples:
 *
 *     a = [1, 2, 3, 4]
 *     a.combination(1).to_a  #=> [[1],[2],[3],[4]]
 *     a.combination(2).to_a  #=> [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
 *     a.combination(3).to_a  #=> [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
 *     a.combination(4).to_a  #=> [[1,2,3,4]]
 *     a.combination(0).to_a  #=> [[]] # one combination of length 0
 *     a.combination(5).to_a  #=> []   # no combinations of length 5
 *     
 */

static VALUE
rb_ary_combination(ary, num)
    VALUE ary;
    VALUE num;
{
    long n, i, len;

    n = NUM2LONG(num);
    RETURN_ENUMERATOR(ary, 1, &num);
    len = RARRAY(ary)->len;
    if (n < 0 || len < n) {
        /* yield nothing */
    }
    else if (n == 0) {
        rb_yield(rb_ary_new2(0));
    }
    else if (n == 1) {
        for (i = 0; i < len; i++) {
            rb_yield(rb_ary_new3(1, RARRAY(ary)->ptr[i]));
        }
    }
    else {
        volatile VALUE t0 = tmpbuf(n+1, sizeof(long));
        long *stack = (long*)RSTRING(t0)->ptr;
        long nlen = combi_len(len, n);
        volatile VALUE cc = rb_ary_new2(n);
        VALUE *chosen = RARRAY(cc)->ptr;
        long lev = 0;

        RBASIC(cc)->klass = 0;
        MEMZERO(stack, long, n);
        stack[0] = -1;
        for (i = 0; i < nlen; i++) {
            chosen[lev] = RARRAY(ary)->ptr[stack[lev+1]];
            for (lev++; lev < n; lev++) {
                chosen[lev] = RARRAY(ary)->ptr[stack[lev+1] = stack[lev]+1];
            }
            rb_yield(rb_ary_new4(n, chosen));
            do {
                stack[lev--]++;
            } while (lev && (stack[lev+1]+n == len+lev+1));
        }
    }
    return ary;
}