17
\$\begingroup\$

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

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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 → N2 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 f1(i) and f2(i) as the results.

To obtain a bijective mapping g : N → N3, we can define g(n) := (f1(i), f1(f2(i)), f2(f2(i))).

To obtain a bijective mapping h : N → N4, we can define h(i) := (g1(i), g2(i), f1(g3(i)), f2(g3(i))).

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

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#
\$\endgroup\$
  • \$\begingroup\$ xnor's idea also gives 20 bytes (or less if you golf it better than I did): q~2bW%1$Te]/zWf%2fbp (opposite input order) \$\endgroup\$ – Martin Ender Nov 12 '15 at 9:11
3
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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 → Nk by f(i) := (α1, … αk-1, p1αk…p2αk+1… - 1), where ⟨pn is the sequence of prime numbers and i + 1 = p1α1p2α2.

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

Since f(i) = (g1(i), … gk-1(i), g-1(gk(i), gk+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.
\$\endgroup\$
  • \$\begingroup\$ Why is your function bijective? \$\endgroup\$ – xnor Nov 12 '15 at 8:05
  • \$\begingroup\$ @xnor At least the one from my explanation wasn't, since I had swapped a couple of indices by mistake. I've added a proof sketch. \$\endgroup\$ – Dennis Nov 12 '15 at 13:54
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I realized I'm making this way too complicated... \$\endgroup\$ – xnor Nov 12 '15 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.