Finding an algorithm for all combinations

Question

I need an answer on a question Im confronted writing a program. So I recently askend on Stackoverflow but I hope to get some better results from the mathematics site.

I need to go through an array of objects with n entries. I need to check almost every combination. Lets say the lists contains $\lbrace 0,1,2,3 \rbrace$ (Im matching the objects values to their index here for explenation). We fix the first one. This is the start value for all combinations. From 0 we choose one of the three objects left. This gives $n! = 4!$ combinations but we consider the combinations $0 - 1 - 2 - 3$ and $0 - 3 - 2 - 1$ to be the same because their last $(n-1)$ digits are the same in reverse order. With that the combination $0 - 2 - 1 - 3$ and $0 - 3 - 1 - 2$ give the same result and I dont have to look at both of them.

Do you know an effective way of getting an algorithm which gives me the $j$-th combination for j out of $1,...,\dfrac{(n-1)!}{2}$ ?

It seems to be pretty similiar to the travelling salesman problem where you have a starting point $0$ and have to visit all the other places. This way you might understand a little bit better how $0 - 1 - 2 - 3$ and $0 - 3 - 2 - 1$ are giving the same result. Its just like going around the other way.

Answer 1

I am interpreting your question to indicate that you want a math algorithm that you can code into a computer program. I would do this as follows:
1. construing the element-0 as home base, you have (n-1) choices for the element-1. Once element-1 has been chosen, you then have (n-2) choices for element-2. Continuing, you will generate (n-1)! candidate sequences.
2. every time that you generate a candidate sequence you check whether the reverse of that sequence has already been added to your list of sequences. If so, discard the candidate sequence. If not, add the candidate sequence to your list of sequences.

This will result in your list having (n-1)!/2 rather than (n-1)! sequences.

Please provide comment if I have misunderstood your question.

Answer 2

If I understand your question correctly, it seems you want to generate all Hamiltonian cycles in a complete undirected graph with $n$ vertices. The number of different cycles is, as you say, $\frac{(n-1)!}{2}$.

An efficient way to do this is described in the answer here.

First, find an algorithm which generates permutations sequentially. An example is algorithm $2$ here.

Second, starting with the list $\{2,3,\ldots , n \}$ (the first element $1$ is fixed) generate permutations of this list. If the first element of that permutation is larger than the last element, discard it, otherwise keep it.

And you're done.

This algorithm will check less than $(n-1)!$ permutations.