I did not know where to turn so I'm looking up anyone who could offer an answer to this interesting problem.
I have a set of variables, listed as (A, B, C, D, E, F, G, H)
Each variable is couple in a set and can both be the same variable Example: (A/A, A/B, A/C, A/D etc...)
This makes 64 different combinations.
I am attempting to make a list of sets using a rule that will have the bottom half of the set (A/B) start the top half of the next set (B/C) And so on... (C/D, D/E, E/F)
The goal here is to have all 64 sets in this manner.
What is the order of all 64 combinations in order, using the rule described? I have been trying to figure this out for a long time and I don't know if it's even possible.
Thank you in advance. I hope you can help me with this seemingly impossible problem :)
Here is a hint: You are looking for an Eulerian path in the complete graph on 8 vertices. The set of vertices being $\{A,B,C,D,E,F,G,H\}$, and the edge from $x$ to $y$ being denoted $x/y$ by you.
(Actually, I may be misusing the term “complete graph” here, since your graph also contains all the loops $x/x$.)
Edit: On second thought, your graph is a directed graph, with two oppositely directed arrows between any two different vertices, and just one from a vertex to itself. This does change the picture a bit, but the notion of Eulerian path still applies.
Edit #2 (after reading the comments): Your graph has 8 vertices. Each vertex has indegree 8 and outdegree 8, meaning there are 8 incoming and 8 outgoing edges. Since these degrees match up, and the graph is strongly connected, there exists an Eulerian cycle.
A simple, though perhaps not very efficient, way to find one, is this: Start at any vertex. Travel along, always following a previously unused edge, until you can go no further. You will find you are back at the starting point. However, you may not have visited all edges yet. If so, pick a vertex in the cycle you just created which has an unused edge going out. (There must be one somewhere, by connectedness and the matching of in- and outdegrees.) Starting at this vertex, create a new cycle by the same procedure as the first one, avoiding all used edges including those from the first cycle. Again, you will be back where you started when you can go no longer. Join the two cycles into one. Repeat the procedure until all edges are included.
The above is a brief description of a standard construct in graph theory, found in many textbooks on the subject.
EDIT #3: Here is one solution.
Listing the nodes, in the order visited:
AABBCCDDEEFFGGHHADGBEHCFAFCHEBGDACEFAHBDFHDHGCGFBFEAECAGEDBHFDCBA
and listing the edges:
A/A A/B B/B B/C C/C C/D D/D D/E E/E E/F F/F F/G G/G G/H H/H H/A A/D D/G G/B B/E E/H H/C C/F F/A A/F F/C C/H H/E E/B B/G G/D D/A A/C C/E E/F F/A A/H H/B B/D D/F F/H H/D D/H H/G G/C C/G G/F F/B B/F F/E E/A A/E E/C C/A A/G G/E E/D D/B B/H H/F F/D D/C C/B B/A
Roughly speaking, the solution is worked out as follows:
No need for Fleury's algorithm.