#!/usr/bin/perl -w
#
#  "Loop Abstraction Via Recursion"
#
#   060111 by liverpole
#

# Strict
use strict;
use warnings;


# User-defined
my @list    = qw( 1 2 3 4 5 );

# Prototypes
sub abstract_loop($$$);
sub arbitrary_N_loops($;$$);
sub show_results($$$);


# Globals
my $N;                  # The number of loops (which we want to abstract)
my $total;              # Total match attempts
my $pvals = [ ];        # The list of values
my $nmatch = 0;         # Total matches


# Subroutines
sub match(@) {
    my ($plist) = @_;
    my $sum = 0;
    my $prod = 1;
    map { $prod *= $_; $sum += $_ } @$plist;
    my $div = ($prod / $sum);
    ($div == int($div));
}


sub show_results($$$) {
    my ($nloops, $nmatch, $total) = @_;
    my $pct = ($total)? int(1000 * $nmatch / $total) / 10: 0;
    my $s = (1 == $nloops)? " ": "s";
    printf "[%3d loop$s]  ", $nloops;
    printf "Matches:  %8d / %9d ", $nmatch, $total;
    printf "(%5.1f%%)\n", $pct;
}


# Main program

# One loop
$N = 1;
$nmatch = $total = 0;
foreach (@list) {
    push @$pvals, $_;               # Add a new value to the list
    match($pvals) and ++$nmatch;    # Check if it matches the criteria
    ++$total;                       # Add 1 to the total count
    pop @$pvals;                    # Remove the value at the end
}
show_results($N, $nmatch, $total);


##</code><code>##

[  1 loop ]  Matches:         5 /         5 (100.0%)

##</code><code>##

# Two loops
$N = 2;
$nmatch = $total = 0;
foreach (@list) {
    push @$pvals, $_;
    foreach (@list) {
        push @$pvals, $_;
        match($pvals) and ++$nmatch;
        ++$total;
        pop @$pvals;
    }
    pop @$pvals;
}
show_results($N, $nmatch, $total)

##</code><code>##

[  1 loop ]  Matches:         5 /         5 (100.0%)
[  2 loops]  Matches:         2 /        25 (  8.0%)

##</code><code>##


# Three loops
$N = 3;
$nmatch = $total = 0;
foreach (@list) {
    push @$pvals, $_;
    foreach (@list) {
        push @$pvals, $_;
        foreach (@list) {
            push @$pvals, $_;
            match($pvals) and ++$nmatch;
            ++$total;
            pop @$pvals;
        }
        pop @$pvals;
    }
    pop @$pvals;
}
show_results($N, $nmatch, $total);

##</code><code>##

# Four loops
$N = 4;
$nmatch = $total = 0;
foreach (@list) {
    push @$pvals, $_;
    foreach (@list) {
        push @$pvals, $_;
        foreach (@list) {
            push @$pvals, $_;
            foreach (@list) {
                push @$pvals, $_;
                match($pvals) and ++$nmatch;
                ++$total;
                pop @$pvals;
            }
            pop @$pvals;
        }
        pop @$pvals;
    }
    pop @$pvals;
}
show_results($N, $nmatch, $total);

##</code><code>##

[  1 loop ]  Matches:         5 /         5 (100.0%)
[  2 loops]  Matches:         2 /        25 (  8.0%)
[  3 loops]  Matches:        28 /       125 ( 22.4%)
[  4 loops]  Matches:       110 /       625 ( 17.6%)

##</code><code>##

sub abstract_loop($$$) {
    my ($N, $plevel, $pvals) = @_;
    foreach (@list) {
        push @$pvals, $_;
        arbitrary_N_loops($N, $plevel, $pvals);
        pop @$pvals;
    }
}


sub arbitrary_N_loops($;$$) {
    my ($N, $plevel, $pvals) = @_;

    # Check level
    my $level = (!defined($plevel))? 1: $$plevel + 1;
    
    # Initialization (Called once at the beginning of all loops)
    if (1 == $level) {
        $pvals = [ ];
        $nmatch = $total = 0;
    }

    # Call loop N times
    if ($level <= $N) {
        &abstract_loop($N, \$level, $pvals);
    } else {
        # This block only happens within the innermost loop
        match($pvals) and ++$nmatch;
        ++$total;
    }

    # Finalization (Called once at the end of all loops)
    if (0 == --$level) {
        show_results($N, $nmatch, $total);
    }
}

arbitrary_N_loops(1);
arbitrary_N_loops(2);
arbitrary_N_loops(3);
arbitrary_N_loops(4);
arbitrary_N_loops(5);
arbitrary_N_loops(6);
arbitrary_N_loops(7);
arbitrary_N_loops(8);


##</code><code>##

[  1 loop ]  Matches:         5 /         5 (100.0%)
[  2 loops]  Matches:         2 /        25 (  8.0%)
[  3 loops]  Matches:        28 /       125 ( 22.4%)
[  4 loops]  Matches:       110 /       625 ( 17.6%)
-------------------------------------------------------------------------------

[  1 loop ]  Matches:         5 /         5 (100.0%)
[  2 loops]  Matches:         2 /        25 (  8.0%)
[  3 loops]  Matches:        28 /       125 ( 22.4%)
[  4 loops]  Matches:       110 /       625 ( 17.6%)
[  5 loops]  Matches:       681 /      3125 ( 21.7%)
[  6 loops]  Matches:      3615 /     15625 ( 23.1%)
[  7 loops]  Matches:     18550 /     78125 ( 23.7%)
[  8 loops]  Matches:     92598 /    390625 ( 23.7%)