Number of simple paths in a Tesseract

If you don't know where to post something, put it here and an administrator or moderator will move it to the right place.

Number of simple paths in a Tesseract

Postby Darez » Thu Mar 20, 2008 5:27 am

Hi everybody,

Can somebody help me on this?

If let's say we are interested to find out the number of simple paths from (0,0,0,0) to (1,1,1,1) in a tesseract, how should we go about doing it?

Hope that you guys can help me on this...

A million thanks!

Cheers
Darez
Darez
Mononian
 
Posts: 4
Joined: Thu Mar 20, 2008 5:24 am

Re: Number of simple paths in a Tesseract

Postby wendy » Fri Mar 21, 2008 5:33 am

The path from 0,0,0,0 to 1,1,1,1 involve. in any order 0001, 0010, 0100, and 1000.

We can then take any of these four, followed by any of the remaining three, by any of the remaining two, and then the last one, so 4*3*2*1 = 24.

For a penteract there is 100 of vi score, that is, 120 or 5*4*3*2*1
The dream you dream alone is only a dream
the dream we dream together is reality.

\ ( \(\LaTeX\ \) \ ) [no spaces] at https://greasyfork.org/en/users/188714-wendy-krieger
User avatar
wendy
Pentonian
 
Posts: 2014
Joined: Tue Jan 18, 2005 12:42 pm
Location: Brisbane, Australia

Re: Number of simple paths in a Tesseract

Postby zero » Fri Mar 21, 2008 10:53 am

Actually, it turns out to be a bit more complicated when you give this a closer look. The factorial answer occurred to me also, but then I realized that counts only the shortest paths. Simple paths do not have to be shortest paths; they can wander all around, provided they don't reuse a vertex.

If we let P(n) represent the number of simple paths from one "corner" to the opposite one in a hypercube of dimension n, then it's obvious that P(1)=1 and P(2)=2.

However, the number jumps considerably for three dimensions. By inspection, we can see that P(3)=18. All the cases are listed below:

[0,0,0]->[1,0,0]->[1,1,0]->[0,1,0]->[0,1,1]->[1,1,1]
[0,0,0]->[1,0,0]->[1,1,0]->[0,1,0]->[0,1,1]->[0,0,1]->[1,0,1]->[1,1,1]
[0,0,0]->[1,0,0]->[1,1,0]->[1,1,1]
[0,0,0]->[1,0,0]->[1,0,1]->[0,0,1]->[0,1,1]->[1,1,1]
[0,0,0]->[1,0,0]->[1,0,1]->[0,0,1]->[0,1,1]->[0,1,0]->[1,1,0]->[1,1,1]
[0,0,0]->[1,0,0]->[1,0,1]->[1,1,1]
[0,0,0]->[0,1,0]->[1,1,0]->[1,0,0]->[1,0,1]->[0,0,1]->[0,1,1]->[1,1,1]
[0,0,0]->[0,1,0]->[0,1,1]->[0,0,1]->[1,0,1]->[1,1,1]
[0,0,0]->[0,1,0]->[1,1,0]->[1,1,1]
[0,0,0]->[0,1,0]->[0,1,1]->[1,1,1]
[0,0,0]->[0,1,0]->[1,1,0]->[1,0,0]->[1,0,1]->[1,1,1]
[0,0,0]->[0,1,0]->[0,1,1]->[0,0,1]->[1,0,1]->[1,0,0]->[1,1,0]->[1,1,1]
[0,0,0]->[0,0,1]->[1,0,1]->[1,1,1]
[0,0,0]->[0,0,1]->[1,0,1]->[1,0,0]->[1,1,0]->[0,1,0]->[0,1,1]->[1,1,1]
[0,0,0]->[0,0,1]->[1,0,1]->[1,0,0]->[1,1,0]->[1,1,1]
[0,0,0]->[0,0,1]->[0,1,1]->[1,1,1]
[0,0,0]->[0,0,1]->[0,1,1]->[0,1,0]->[1,1,0]->[1,0,0]->[1,0,1]->[1,1,1]
[0,0,0]->[0,0,1]->[0,1,1]->[0,1,0]->[1,1,0]->[1,1,1]

I do not know the answer for P(4), and am not going to bother inspecting it by hand, as I suspect the number is rather large. This is what computer programs were made for, as there's definitely a nice pattern here. It shouldn't be too difficult to create a recursive procedure to traverse the possibilities and count the number of paths for n dimensions in general. With that data available, one might even hazard a guess at a theorem.
zero
Trionian
 
Posts: 139
Joined: Wed Nov 07, 2007 5:45 am
Location: Florida

Re: Number of simple paths in a Tesseract

Postby Darez » Sat Mar 22, 2008 1:38 am

Hi Zero,

Is there any computer program that you can recommend so that I can use it to get an answer?

If there is indeed one, do you mind to share with me the programming code?

It's urgent! Hope you can help me on this.

Thanks!!!

Cheers
Darez
Darez
Mononian
 
Posts: 4
Joined: Thu Mar 20, 2008 5:24 am

Re: Number of simple paths in a Tesseract

Postby zero » Sat Mar 22, 2008 8:58 pm

Why so urgent?

I really don't know enough to make the best program recommendation for you. Not only do I lack comprehensive information about such programs, I haven't a clue what your skill level is. Do you program? If so, in what languages?

Anyway, I may be able to help. For a class, I'm learning to use Maple (which is designed for symbolic manipulation and math in general), so I'll see if I can implement this, because it's an interesting question.
zero
Trionian
 
Posts: 139
Joined: Wed Nov 07, 2007 5:45 am
Location: Florida

Re: Number of simple paths in a Tesseract

Postby zero » Sun Mar 23, 2008 1:18 am

Wow!

I was right -- it's a much larger number of simple paths from [0,0,0,0] to [1,1,1,1] on a tesseract than I would want to do by hand (as above for a cube). Now checking to see how many there are for a 5-cube, but it's taking a long time (over twenty minutes already) with no clue how much longer it has to finish counting. I didn't think the numbers would grow so large that it would take that long to compute, or else I would have paid more attention to efficiency when writing the Maple procedure. Oh, well. I'll let it run just to see how long it takes and to get the number to impress random strangers with. Assuming it finishes overnight.

The Maple code could be easily modified to print out all of the simple paths if you like, but that would be crazy when there are over six thousand.

What is this for, anyway? I don't exactly want to do someone's homework for them. On the other hand, anyone who shows the initiative to go looking for help deserves it, especially when bringing an interesting problem to the table. Anyway, for whoever is interested, here's what I cooked up to solve it:

Code: Select all
# ======================================================================================
# 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:

Then P(1)=1, P(2)=2, and P(3)=18 just as previously determined by hand. It was quick to give a result for P(4), so there you go -- but unless you have a lot of patience or some serious computing power handy, I don't recommend trying this to get P(n) for n greater than 4.
zero
Trionian
 
Posts: 139
Joined: Wed Nov 07, 2007 5:45 am
Location: Florida

Re: Number of simple paths in a Tesseract

Postby zero » Mon Mar 24, 2008 4:33 am

My computer experienced a stack overflow, so I still don't know the value of P(5).

There's even a listing in Sloane's On-Line Encyclopedia of Integer Sequences, but it contains only the first four entries of this infinite sequence. Now I am even more motivated to see what comes next!
zero
Trionian
 
Posts: 139
Joined: Wed Nov 07, 2007 5:45 am
Location: Florida

Re: Number of simple paths in a Tesseract

Postby Keiji » Mon Mar 24, 2008 10:35 pm

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 don't understand Maple whatsoever, but I'm now pretty interested, and I could take a crack at it in Python if I understood the algorithm.
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Number of simple paths in a Tesseract

Postby zero » Tue Mar 25, 2008 4:37 am

Hayate wrote:Stack overflows can easily be fixed by removing recursion and making your own stack.

That sounds too much like real work.

Could you rewrite that as some form of pseudocode, by any chance?


How's this?

BEGIN PROGRAM
define S = [ 0, 0, 0, . . . , 0 ] -- zero repeated n times
define E = [ 1, 1, 1, . . . , 1 ] -- one repeated n times
call the subroutine, passing the values n, S, and an empty list
print the value of the count variable which has been incremented in the subroutine
END PROGRAM

BEGIN SUBROUTINE
(values passed from the calling program are n, vertex, and list)
assign V = vertex
assign L = list with V appended to it
for k = 1 to n do the following loop
. assign Vk = 1 - Vk -- in other words, change the kth coordinate of V from 0 to 1 or vice versa
. if V is an element of L then
. . assign Vk = 1 - Vk -- change the coordinate back, because we've already been here
. . go to the next value of k
. else
. . if V = E then
. . . count = count+1
. . . assign Vk = 1 - Vk
. . . go to the next value of k
. . else
. . . call the subroutine recursively, passing the values n, V, and L
. . . assign Vk = 1 - Vk
. . end if
. end if
end do loop
END SUBROUTINE
zero
Trionian
 
Posts: 139
Joined: Wed Nov 07, 2007 5:45 am
Location: Florida

Re: Number of simple paths in a Tesseract

Postby Darez » Tue Mar 25, 2008 4:50 am

Hi Zero,

Ok, so you mean I just type the following program on Maple window?

P:=proc(n)
global count,E;
local S;
count:=0;
S:=[seq(0,i=1..4)];
E:=[seq(1,i=1..4)];
traverse(n,S,[]);
count;
end proc:

Will this do? I mean P(4) will thus be generated???

Hey thanks bro!!! Nah, this isn't my homework... Just part of my research...

Cheers
Darez
Darez
Mononian
 
Posts: 4
Joined: Thu Mar 20, 2008 5:24 am

Re: Number of simple paths in a Tesseract

Postby Darez » Tue Mar 25, 2008 5:03 am

Hmm sorry,

Typo, I mean the program should be like the following right?

P:=proc(4)
global count,E;
local S;
count:=0;
S:=[seq(0,i=1..4)];
E:=[seq(1,i=1..4)];
traverse(4,S,[]);
count;
end proc:

Cheers
Darez
Darez
Mononian
 
Posts: 4
Joined: Thu Mar 20, 2008 5:24 am

Re: Number of simple paths in a Tesseract

Postby zero » Tue Mar 25, 2008 6:25 am

You could copy and paste all the code (which include two routines and comments, not that the comments do anything) exactly as-is into Maple, then execute them and simply type P(4); to generate the result. Alternately, you can find it as part of integer sequence A059783 on Sloane's.

Intuitively, I feel that there's a much easier way to program this, and I'll probably play with it some more when i have time next week.
zero
Trionian
 
Posts: 139
Joined: Wed Nov 07, 2007 5:45 am
Location: Florida

Re: Number of simple paths in a Tesseract

Postby Keiji » Tue Mar 25, 2008 1:00 pm

Okay, I ported the algorithm to Python. Here it is:

http://teamikaria.com/dl/HFXKUeT4KCDf92 ... gMNsw1q2IR

If you just run that, it'll calculate P(5) with the stack-optimized function which is called sub2; the ordinary function is called sub.

The first three functions are only there because Python assigns and compares lists based on their references, not their values.
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Number of simple paths in a Tesseract

Postby Keiji » Tue Mar 25, 2008 7:52 pm

Hmmm... a comment from a friend:

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


Now, I know nothing about group theory, but does this conclusion help?
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Number of simple paths in a Tesseract

Postby zero » Fri Mar 28, 2008 7:29 am

Thanks, I'll try that later. I just looked at this again today. As for group theory, it touches on a lot of things, so it could be related somehow -- I just don't see an obvious connection right offhand. The following leads me to think there should be a way to use symmetry considerations to substantially improve the efficiency of any algorithm, especially as n increases.

If we let L be the length of a simple path from (0,0,0) to (1,1,1), then the number N of simple paths with length L are:

L=3, N=6
L=5, N=6
L=7, N=6

If we let L be the length of a simple path from (0,0,0,0) to (1,1,1,1), then the number N of simple paths with length L are:

L=4, N=24
L=6, N=96
L=8, N=456
L=10, N=1584
L=12, N=2640
L=14, N=1632

For 5 dimensions, there will be 14 possible lengths, and I'm guessing that 5! will divide the number of each. For n dimensions in general, the number of possible lengths is 2n+(1/4)*(-1)n-(1/2)*n-1/4 and my guess is that n! will divide the number of simple paths for each length.
zero
Trionian
 
Posts: 139
Joined: Wed Nov 07, 2007 5:45 am
Location: Florida

Re: Number of simple paths in a Tesseract

Postby Mucleus » Fri Mar 28, 2008 7:47 pm

n! must divide the number of paths of a certain length, because if we have a path, we can permute the axes in n! ways to get a new path of the same form. For example:
0001-0011-0010-0110-0111-1111 is the same as 0010-0011-0001-1001-1011-1111 (swapping columns 1 and 2, 3 and 4). This cannot give duplications, because if swapping two columns had no effect, there would have to be a jump from k 1s to (k+2) 1s (since each row is the same) which cannot happen.

NB. This:
Hayate wrote:Hmmm... a comment from a friend:...

is me :D

I'm less confident now about the group theory, or at least the # groups order 64. It would be more reasonable to expect that some crazy group's cardinality is what we want :\
Mucleus
Mononian
 
Posts: 6
Joined: Fri Mar 28, 2008 7:29 pm

Re: Number of simple paths in a Tesseract

Postby Keiji » Fri Mar 28, 2008 11:09 pm

zero wrote:For n dimensions in general, the number of possible lengths is 2n+(1/4)*(-1)n-(1/2)*n-1/4


Well, that formula is most certainly wrong: n = 3 gives 6 and n = 4 gives 14.
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Number of simple paths in a Tesseract

Postby Mucleus » Sat Mar 29, 2008 2:33 pm

Perhaps it is for (n+1) dimensions in general :)

Anyway, we can further divide the subsets of equal-length paths into the pattern of 1s they make (partly shown below for 4d)
Length 4:
Type 01234: 0000-0001-0011-0111-1111 = 1 type => 24
Total 24
Length 6:
Type 0121234: 0000-0001-0011-0010-0110-0111-1111; 0000-0001-0011-0010-0110-1110-1111 = 2 types => 48
Type 0123234: 0000-0001-0011-0111-0101-1101-1111; 0000-0001-0011-0111-0110-1110-1111 = 2 types => 48
Total 96
And so on.
Mucleus
Mononian
 
Posts: 6
Joined: Fri Mar 28, 2008 7:29 pm

Re: Number of simple paths in a Tesseract

Postby zero » Sun Mar 30, 2008 5:03 am

Mucleus wrote:Perhaps it is for (n+1) dimensions in general :)

Yes, that is the necessary correction.
zero
Trionian
 
Posts: 139
Joined: Wed Nov 07, 2007 5:45 am
Location: Florida

Re: Number of simple paths in a Tesseract

Postby Keiji » Sun Mar 30, 2008 10:38 pm

Well, my program has been running for a little over 47 hours now trying to calculate the number of simple paths in a penteract of each length...

If it doesn't finish by 8:30 AM GMT tomorrow, I'll have to abandon it until next week due to a combination of school, parents and their paranoia (go figure).
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Number of simple paths in a Tesseract

Postby zero » Sun Mar 30, 2008 11:25 pm

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.
zero
Trionian
 
Posts: 139
Joined: Wed Nov 07, 2007 5:45 am
Location: Florida

Re: Number of simple paths in a Tesseract

Postby percussgal » Mon Mar 31, 2008 3:47 am

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.
percussgal
Nullonian
 
Posts: 1
Joined: Mon Mar 31, 2008 3:40 am

Re: Number of simple paths in a Tesseract

Postby Keiji » Mon Mar 31, 2008 6:10 am

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.


An upper bound on the number of possible simple paths in a penteract is 2^(2^5), or 2^32. That number is how I calculated it would take a maximum of eight days to finish, and given that the actual number for the cube and tesseract is far lower than the maximum, I educatedly guessed it would take about two days. What I didn't think of at the time is that the time taken to check whether a simple path exists for a penteract is higher than that for a tesseract, as the "is V in L" test (which is executed several times per path) would take longer because L would be longer.

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.


C++ isn't really suited to this kind of thing due to not having such built-in data types like Maple and indeed Python, hence why I wrote it in Python. It would certainly be a lot harder and take a lot more code to write it in C++... I guess it'd be a bit faster, though.
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Number of simple paths in a Tesseract

Postby Keiji » Wed Apr 02, 2008 9:41 am

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...

However, in doing so, I think I have found a new, much faster, algorithm to calculate the numbers. I'll write another Python script as soon as I get home today and see if it works. If it does, I'll post it, of course. :)

Edit: Wut?

I ran the original program again, and got those supposedly incorrect numbers. But I can't find a flaw in what we were proposing either, about the different possible structures of the paths (there are four groups for length 8: 012121234, 012323234, 012123234 and 012321234; the first three have four possibilities and the last has eight, giving 20, not 19). Something's weird here. Perhaps the last one should have seven. I'll write the new program anyway and see if it eliminates that mysterious extraneous one.
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Number of simple paths in a Tesseract

Postby Keiji » Wed Apr 02, 2008 3:12 pm

Okay, the calculation finished, taking 662.80 seconds to complete on my computer. The current lower bound for the number of simple paths in a penteract is 514,228*5! = 61,707,360, assuming that there is at least one set of 5! paths in each shape. Here's the current version of the program, which will calculate all possible shapes in all possible lengths for dimension n if you run ./simplepaths.py n.
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Number of simple paths in a Tesseract

Postby zero » Thu Apr 03, 2008 3:30 am

Hayate wrote:An upper bound on the number of possible simple paths in a penteract is 2^(2^5), or 2^32.

I do not understand how that was determined to be an upper bound for this problem. 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.
zero
Trionian
 
Posts: 139
Joined: Wed Nov 07, 2007 5:45 am
Location: Florida

Re: Number of simple paths in a Tesseract

Postby Keiji » Thu Apr 03, 2008 3:38 am

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?

I don't recall why it was an upper bound; Mucleus determined it, not me. Ask him =p
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Number of simple paths in a Tesseract

Postby zero » Thu Apr 03, 2008 3:46 am

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...

I can easily produce a file with these 6432 possible outcomes, actually generating a list of all the simple paths from (0,0,0,0) to (1,1,1,1).

That way, if you're still obtaining different numbers than the above (for n=4 in this general problem of counting the number of simple paths from one vertex of an n-cube to the opposite vertex), then it could be worthwhile to double check which results are accurate.
Last edited by zero on Thu Apr 03, 2008 4:04 am, edited 1 time in total.
zero
Trionian
 
Posts: 139
Joined: Wed Nov 07, 2007 5:45 am
Location: Florida

Re: Number of simple paths in a Tesseract

Postby zero » Thu Apr 03, 2008 4:02 am

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?

It's a partial result for the streamlined program I'm currently running (with n set equal to 5). The accumulated count of simple paths between opposite vertices is growing at about 200 million per hour. The count is already past 5.32 * 10^9 and with symmetry considerations, we're looking at a final answer of over six times this number. I did not expect such a large result.
zero
Trionian
 
Posts: 139
Joined: Wed Nov 07, 2007 5:45 am
Location: Florida

Re: Number of simple paths in a Tesseract

Postby Keiji » Thu Apr 03, 2008 6:15 pm

Well, we've calculated a new upper bound which is around 2.15x10<sup>22</sup>. This one is actually correct - it is the sum of nCr for n=80 (the number of edges in a penteract) and r=5,7,9,...,31.

I am positive there should be 20 sets for the tesseract, so I shall continue updating the script to generate these sets and see what happens.
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Next

Return to Where Should I Post This?

Who is online

Users browsing this forum: No registered users and 8 guests

cron