Enumerating N-Dimensional Vectors

Question

Given a positive integer k > 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 < k < 32, i < 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 2¹²⁸ 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

Answer 1

Pyth, 15 12 bytes

ms+0_%Q>_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.

Answer 2

CJam, 20 bytes

q~({4b2fmd2/z2fb~p}*

The mapping is bijective since it applies the mapping from this answer k - 1 times.

The program reads the input as i k. Try it online in the CJam interpreter.

Idea

We can construct a bijective mapping f : N → N² by defining f(i) as follows:

• Convert i into the array of its binary digits.

• Prepend a 0 to this array if there is an odd number of digits.

• Deinterleave the resulting array, forming to new ones in the process.

• Convert those arrays from base 2 to integer. Define f₁(i) and f₂(i) as the results.

To obtain a bijective mapping g : N → N³, we can define g(n) := (f₁(i), f₁(f₂(i)), f₂(f₂(i))).

To obtain a bijective mapping h : N → N⁴, we can define h(i) := (g₁(i), g₂(i), f₁(g₃(i)), f₂(g₃(i))).

Continuing the above process, we eventually arrive at a bijective map N → N^k.

Code

q~      e# Read and evaluate all input. This pushes i and k.
({      e# Do k-1 times:
  4b    e#   Convert the integer on the stack (initially i) to base 4.
  2fmd  e#   Replace each base-4 digit d by d/2 and d%2.
  2/    e#   Split into the chunks [d/2 d%2].
  z     e#   Transpose. This collects all quotients in one array and all
        e#   residues in another one.
  2fb   e#   Convert each array from base 2 to integer.
  ~     e#   Dump both integers on the stack.
  p     e#   Print the topmost one.
}*      e#

Answer 3

J, 38 28 27 bytes

(({.,g^:_1@}.)g=:_ q:>:)~<:

This is a tacit, dyadic verb that takes i and k as left and right arguments. Try it online with J.js.

Idea

We define a map f : N → N^k by f(i) := (α₁, … α_k-1, p₁^α_k…p₂^α_k+1… - 1), where 〈p_n〉 is the sequence of prime numbers and i + 1 = p₁^α₁p₂^α₂….

By the Fundamental Arithmetic Theorem, the map g : N → N^ω defined by g(i) := (α₁, α₂, …) (exponents of the prime factorization of i + 1) is bijective.

Since f(i) = (g₁(i), … g_k-1(i), g^-1(g_k(i), g_k+1(i), …)), the map f is bijective as well.

Code

                            Left argument: i -- Right argument: k
                         <: Decerement k.
(                      )~   Reverse the order of the arguments and apply the
                            dyadic verb inside the parentheses to k-1 and i.
              g=:            Define a monadic helper verb g:
                     >:       Increment its right argument.
                 _ q:         Calculate the exponents of the prime factorization.
                             (implicit) Apply g to i.
(            )               Apply the dyadic verb inside the parentheses to k-1
                             and (g i).
           }.                 Drop the first k-1 elements of (g i)...
          @                   and...
     g^:_1                    apply the inverse of g to the result.
  {.                          Take the first k-1 elements of (g i).
    ,                         Append the rightmost result to the leftmost one.

Answer 4

CJam, 18 bytes

q~({)2bW%_1#p))b}*

It uses a more stupid formula.

Try it here.

Explanation

q~          e# Read input.
({          e# Repeat k-1 times:
    )       e# Increment the current integer (initially i), to make it positive.
    2b      e# Convert to binary.
    W%      e# Reverse the binary.
            e# The result can be any non-empty binary string without trailing 0s.
    _1#     e# Find the position of the first 1, or the number of initial 0s.
    p       e# Print.
    )       e# Extract the final bit, which is always 1.
            e# An array that can be any binary string is left in the stack.
    )       e# Increment the 1 to make it 2.
    b       e# Convert the binary string to a number using base 2.
            e# Only the number of initial 0s doesn't affect the result,
            e# which is exactly what is printed before.
}*          e# The final integer is printed automatically when the program ends.

In summary, it maps a positive integer to:

1. The number of trailing zeros.
2. The original integer with trailing zeros removed, reversed, and the trailing (originally initial) 1 removed.

Answer 5

Python 2, 62

lambda z,k:[int('0'+bin(z)[~i:1:-k][::-1],2)for i in range(k)]

This code is ugly and golfable, but the idea is very simple.

Pack k binary expansions into one by reading every kth digit with different offsets. For example, with k=3, the input 357 maps to (3,0,7):

101100101 <- 357
  1  0  1 -> 5
 0  0  0  -> 0
1  1  1   -> 7

Zipping the numbers back together reverses it, so it's a bijection. In doing so, think of the binary expansions as having an infinite number of leading zeroes.

Answer 6

Python 2, 72

q=lambda z:z and z%2+2*q(z/4)
g=lambda z,k:1/k*[z]or[q(z)]+g(q(z/2),k-1)

The function q acts on binary numbers by taking every second bit starting from the end. As a result q(z), q(z>>1) gives two numbers whose binary digits intersperse to give z. For example, 594 splits into 12 and 17.

1001010010   <- 594
 0 1 1 0 0   ->  12
1 0 0 0 1    ->  17

This is a bijection because we can zip the numbers back together to recover the original number.

The function g applies this bijection k-1 times, expanding from a single element to a pair to a triple ... to a k-tuple. Each time, the last element is expanded to two elements. This is done recursively by mapping the input to a pair via the bijection, taking the first element of the pair for the first entry of the output, and applying the function recursively with k-1 to the second element to produce the remaining entries.