view release on metacpan or  search on metacpan

Combinatorics.xs  view on Meta::CPAN

 */
int __next_permutation(SV* tuple_avptr)
{
    AV* tuple = GETAV(tuple_avptr);
    I32 max_n, j, h, k;
    IV aj;

    max_n = av_len(tuple);

    /* [Find j.] Find the element a(j) behind the longest decreasing tail. */
    for (j = max_n-1; j >= 0 && GETIV(tuple, j) > GETIV(tuple, j+1); --j)
        ;
    if (j == -1)
        return -1;

    /* [Increase a(j).] Find the rightmost element a(h) greater than a(j) and swap them. */
    aj = GETIV(tuple, j);
    for (h = max_n; aj > GETIV(tuple, h); --h)
        ;
    __swap(tuple, j, h);

    /* [Reverse a(j+1)...a(max_n)] Reverse the tail. */
    for (k = j+1, h = max_n; k < h; ++k, --h)
        __swap(tuple, k, h);

    /* Done. */
    return 1;
}


int __next_permutation_heap(SV* a_avptr, SV* c_avptr)
{
    AV* a = GETAV(a_avptr);
    AV* c = GETAV(c_avptr);
    int k;
    I32 n;
    IV ck;

    n = av_len(a) + 1;

    for (k = 1, ck = GETIV(c, k); ck == k; ++k, ck = GETIV(c, k))
        SETIV(c, k, 0);

    if (k == n)
        return -1;

    ++ck;
    SETIV(c, k, ck);

    k % 2 == 0 ? __swap(a, k, 0) : __swap(a, k, ck-1);

    return k;
}


/**
 * The only algorithms I have found by now are either recursive, or a
 * naive wrapper around permutations() that loops over all of them and
 * discards the ones with fixed-points.
 *
 * We take here a mixed-approach, which consists on starting with the
 * algorithm in __next_permutation() and tweak a couple of places that
 * allow us to skip a significant number of permutations sometimes.
 *
 * Benchmarking shows this subroutine makes derangements() more than
 * two and a half times faster than permutations() for n = 8.
 */
int __next_derangement(SV* tuple_avptr)
{
    AV* tuple = GETAV(tuple_avptr);
    I32 max_n, min_j, j, h, k;
    IV aj;

    max_n = av_len(tuple);
    min_j = max_n;

    THERE_IS_A_FIXED_POINT:
    /* Find the element a(j) behind the longest decreasing tail. */
    for (j = max_n-1; j >= 0 && GETIV(tuple, j) > GETIV(tuple, j+1); --j)
          ;
    if (j == -1)
        return -1;

    if (min_j > j)
        min_j = j;

    /* Find the rightmost element a(h) greater than a(j) and swap them. */
    aj = GETIV(tuple, j);
    for (h = max_n; aj > GETIV(tuple, h); --h)
        ;
    __swap(tuple, j, h);

    /* If a(h) was j leave the tail in decreasing order and try again. */
    if (GETIV(tuple, j) == j)
        goto THERE_IS_A_FIXED_POINT;

    /* I tried an alternative approach that would in theory avoid the
    generation of some permutations with fixed-points: keeping track of
    the leftmost fixed-point, and reversing the elements to its right.
    But benchmarks up to n = 11 showed no difference whatsoever.
    Thus, I left this version, which is simpler.

    That n = 11 does not mean there was a difference for n = 12, it
    means I stopped benchmarking at n = 11. */

    /* Otherwise reverse the tail and return if there's no fixed point. */
    for (k = j+1, h = max_n; k < h; ++k, --h)
        __swap(tuple, k, h);
    for (k = max_n; k > min_j; --k)
        if (GETIV(tuple, k) == k)
            goto THERE_IS_A_FIXED_POINT;

    return 1;
}

/*
 * This is a transcription of algorithm 3 from [3].
 *
 * It is a classical approach based on restricted growth strings, which are
 * introduced in the paper.
 */

Combinatorics.xs  view on Meta::CPAN

    len_k = av_len(k);
    for (i = len_k; i > 0; --i) {
        if (GETIV(k, i) < p-1 && GETIV(k, i) <= GETIV(M, i-1)) {
            INCR(k, i);

            if (GETIV(k, i) > GETIV(M, i))
                SETIV(M, i, GETIV(k, i));

            n_minus_p = len_k + 1 - p;
            mi = GETIV(M, i);
            x = n_minus_p + mi;
            for (j = i+1; j <= x; ++j) {
                SETIV(k, j, 0);
                SETIV(M, j, mi);
            }
            for (j = x+1; j <= len_k; ++j) {
                SETIV(k, j, j - n_minus_p);
                SETIV(M, j, j - n_minus_p);
            }
            return i;
        }
    }

    return -1;
}

/*
 * This subroutine has been copied from List::PowerSet.
 *
 * It uses a vector of bits "odometer" to indicate which elements to include
 * in each iteration. The odometer runs and eventually exhausts all possible
 * combinations of 0s and 1s.
 */
AV* __next_subset(SV* data_avptr, SV* odometer_avptr)
{
    AV* data     = GETAV(data_avptr);
    AV* odometer = GETAV(odometer_avptr);
    I32 len_data = av_len(data);
    AV* subset   = newAV();
    IV adjust    = 1;
    int i;
    IV n;

    for (i = 0; i <= len_data; ++i) {
        n = GETIV(odometer, i);
        if (n) {
            av_push(subset, newSVsv(*av_fetch(data, i, 0)));
        }
        if (adjust) {
            adjust = 1 - n;
            SETIV(odometer, i, adjust);
        }
    }

    return (AV*) sv_2mortal((SV*) subset);
}

/** -------------------------------------------------------------------
 *
 * XS stuff starts here.
 *
 */

MODULE = Algorithm::Combinatorics   PACKAGE = Algorithm::Combinatorics
PROTOTYPES: DISABLE

int
__next_combination(tuple_avptr, max_n)
    SV* tuple_avptr
    int max_n

int
__next_combination_with_repetition(tuple_avptr, max_n)
    SV* tuple_avptr
    int max_n

int
__next_variation(tuple_avptr, used_avptr, max_n)
    SV* tuple_avptr
    SV* used_avptr
    int max_n

int
__next_variation_with_repetition(tuple_avptr, max_n)
    SV* tuple_avptr
    int max_n

int
__next_variation_with_repetition_gray_code(tuple_avptr, f_avptr, o_avptr, max_m)
    SV* tuple_avptr
    SV* f_avptr
    SV* o_avptr
    int max_m

int
__next_permutation(tuple_avptr)
    SV* tuple_avptr

int
__next_permutation_heap(a_avptr, c_avptr)
    SV* a_avptr
    SV* c_avptr

int
__next_derangement(tuple_avptr)
    SV* tuple_avptr

int
__next_partition(k_avptr, M_avptr)
    SV* k_avptr
    SV* M_avptr

int
__next_partition_of_size_p(k_avptr, M_avptr, p)
    SV* k_avptr
    SV* M_avptr
    int p

AV*
__next_subset(data_avptr, odometer_avptr)