#!/usr/bin/perl

use strict vars;

# What I want is an answer to the question, how many possible
#  loops can be formed of a set of dominoes with ends numbered
#  to k. For example for k = 3, the dominoes are:
#   1-1, 1-2, 1-3, 2-2, 2-3, 3-3
# The x-x dominoes can be eliminated since they have no effect
#  on a loop, leaving:
#   1-2, 1-3, 2-3

# In general, |D| = k * (k - 1) / 2 (Each element (k) is
#  connected to all the others (k - 1) and each edge is
#  duplicated twice

my $k = ($#ARGV >= 0 ? $ARGV[0] : 5);
my $card = $k * ($k - 1) / 2;

# This number can be generated by brute force relatively easily.
# Just start walking the graph and keeping track and counting
#  valid loops.
# To make sure that loops are not duplicated, start each loop
#  with 1-2. This will both specify a location in the loop and
#  a direction. Since an edge may only be used once this means
#  each combination will be unique.

# Loops only exist for sets where k is odd.

die "k must be odd ($k is not)\n" if($k % 2 != 1 || int($k) != $k);

# Create a structure to track where we've been

my $i, my $j;

my @visited;
for($i = 1, $j = i; $i <= $k; $i++) {
    for($j = 1; $j <= $k; $j++) {
        $visited[$i][$j] = 0;
    }
}

# Eliminate x-x dominoes

for($i = 1; $i <= $k; $i++) {
    $visited[$i][$i] = true;
}

# Start with 1-2

$visited[1][2] = $visited[2][1] = true;

sub print_matrix() {
    print("   ");
    for($i = 1; $i <= @visited; $i++) {
        printf("%-5d ", $i);
    }
    print("\n");
    
    for($i = 1; $i <= $#visited; $i++) {
        printf("%-2d ", $i);
        for($j = 1; $j <= $k; $j++) {
            print(($visited[$i][$j] ? "true  " : "false "));
        }
        print("\n");
    }
}

my $loop_count = 0;
my @path = (1);
my @counts;

check_location(2);

print("Total loops: $loop_count\n");

for($i = 0; $i <= $#counts; $i++) {
    printf("%2d: ", $i + 1);
    for($j = 1; $j <= $#{@counts[$i]}; $j++) {
        if($counts[$i][$j] > 0) {
            printf("%2d (%2d) ", $j, $counts[$i][$j]);
        } else {
            print("        ");
        }
    }
    print("\n");
}

sub check_location() {
    my $current_node = shift @_;
    if($#path == $card - 1) {
        $loop_count++;
        for($i = 0; $i <= $#path; $i++) {
            $counts[$i][$path[$i]]++;
        }
        if(0) {
            printf("Found %04d: ", $loop_count);
            print("$_-") foreach(@path);
            print("$current_node\n");
        }
    } else {
        push(@path, $current_node);
        for(my $i = 1; $i <= $k; $i++) {
            if(!$visited[$current_node][$i]) {
                $visited[$current_node][$i] = $visited[$i][$current_node] = true;
                check_location($i);
                $visited[$current_node][$i] = $visited[$i][$current_node] = 0;
            }
        }
        pop(@path);
    }
}