in reply to Pure regex Hamiltonian Circuit solution
Here's an updated version using lookaheads to greatly shorten things. Matching time shouldn't change much.
There's no more need for repeating the listing of @all_edges so many times. With lookaheads, it only needs to be there once. Same with the listing of @E. This reduces $string to O(V^2).my @E = ([1,3],[1,5],[2,3],[2,4],[2,5],[4,5]); my $V = 5; my $verbose = 1; my @all_edges = map { my $x = $_; map { [$x, $_] } $x+1 .. $V } 1 .. $ +V-1; my $string = (join(' ', 1 .. $V) . "\n") x $V . join(' ', map { join "-", @$_ } @all_edges ) . "\n" . join(' ', map { join "-", @$_ } @E ); my $regex = "^\n" . ".* \\b (\\d+) \\b .* \\n\n" x $V . join("", map { my ($x, $y) = @$_; "(?= .* \\b (?: \\$x-\\$y | \\$y-\\$x ) \\b + ) \n" } @all_edges) . ".*\\n\n" . join("", map { my ($x, $y) = ($_, $_+1); "(?= .* \\b (?: \\$x-\\$y | \\$y-\\$x ) \\b + )\n" } 1 .. ($V-1)) . "(?= .* \\b (?: \\$V-\\1 | \\1-\\$V ) \\b )\n"; print "'$string' =~ /\n$regex\n/x\n" if $verbose; if (my @c = $string =~ /$regex/x) { local $" = " -> "; print "Hamiltonian circuit: [ @c -> $1 ]\n"; } else { print "No Hamiltonian circuit\n"; } __END__ $string = q[ 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1-2 1-3 1-4 1-5 2-3 2-4 2-5 3-4 3-5 4-5 1-3 1-5 2-3 2-4 2-5 4-5 ]; $regex = q[ ^ .* \b (\d+) \b .* \n .* \b (\d+) \b .* \n .* \b (\d+) \b .* \n .* \b (\d+) \b .* \n .* \b (\d+) \b .* \n (?= .* \b (?: \1-\2 | \2-\1 ) \b ) (?= .* \b (?: \1-\3 | \3-\1 ) \b ) (?= .* \b (?: \1-\4 | \4-\1 ) \b ) (?= .* \b (?: \1-\5 | \5-\1 ) \b ) (?= .* \b (?: \2-\3 | \3-\2 ) \b ) (?= .* \b (?: \2-\4 | \4-\2 ) \b ) (?= .* \b (?: \2-\5 | \5-\2 ) \b ) (?= .* \b (?: \3-\4 | \4-\3 ) \b ) (?= .* \b (?: \3-\5 | \5-\3 ) \b ) (?= .* \b (?: \4-\5 | \5-\4 ) \b ) .*\n (?= .* \b (?: \1-\2 | \2-\1 ) \b ) (?= .* \b (?: \2-\3 | \3-\2 ) \b ) (?= .* \b (?: \3-\4 | \4-\3 ) \b ) (?= .* \b (?: \4-\5 | \5-\4 ) \b ) (?= .* \b (?: \5-\1 | \1-\5 ) \b ) ];
Because backtracking doesn't happen within lookaheads, I couldn't use lookaheads to select the captured vertices. So the listing of vertices 1 to $V still has to be there $V times.
blokhead
|
---|
In Section
Meditations