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] ]);

    return __contextualize($iter);
}


sub permutations {
    my ($data) = @_;
    __check_params($data, 0);

    return __contextualize(__once_iter()) if @$data == 0;

    my @indices = 0..(@$data-1);
    my $iter = Algorithm::Combinatorics::Iterator->new(sub {
        __next_permutation(\@indices) == -1 ? undef : [ @{$data}[@indices] ];
    }, [ @{$data}[@indices] ]);

    return __contextualize($iter);
}


sub circular_permutations {
    my ($data) = @_;
    __check_params($data, 0);

    return __contextualize(__once_iter())         if @$data == 0;
    return __contextualize(__once_iter([@$data])) if @$data == 1 || @$data == 2;

    my @indices = 1..(@$data-1);
    my $iter = Algorithm::Combinatorics::Iterator->new(sub {
        __next_permutation(\@indices) == -1 ? undef : [ @{$data}[0, @indices] ];
    }, [ @{$data}[0, @indices] ]);

    return __contextualize($iter);
}

sub __permutations_heap {
    my ($data) = @_;
    __check_params($data, 0);

    return __contextualize(__once_iter()) if @$data == 0;

    my @a = 0..(@$data-1);
    my @c = (0) x (@$data+1); # yeah, there's an spurious $c[0] to make the notation coincide
    my $iter = Algorithm::Combinatorics::Iterator->new(sub {
        __next_permutation_heap(\@a, \@c) == -1 ? undef : [ @{$data}[@a] ];
    }, [ @{$data}[@a] ]);

    return __contextualize($iter);
}


sub derangements {
    my ($data) = @_;
    __check_params($data, 0);

    return __contextualize(__once_iter()) if @$data == 0;
    return __contextualize(__null_iter()) if @$data == 1;

    my @indices = 0..(@$data-1);
    @indices[$_, $_+1] = @indices[$_+1, $_] for map { 2*$_ } 0..((@$data-2)/2);
    @indices[-1, -2] = @indices[-2, -1] if @$data % 2;
    my $iter = Algorithm::Combinatorics::Iterator->new(sub {
        __next_derangement(\@indices) == -1 ? undef : [ @{$data}[@indices] ];
    }, [ @{$data}[@indices] ]);

    return __contextualize($iter);
}

*complete_permutations = \&derangements;


sub partitions {
    my ($data, $k) = @_;
    if (defined $k) {
        __partitions_of_size_p($data, $k);
    } else {
        __partitions_of_all_sizes($data);
    }
}

sub __partitions_of_all_sizes {
    my ($data) = @_;
    __check_params($data, 0);

    return __contextualize(__once_iter()) if @$data == 0;

    my @k = (0) x @$data;
    my @M = (0) x @$data;
    my $iter = Algorithm::Combinatorics::Iterator->new(sub {
       __next_partition(\@k, \@M) == -1 ? undef : __slice_partition(\@k, \@M, $data);
    }, __slice_partition(\@k, \@M, $data));

    return __contextualize($iter);
}

# We use @k and $p here and sacrifice the uniform usage of $k
# to follow the notation in [3].
sub __partitions_of_size_p {
    my ($data, $p) = @_;
    __check_params($data, $p);

    return __contextualize(__null_iter()) if $p < 0;
    return __contextualize(__once_iter()) if @$data == 0 && $p == 0;