# Algorithm for Low Discrepancy Sequence of Hamilton Cycles in Complete Graphs

Are there deterministic algorithms that generate a sequence of Hamilton Tours that is superior to a sequence of randomly chosen tours, when applied to the TSP (by applying to the TSP, I understand summing up a tour's edge weights)?

Whether Low Discrepancy is better that Random Generation is decided via the index of the Optimal Tour in the Low Discrepancy sequence of all tours.
If it is more likely to encounter the Optimal Tour in the Low Discrepancy sequence earlier than in the Random Generation sequence, then Low Discrepancy is conidered superior.
That measure of superiority is only one concrete example; other ways of defining it are also possible, while eventually yielding a different decision.

Background of my question is to learn whether similar improvements as in multidimensional integration are possible when switching from Monte Carlo to Low Discrepancy.
Note however, that multidimensional integration only serves as an example for the beneficial use of Low Discrepancy but is otherwise considered as being completely unrelated to TSP

I also appreciate any further information as well, like how to define a discrepancy measure for tours, estimates for performance gains, etc.

I know that there are methods for generating Low Discrepancy permutations, but I want information dedicated to tours and not to permutations in general.

What I have tried so far, is to combine the ability to calculate the n-th permutation via factoradic numbers with n taken from an appropriately chosen van der Corput sequence. I'm not quite satisfied with that approach because:
-the calculation of the n-th permutation is based on lexicographical ordering but, I would prefer the order generated by the Steinhaus-Trotter algorithm (because of the minimal change from one permutation to the next)
-the van der Corput sequence corresponds to inverting the sequence of bits and is thus tailored for value ranges that are powers of two; numbers ranges that are factorials do not fit that pattern and one has to reject certain values of the van der Corput sequence because they are outside the valid range
-cyclicity and symmetry are not taken into account

all that adds some bias, which worries me

• Superior in what sense? Also I don't see the analogy as integration is summing/averaging and TSP is minimizing. – Brendan McKay Jul 27 '13 at 16:21
• @Brendan: by superior I mean that the minimum of the first k generated tours is smaller on the average. There is of course no relation to integration; that only was intended as an example for beneficial use of Low Discrepancy methods. – Manfred Weis Jul 27 '13 at 16:56
• Ok, that is an interesting question but I suggest you edit the text to add this information. Nobody will respond if they don't get it. – Brendan McKay Jul 28 '13 at 1:51
• @BrendanMcKay: I edited my problem description in response to your feeback; thanks for the input. – Manfred Weis Jul 28 '13 at 10:23

Motivated by a recent upvote, I started to reconsider the problem.
The first thing I did, was to repeat my search for algorithms that generate the $n$-th Steinhaus-Trotter-Johnson permutation - needless to say that the search was still not successful; this time however my attention was caught by a noticable zig-zag pattern of the number $4$ in the visualisation of the JST sequence of all permutations of the numbers $1,2,3$ and $4$ in this wikipedia article; that seemed something where leveraging might be possible.
The outcome of that observation is detailed in the first part of the answer to my question; the second part will be dedicated to generating a low discrepancy sequence for enumerating the Hamilton cycles of a complete graph.

Part 1: ranking and unranking Johnson-Trotter-Steinhaus permutations
A closer look at the previously mentioned visualisation revealed that within each "zig" and within each "zag" the relative order of the elements $1,2$ and $3$ is unaltered and, that the sequence of those relative orders resembles the JST sequence of permutations of $1,2$ and $3$. Now, the position that is held by the number $k$ in the $n$-th JST permutation of the numbers $1,2,\ ...\ k$, one has to figure out, whether that permutation is in a "zig" or in a "zag" block and what $n\mod k$ is; in a "zig" block the position is determined as the $n\mod k$ from the right and from the left otherwise.
After the position of number $k$ is determined, one can determine the position of number $k-1$ by replacing $n$ with $n/k$ and the proceed in the same manner as for $k$ with the only difference, that previously determined positions for numbers with higher values are ignored.

Below is the C++ source code for calculating the permutation from its JST number and, for completenes sake, also the function, that does the opposite, namely to calculate the JST number of a given permutation.
The code is not highly optimized in order to make it not too cryptic.

// calculate the permutation with a given number in the Johnson-Trotter-Steinhaus
// sequence of permutations
void jstPermutation(size_t num_elements, size_t jst_number, std::vector<size_t>& jst_permutation)
{
for (int i = 0; i < num_elements; ++i){
jst_permutation[i] = 0;
}
int jst_index = jst_number - 1;
for (size_t element_label = num_elements; element_label > 0; --element_label){
int block_index = jst_index / element_label;
size_t free_pos = (block_index % 2)
? 1 + jst_index % element_label
: element_label-(jst_index%element_label);

size_t count_free = 0;
for (int i = 0; i < num_elements; ++i) {
if (jst_permutation[i] == 0 && ++count_free == free_pos){
jst_permutation[i] = element_label;
break;
}
}
jst_index = block_index;
} // element_label

// given a permutation, calculate its number in the Johnson-Trotter-Steinhaus
// sequence of permutations
void jstNumber(size_t num_elements, const std::vector<size_t>& jst_permutation, size_t& jst_number){
size_t jst_index = 0;
for (size_t element_label = 1; element_label <= num_elements; ++element_label){
size_t count_smaller = 0;
for (size_t i = 0; jst_permutation[i] != element_label; ++i){
if (jst_permutation[i] < element_label){
++count_smaller;
}
}
size_t remainder = (jst_index%2)
? count_smaller
: (element_label - 1) - count_smaller;
(jst_index *= element_label) += remainder;
}
jst_number = jst_index + 1;
}


Part 2: generating a low discrepancy sequence for Hamilton cycles
The first observation is that the fact, that factorials are in general no powers of two, is probably not an issue for practical problem, that can't be solved exactly due to their size; the reason is due to a result of Legendre concerning the prime factorization of factorials, according to wich $n!=2^{(n+h(n))}m$, where $h(n)$ is the Hamming weight of $n$, the number of $1$-bits in the binary representation of $n$.
A solution for a low discrepancy sequence that covers all permutations could be to insert some sentinel values, so that the total number of values to be covered is again a power of two.
If $n$ is so big, that an enumeration of all permutations is practically impossible, one would create a the low discrepancy sequence for a sufficiently small range of values from $(0,...,2^k <= 2^{(n+h(w)))}$, multiply with $\frac{n!}{2^k}$ and report the corresponding permutation.
If one needs a sequence for all permutations, then let $2^N$ be the smallest power of two that is not smaller than $n!$; the low discrepancy sequence is then generated over the range $(0,...,2^N)$ however with the twist that only those elements are reported, for which $\lfloor i\frac{n!}{2^N} \rfloor -\lfloor (i-1)\frac{n!}{2^N} \rfloor = 1$

Due to the property, that in the JST sequence of permutations the ones, for which the elements appear in opposite order, are $\frac{n!}{2}$ apart, and, because the first element in a sequence denoting a Hamilton cycle, can be fixed, it suffices to explore the first half of the JST sequence of permutations of $n-1$ elements.

As the functions presented above, have $O(n^2)$ time complexity, it is still desirable to find more efficient formulations; some ideas exist already on my side, but they are not mature enough to be presented already.

Finally, I would like to remark, that in view of the relative simplicity of the solution, I strongly suspect, that that is already known and documented somewhere; any pointers would be highly appreciated.