Dengan bilangan bulat positif k > 1dan bilangan bulat non-negatif i, buat k-tupel (atau kvektor -dimensi) dari bilangan bulat non-negatif. Untuk setiap k, peta dari ℕ ke ℕ ^k , harus bijective . Artinya, setiap inputi harus menghasilkan tuple yang berbeda, dan setiap tuple yang mungkin harus dihasilkan oleh beberapa input i.

Anda dapat menulis suatu program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter fungsi (keluar).

Anda dapat menggunakan format daftar datar yang nyaman, tidak ambigu, untuk output.

Solusi Anda seharusnya tidak memaksakan batasan buatan kdani tetapi Anda dapat mengasumsikan bahwa mereka sesuai dengan ukuran bilangan bulat asli bahasa Anda. Paling tidak, Anda harus mendukung nilai hingga 255, meskipun, ukuran bilangan bulat asli Anda lebih kecil dari itu.

Bagaimanapun 1 < k < 32, kode Anda akan menghasilkan hasil dalam hitungan detik (tentu saja, jika jawaban Anda tidak mendukung sebesar itu karena aturan sebelumnya, batasnya disesuaikan). Ini seharusnya tidak menjadi masalah: mungkin untuk menyelesaikan tantangan ini sehingga bisa bekerja hingga ¹²⁸ dalam beberapa detik, tetapi ada batasnya untuk menghindari jawaban yang sebenarnya beralih dari kei < 231i0i untuk menemukan hasilnya.

Harap sertakan dalam jawaban Anda deskripsi pemetaan yang Anda pilih dan alasan mengapa itu bersifat obyektif (ini tidak perlu menjadi bukti formal).

Ini adalah kode golf, jawaban terpendek (dalam byte) menang.

Tantangan Terkait

• Hasilkan sepasang bilangan bulat dari yang tidak negatif
• Keluarkan daftar semua angka rasional

Pyth, 15 12 byte

ms+0_%Q>_zdQ

Suite uji

Transformasi saya mirip dengan salah satu dari xnor, tetapi di basis 10. Ia bekerja dengan membuka ritsleting input ke dalam k nomor yang terpisah:

n = 21003034
k = 3

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

Angka-angka disusun dalam posisi menurun dari digit paling kanan, sehingga semua pemesanan dari kelompok angka apa pun dimungkinkan.

Cara kode bekerja adalah kita membalikkan input, lalu mengiris 0, 1, ... k-1digit terakhir , lalu mengambil setiap kdigit, mundur lagi, menempelkan a 0di awal, dan mengonversi ke int.

CJam, 20 byte

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

Pemetaan ini bersifat obyektif karena menerapkan pemetaan dari jawaban ini k - 1 kali.

Program membaca input sebagai i k. Cobalah online di juru bahasa CJam .

Ide

Kita dapat membuat pemetaan bijektif f: N → N ² dengan mendefinisikan f (i) sebagai berikut:

• Ubah i menjadi array angka binernya.

• Tambahkan a 0 ke larik ini jika ada angka ganjil.

• Deinterleave array yang dihasilkan, membentuk ke yang baru dalam proses.

• Konversikan array tersebut dari basis 2 ke integer. Tentukan f ₁ (i) dan f ₂ (i) sebagai hasilnya.

Untuk mendapatkan pemetaan bijektif g: N → N ³ , kita dapat mendefinisikan g (n): = (f ₁ (i), f ₁ (f ₂ (i)), f ₂ (f ₂ (i))) .

Untuk mendapatkan pemetaan bijektif h: N → N ⁴ , kita dapat mendefinisikan h (i): = (g ₁ (i), g ₂ (i), f ₁ (g ₃ (i)), f ₂ (g ₃ ( i))) .

Melanjutkan proses di atas, kami akhirnya tiba di peta bijective N → N ^k .

Kode

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#

CJam, 18 byte

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

Ini menggunakan formula yang lebih bodoh.

Coba di sini .

Penjelasan

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.

Singkatnya, ini memetakan bilangan bulat positif ke:

1. Jumlah nol yang tertinggal.
2. Bilangan bulat asli dengan nol trailing dihapus, dibalik, dan trailing (awalnya awal) 1 dihapus.

Python 2, 62

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

Kode ini jelek dan golf, tetapi idenya sangat sederhana.

Kemas kekspansi biner menjadi satu dengan membaca setiap kdigit dengan offset berbeda. Misalnya, dengan k=3, input 357memetakan ke (3,0,7):

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

Mengaitkan angka-angka kembali bersama-sama membalikkannya, jadi itu adalah sebuah kebohongan. Dengan demikian, anggap ekspansi biner memiliki angka nol terdepan dalam jumlah tak terbatas.

J, 38 28 27 byte

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

Ini adalah kata kerja diam-diam dan diad yang menggunakan i dan k sebagai argumen kiri dan kanan. Cobalah online dengan J.js .

Ide

Kami mendefinisikan peta f: N → N ^k oleh f (i): = (α ₁ , ... α _k-1 , p ₁ ^{α _k} ... p ₂ ^{α _{k + 1}} ... - 1) , di mana ⟨p _n ⟩ adalah urutan bilangan prima dan i + 1 = p ₁ ^{α ₁} p ₂ ^{α ₂} ... .

Dengan Teorema Aritmatika Fundamental, peta g: N → N ^ω didefinisikan oleh g (i): = (α ₁ , α ₂ , ...) (eksponen faktorisasi utama i + 1 ) adalah kata sifat.

Karena f (i) = (g ₁ (i), ... g _k-1 (i), g ^-1 (g _k (i), g _{k + 1} (i), ...)) , peta f bersifat bijektif sebagai baik.

Kode

                            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.

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)

Fungsi ini qbekerja pada angka-angka biner dengan mengambil setiap bit detik mulai dari akhir. Sebagai hasilnya, q(z), q(z>>1)berikan dua angka yang digit binernya diselingi z. Misalnya, 594 dibagi menjadi 12 dan 17.

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

Ini adalah peninggalan karena kita dapat menyatukan kembali angka-angka untuk memulihkan nomor aslinya.

Fungsi gini menerapkan k-1waktu penambangan ini , berkembang dari satu elemen ke sepasang menjadi tiga ... ke- kganda. Setiap kali, elemen terakhir diperluas menjadi dua elemen. Ini dilakukan secara rekursif dengan memetakan input ke suatu pasangan melalui bijection, mengambil elemen pertama dari pasangan untuk entri pertama dari output, dan menerapkan fungsi secara rekursif dengan k-1elemen kedua untuk menghasilkan entri yang tersisa.