# ======================================================================================
# Count Simple Paths from one vertex to the oposite vertex of an n-dimensional hypercube
# --------------------------------------------------------------------------------------
P:=proc(n)
global count,E; # count to enummerate simple paths, E for the ending vertex
local S; # S for the starting vertex
count:=0; # initiate counter at zero
S:=[seq(0,i=1..n)]; # define the starting vertex
E:=[seq(1,i=1..n)]; # define the ending vertex
traverse(n,S,[]); # call procedure to traverse the graph from this vertex
count; # return the number of simple paths
end proc:
# =========================================================================
# Recursive procedure to traverse an n-cube graph to count all simple paths
# -------------------------------------------------------------------------
traverse:=proc(n,vertex,list)
global count,E;
local i,V,L;
V:=vertex;
L:=[op(1..nops(list),list),V]; # add vertex to list so it is not revisited
for i from 1 to n do # try all n directions systematically
V[i]:=1-V[i]; # move to next vertex in the ith dimension
if member(V,L) then # was vertex already visited on this path?
V[i]:=1-V[i]; # if yes, return to the previous vertex
next; # then try the next direction
elif V=E then # if new vertex, is it the end vertex?
count:=count+1; # if yes, increment the counter
V[i]:=1-V[i]; # and return to the previous vertex
next; # then try the next direction
else # otherwise this is a new vertex
traverse(n,V,L); # then recurse to continue from there
V[i]:=1-V[i]; # and return to the previous vertex
end if;
end do;
end proc:
Hayate wrote:Stack overflows can easily be fixed by removing recursion and making your own stack.
Could you rewrite that as some form of pseudocode, by any chance?
I think group theory is important here, my main 'evidence' for this is that #paths for a tesseract = 4!×268, and 267 is the number of groups of order 64. I have yet to justify this, or extrapolate
Hayate wrote:Hmmm... a comment from a friend:...
zero wrote:For n dimensions in general, the number of possible lengths is 2n+(1/4)*(-1)n-(1/2)*n-1/4
Mucleus wrote:Perhaps it is for (n+1) dimensions in general
zero wrote:I've been running something similar (which also keeps track of how many paths are of a given length), and will keep it going until there's an answer -- or until the power goes out for longer than my battery backup can handle, whichever comes first. There are literally millions of simple paths from one vertex to the opposite one for a 5-cube, so this could take some time.
Hi.. I am interested in this, but i'm having a problem in converting the maple code to C++ code. Can someone please help? I'm new here but am really interested in this problem.
zero wrote:L=4, N=24
L=6, N=96
L=8, N=456
L=10, N=1584
L=12, N=2640
L=14, N=1632
Hayate wrote:An upper bound on the number of possible simple paths in a penteract is 2^(2^5), or 2^32.
That bound appears to be exceeded even if we are counting only the possible simple paths that are of lengths 23,25,27,29, and 31.
Hayate wrote:zero wrote:L=4, N=24
L=6, N=96
L=8, N=456
L=10, N=1584
L=12, N=2640
L=14, N=1632
Mucleus and I have discovered these numbers are incorrect...
Hayate wrote:That bound appears to be exceeded even if we are counting only the possible simple paths that are of lengths 23,25,27,29, and 31.
How did you calculate that?
Return to Where Should I Post This?
Users browsing this forum: No registered users and 1 guest