Enumerating N-Dimensional Vectors Given a positive integer k &gt; 1 and a non-negative integer i, generate a k-tuple (or k-dimensional vector) of non-negative integers. For every k, the map from ℕ to ℕk, must be bijective. That is, every input i should produce a different tuple, and every possible tuple must be produced by some input i.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

You may use any convenient, unambiguous, flat list format for the output.

Your solution should impose no artificial limits on k and i but you may assume that they fit into your language's native integer size. At the very least, you must support values up to 255, though, even your native integer size is smaller than that.

For any 1 &lt; k &lt; 32, i &lt; 231, your code should produce a result in a matter of seconds (of course, if your answer doesn't support i that large due to the previous rule, the limit is adjusted accordingly). This should be no issue: it's possible to solve this challenge such that it works up to 2128 in a few seconds, but the limit is there to avoid answers which actually iterate from 0 to i to find the result.

Please include in your answer a description of your chosen mapping and a justification for why it's bijective (this doesn't need to be a formal proof).

This is code golf, the shortest answer (in bytes) wins.

Related Challenges


Generate a pair of integers from a non-negative one
Output a list of all rational numbers
Pyth, 15 12 bytes

ms+0_%Q&gt;_zdQ


Test suite

My transformation is similar to one of xnor's, but in base 10. It works by unzipping the input into k separate numbers:

n = 21003034
k = 3

21003034
 1  3  4    134
2  0  3     203
  0  0        0


The numbers are ordered in decreasing position of the rightmost digit, so that all orderings of any group of numbers are possible.

The way the code works is we reverse the input, then slice off the last 0, 1, ... k-1 digits, then take every kth digit, reverse again, stick a 0 at the begining, and convert to int.