Étant donné un entier positif k > 1et un entier non négatif i, générez un k-tuple (ou kvecteur -dimensionnel ) d'entiers non négatifs. Pour tout k, la carte de ℕ à ℕ ^k , doit être bijective . Autrement dit, chaque entrée idoit produire un tuple différent, et chaque tuple possible doit être produit par une entrée i.

Vous pouvez écrire un programme ou une fonction, en prenant une entrée via STDIN (ou l'alternative la plus proche), un argument de ligne de commande ou un argument de fonction et en sortant le résultat via STDOUT (ou l'alternative la plus proche), la valeur de retour de la fonction ou le paramètre de la fonction (out).

Vous pouvez utiliser n'importe quel format de liste plat pratique et sans ambiguïté pour la sortie.

Votre solution ne devrait pas imposer de limites artificielles ket ivous pouvez supposer qu'elles correspondent à la taille entière native de votre langue. À tout le moins, vous devez prendre en charge des valeurs jusqu'à 255, cependant, même votre taille entière native est plus petite que cela.

Pour tout 1 < k < 32, votre code devrait produire un résultat en quelques secondes (bien sûr, si votre réponse ne prend pas en charge cette taille en raison de la règle précédente, la limite est ajustée en conséquence). Cela ne devrait pas poser de problème: il est possible de résoudre ce défi de telle sorte qu'il fonctionne jusqu'à 2 ¹²⁸ en quelques secondes, mais la limite est là pour éviter les réponses qui itèrent réellement de à pour trouver le résultat.i < 231i0i

Veuillez inclure dans votre réponse une description de la cartographie que vous avez choisie et une justification de la raison pour laquelle elle est bijective (cela n'a pas besoin d'être une preuve formelle).

C'est le code golf, la réponse la plus courte (en octets) l'emporte.

Défis liés

• Générer une paire d'entiers à partir d'un entier non négatif
• Afficher une liste de tous les nombres rationnels

Pyth, 15 12 octets

ms+0_%Q>_zdQ

Suite de tests

Ma transformation est similaire à celle de xnor, mais en base 10. Elle fonctionne en décompressant l'entrée en k nombres séparés:

n = 21003034
k = 3

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

Les numéros sont classés par ordre décroissant du chiffre le plus à droite, de sorte que tous les ordres de n'importe quel groupe de numéros sont possibles.

La façon dont le code fonctionne est que nous inversons l'entrée, puis coupons les derniers 0, 1, ... k-1chiffres, puis prenons tous les ktrois chiffres, inversons à nouveau, collons a 0au début et convertissons en int.

CJam, 20 octets

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

Le mappage est bijectif car il applique le mappage de cette réponse k - 1 fois.

Le programme lit l'entrée comme i k. Essayez-le en ligne dans l' interpréteur CJam .

Idée

On peut construire une cartographie bijective f: N → N ² en définissant f (i) comme suit:

• Convertissez i dans le tableau de ses chiffres binaires.

• Ajoutez un 0 à ce tableau s'il y a un nombre impair de chiffres.

• Désentrelacez le tableau résultant, en en formant de nouveaux dans le processus.

• Convertissez ces tableaux de la base 2 en entier. Définissez f ₁ (i) et f ₂ (i) comme résultats.

Pour obtenir une cartographie bijective g: N → N ³ , nous pouvons définir g (n): = (f ₁ (i), f ₁ (f ₂ (i)), f ₂ (f ₂ (i))) .

Pour obtenir une cartographie bijective h: N → N ⁴ , on peut définir h (i): = (g ₁ (i), g ₂ (i), f ₁ (g ₃ (i)), f ₂ (g ₃ ( i))) .

En poursuivant le processus ci-dessus, nous arrivons finalement à une carte bijective 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#

CJam, 18 octets

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

Il utilise une formule plus stupide.

Essayez-le ici .

Explication

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.

En résumé, il associe un entier positif à:

1. Le nombre de zéros à la fin.
2. L'entier d'origine avec les zéros de fin supprimés, inversés et le dernier (initialement initial) 1 supprimé.

Python 2, 62

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

Ce code est moche et jouable au golf, mais l'idée est très simple.

Emballez kles extensions binaires en une seule en lisant chaque ke chiffre avec des décalages différents. Par exemple, avec k=3, l'entrée 357correspond à (3,0,7):

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

Le fait de compresser les chiffres ensemble l'inverse, c'est donc une bijection. Ce faisant, pensez aux extensions binaires comme ayant un nombre infini de zéros non significatifs.

J, 38 28 27 octets

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

Il s'agit d'un verbe dyadique tacite qui prend i et k comme arguments gauche et droit. Essayez en ligne avec J.js .

Idée

Nous définissons une carte f: N → N ^k par = (α: f (i) ₁ , ... α _k-1 , p ₁ ^{α _k} ... p ₂ ^{α _{k + 1}} ... - 1) , où ⟨p _n ⟩ est le séquence de nombres premiers et i + 1 = p ₁ ^{α ₁} p ₂ ^{α ₂} … .

Selon le théorème arithmétique fondamental, la carte g: N → N ^ω définie par g (i): = (α ₁ , α ₂ ,…) (exposants de la factorisation en facteurs premiers de i + 1 ) est bijective.

Puisque f (i) = (g ₁ (i),… g _k-1 (i), g ^-1 (g _k (i), g _{k + 1} (i),…)) , la carte f est bijective comme bien.

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.

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)

La fonction qagit sur les nombres binaires en prenant chaque deuxième bit à partir de la fin. En conséquence, q(z), q(z>>1)donne deux nombres dont les chiffres binaires s'interpénètrent pour donner z. Par exemple, 594 se divise en 12 et 17.

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

Il s'agit d'une bijection car nous pouvons compresser les numéros ensemble pour récupérer le numéro d'origine.

La fonction gapplique ces k-1temps de bijection , passant d'un seul élément à une paire à un triple ... à un k-tuple. Chaque fois, le dernier élément est développé en deux éléments. Cela se fait de manière récursive en mappant l'entrée à une paire via la bijection, en prenant le premier élément de la paire pour la première entrée de la sortie et en appliquant la fonction récursivement avec k-1au deuxième élément pour produire les entrées restantes.