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

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: |
is surjective, so that . | ||||||

Proof: |
Let , , and . Assume that , then
The transition from (1) to (2) is allowed as . Similar goes for the equivalence of (2) and (3): as . |

Theorem: |
is surjective, so that . |

Proof: |
Let then the vector (which obviously fullfils ) must exist, since and . |

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.