This algorithm is something a friend of mine and I have developed quite some time ago (probably a year or so). It might also be already known under some name and I’m not aware of it. None the less it’s an interesting solution to a quite interesting problem.
Suppose that you wanted to generate the words
of the alphabet
. And that you wanted to do that in a parallel manner, such that you had a set of threads where each thread has a unique number out of
assigned.
In that case it would be favorable to have a mapping in the form
, so that each thread could easily (reading with less computational effort) generate the word it’s supposed to work on. Notice that implicit definition of
.



In that case it would be favorable to have a mapping in the form


To solve the problem described previously, we start with a function that maps elements of
to points in an
-dimensional discrete hypercube. That mapping
is defined as follows:
where
. This mapping obviously maps a natural number
to a point in a discrete
-dimensional hypercube with an edge length of
. Example: Consider
and
. Then we can visualize
as follows:












Now that we have a mapping from a natural number to a point in the hypercube, we need a mapping from a point in the hypercube to the word itself. Such a mapping
is easy to find. Consider
where the
are the components of the vector
and
.





So our final mapping
is
and exactly what we desired. One might notice that
must be surjective so that each word is computed if there are just enough threads. To prove that, we’ll prove that
as well as
is surjective (since the functional composition of two surjective functions is surjective as well).





Theorem: | ![]() ![]() |
||||||
Proof: | Let ![]() ![]() ![]() ![]() ![]()
The transition from (1) to (2) is allowed as |
Theorem: | ![]() ![]() |
Proof: | Let ![]() ![]() ![]() ![]() ![]() |
So the mapping
is surjective and does exactly what we want. I consider that solution to be a particular elegant one and wanted of post it for about a year now. Finally I found some spare time to do so. If you use that solution, find a mistake or find it somewhere else (maybe even previously described) please drop a comment.
