method

permutation

v1_8_7_72 - Show latest stable - 0 notes - Class: Array

permutation(...) public

When invoked with a block, yield all permutations of length n of the elements of ary, then return the array itself. If n is not specified, yield all permutations of all elements. The implementation makes no guarantees about the order in which the permutations are yielded.

When invoked without a block, return an enumerator object instead.

Examples:

    a = [1, 2, 3]
    a.permutation.to_a     #=> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    a.permutation(1).to_a  #=> [[1],[2],[3]]
    a.permutation(2).to_a  #=> [[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]]
    a.permutation(3).to_a  #=> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    a.permutation(0).to_a  #=> [[]] # one permutation of length 0
    a.permutation(4).to_a  #=> []   # no permutations of length 4

Show source

/*
 *  call-seq:
 *     ary.permutation { |p| block }          -> array
 *     ary.permutation                        -> enumerator
 *     ary.permutation(n) { |p| block }       -> array
 *     ary.permutation(n)                     -> enumerator
 *  
 * When invoked with a block, yield all permutations of length <i>n</i>
 * of the elements of <i>ary</i>, then return the array itself.
 * If <i>n</i> is not specified, yield all permutations of all elements.
 * The implementation makes no guarantees about the order in which 
 * the permutations are yielded.
 *
 * When invoked without a block, return an enumerator object instead.
 * 
 * Examples:
 *
 *     a = [1, 2, 3]
 *     a.permutation.to_a     #=> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 *     a.permutation(1).to_a  #=> [[1],[2],[3]]
 *     a.permutation(2).to_a  #=> [[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]]
 *     a.permutation(3).to_a  #=> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 *     a.permutation(0).to_a  #=> [[]] # one permutation of length 0
 *     a.permutation(4).to_a  #=> []   # no permutations of length 4
 */

static VALUE
rb_ary_permutation(argc, argv, ary)
    int argc;
    VALUE *argv;
    VALUE ary;
{
    VALUE num;
    long r, n, i;

    n = RARRAY(ary)->len;                  /* Array length */
    RETURN_ENUMERATOR(ary, argc, argv);   /* Return enumerator if no block */
    rb_scan_args(argc, argv, "01", &num);
    r = NIL_P(num) ? n : NUM2LONG(num);   /* Permutation size from argument */

    if (r < 0 || n < r) { 
        /* no permutations: yield nothing */
    }
    else if (r == 0) { /* exactly one permutation: the zero-length array */
        rb_yield(rb_ary_new2(0));
    }
    else if (r == 1) { /* this is a special, easy case */
        for (i = 0; i < RARRAY(ary)->len; i++) {
            rb_yield(rb_ary_new3(1, RARRAY(ary)->ptr[i]));
        }
    }
    else {             /* this is the general case */
        volatile VALUE t0 = tmpbuf(n,sizeof(long));
        long *p = (long*)RSTRING(t0)->ptr;
        volatile VALUE t1 = tmpbuf(n,sizeof(int));
        int *used = (int*)RSTRING(t1)->ptr;
        VALUE ary0 = ary_make_shared(ary); /* private defensive copy of ary */

        for (i = 0; i < n; i++) used[i] = 0; /* initialize array */

        permute0(n, r, p, 0, used, ary0); /* compute and yield permutations */
        RB_GC_GUARD(t0);
        RB_GC_GUARD(t1);
    }
    return ary;
}

permutation

Related methods