Algorithm-Combinatorics

 view release on metacpan or  search on metacpan

Combinatorics.pm  view on Meta::CPAN

sub __variations_with_repetition_gray_code {
    my ($data, $k) = @_;
    __check_params($data, $k);

    return __contextualize(__null_iter()) if $k < 0;
    return __contextualize(__once_iter()) if $k == 0;

    my @indices        = (0) x $k;
    my @focus_pointers = 0..$k; # yeah, length $k+1
    my @directions     = (1) x $k;
    my $iter = Algorithm::Combinatorics::Iterator->new(sub {
        __next_variation_with_repetition_gray_code(
            \@indices,
            \@focus_pointers,
            \@directions,
            @$data-1,
        ) == -1 ? undef : [ @{$data}[@indices] ];
    }, [ @{$data}[@indices] ]);

Combinatorics.pm  view on Meta::CPAN

See some values at L<http://www.research.att.com/~njas/sequences/A000166>.


=head2 complete_permutations(\@data)

This is an alias for C<derangements>, documented above.


=head2 variations(\@data, $k)

The variations of length C<$k> of C<@data> are all the tuples of length C<$k> consisting of elements of C<@data>. For example, for C<@data = (1, 2, 3)> and C<$k = 2>:

    (1, 2)
    (1, 3)
    (2, 1)
    (2, 3)
    (3, 1)
    (3, 2)

For this to make sense, C<$k> has to be less than or equal to the length of C<@data>.

Note that

    permutations(\@data);

is equivalent to

    variations(\@data, scalar @data);

The number of variations of C<n> elements taken in groups of C<k> is:

    v(n, k) = 1,                        if k = 0
    v(n, k) = n*(n-1)*...*(n-k+1),      if 0 < k <= n


=head2 variations_with_repetition(\@data, $k)

The variations with repetition of length C<$k> of C<@data> are all the tuples of length C<$k> consisting of elements of C<@data>, including repetitions. For example, for C<@data = (1, 2, 3)> and C<$k = 2>:

    (1, 1)
    (1, 2)
    (1, 3)
    (2, 1)
    (2, 2)
    (2, 3)
    (3, 1)
    (3, 2)
    (3, 3)

Note that C<$k> can be greater than the length of C<@data>. For example, for C<@data = (1, 2)> and C<$k = 3>:

    (1, 1, 1)
    (1, 1, 2)
    (1, 2, 1)
    (1, 2, 2)
    (2, 1, 1)
    (2, 1, 2)
    (2, 2, 1)
    (2, 2, 2)

Combinatorics.pm  view on Meta::CPAN

This is an alias for C<variations>, documented above.


=head2 tuples_with_repetition(\@data, $k)

This is an alias for C<variations_with_repetition>, documented above.


=head2 combinations(\@data, $k)

The combinations of length C<$k> of C<@data> are all the sets of size C<$k> consisting of elements of C<@data>. For example, for C<@data = (1, 2, 3, 4)> and C<$k = 3>:

    (1, 2, 3)
    (1, 2, 4)
    (1, 3, 4)
    (2, 3, 4)

For this to make sense, C<$k> has to be less than or equal to the length of C<@data>.

The number of combinations of C<n> elements taken in groups of C<< 0 <= k <= n >> is:

    n choose k = n!/(k!*(n-k)!)


=head2 combinations_with_repetition(\@data, $k);

The combinations of length C<$k> of an array C<@data> are all the bags of size C<$k> consisting of elements of C<@data>, with repetitions. For example, for C<@data = (1, 2, 3)> and C<$k = 2>:

    (1, 1)
    (1, 2)
    (1, 3)
    (2, 2)
    (2, 3)
    (3, 3)

Note that C<$k> can be greater than the length of C<@data>. For example, for C<@data = (1, 2, 3)> and C<$k = 4>:

    (1, 1, 1, 1)
    (1, 1, 1, 2)
    (1, 1, 1, 3)
    (1, 1, 2, 2)
    (1, 1, 2, 3)
    (1, 1, 3, 3)
    (1, 2, 2, 2)
    (1, 2, 2, 3)
    (1, 2, 3, 3)

README  view on Meta::CPAN

        d(n) = n*d(n-1) + (-1)**n,      if n > 0

    See some values at http://www.research.att.com/~njas/sequences/A000166.

  complete_permutations(\@data)

    This is an alias for `derangements', documented above.

  variations(\@data, $k)

    The variations of length `$k' of `@data' are all the tuples of length
    `$k' consisting of elements of `@data'. For example, for `@data = (1, 2,
    3)' and `$k = 2':

        (1, 2)
        (1, 3)
        (2, 1)
        (2, 3)
        (3, 1)
        (3, 2)

    For this to make sense, `$k' has to be less than or equal to the length
    of `@data'.

    Note that

        permutations(\@data);

    is equivalent to

        variations(\@data, scalar @data);

    The number of variations of `n' elements taken in groups of `k' is:

        v(n, k) = 1,                        if k = 0
        v(n, k) = n*(n-1)*...*(n-k+1),      if 0 < k <= n

  variations_with_repetition(\@data, $k)

    The variations with repetition of length `$k' of `@data' are all the
    tuples of length `$k' consisting of elements of `@data', including
    repetitions. For example, for `@data = (1, 2, 3)' and `$k = 2':

        (1, 1)
        (1, 2)
        (1, 3)
        (2, 1)
        (2, 2)
        (2, 3)
        (3, 1)
        (3, 2)
        (3, 3)

    Note that `$k' can be greater than the length of `@data'. For example,
    for `@data = (1, 2)' and `$k = 3':

        (1, 1, 1)
        (1, 1, 2)
        (1, 2, 1)
        (1, 2, 2)
        (2, 1, 1)
        (2, 1, 2)
        (2, 2, 1)
        (2, 2, 2)

README  view on Meta::CPAN

  tuples(\@data, $k)

    This is an alias for `variations', documented above.

  tuples_with_repetition(\@data, $k)

    This is an alias for `variations_with_repetition', documented above.

  combinations(\@data, $k)

    The combinations of length `$k' of `@data' are all the sets of size `$k'
    consisting of elements of `@data'. For example, for `@data = (1, 2, 3,
    4)' and `$k = 3':

        (1, 2, 3)
        (1, 2, 4)
        (1, 3, 4)
        (2, 3, 4)

    For this to make sense, `$k' has to be less than or equal to the length
    of `@data'.

    The number of combinations of `n' elements taken in groups of `0 <= k <=
    n' is:

        n choose k = n!/(k!*(n-k)!)

  combinations_with_repetition(\@data, $k);

    The combinations of length `$k' of an array `@data' are all the bags of
    size `$k' consisting of elements of `@data', with repetitions. For
    example, for `@data = (1, 2, 3)' and `$k = 2':

        (1, 1)
        (1, 2)
        (1, 3)
        (2, 2)
        (2, 3)
        (3, 3)

    Note that `$k' can be greater than the length of `@data'. For example,
    for `@data = (1, 2, 3)' and `$k = 4':

        (1, 1, 1, 1)
        (1, 1, 1, 2)
        (1, 1, 1, 3)
        (1, 1, 2, 2)
        (1, 1, 2, 3)
        (1, 1, 3, 3)
        (1, 2, 2, 2)
        (1, 2, 2, 3)