introduction

Un tableau de pointeurs est un tableau Ld'entiers non nuls où se 0 ≤ L[i]+i < len(L)tient pour tous les indices i(en supposant une indexation basée sur 0). Nous disons que l'indice i pointe vers l'indice L[i]+i. Un tableau de pointeurs est une boucle si les indices forment un seul cycle de longueur len(L). Voici quelques exemples:

• [1,2,-1,3]n'est pas un tableau de pointeurs, car le 3ne pointe pas vers un index.
• [1,2,-1,-3]est un tableau de pointeurs, mais pas une boucle, car aucun index ne pointe vers le -1.
• [2,2,-2,-2] est un tableau de pointeurs, mais pas une boucle, car les indices forment deux cycles.
• [2,2,-1,-3] est une boucle.

Contribution

Votre entrée est une liste non vide d'entiers non nuls, dans n'importe quel format raisonnable. Il peut ne pas être trié et / ou contenir des doublons.

Production

Votre sortie doit être une boucle qui contient tous les entiers de la liste d'entrée (et éventuellement d'autres entiers également), en comptant les multiplicités. Ils n'ont pas besoin de se produire dans le même ordre que dans l'entrée, et la sortie n'a pas besoin d'être minimale dans aucun sens.

Exemple

Pour l'entrée [2,-4,2], une sortie acceptable serait [2,2,-1,1,-4].

Règles et notation

Vous pouvez écrire un programme complet ou une fonction. Le nombre d'octets le plus bas l'emporte et les failles standard sont interdites. L'inclusion de quelques exemples d'entrées et de sorties dans votre réponse est appréciée.

Cas de test

Celles-ci sont données dans le format input -> some possible output(s).

[1] -> [1,-1] or [1,1,1,-3]
[2] -> [2,-1,-1] or [1,2,-2,-1]
[-2] -> [1,1,-2] or [3,1,2,-2,-4]
[2,-2] -> [2,-1,1,-2] or [2,-1,2,-2,-1]
[2,2,2] -> [2,-1,2,-2,2,-2,-1] or [2,2,2,2,-3,-5]
[2,-4,2] -> [2,2,-1,1,-4] or [2,5,1,1,1,-4,2,-7,-1]
[3,-1,2,-2,-1,-5] -> [2,3,-1,2,-1,-5] or [3,3,-1,-1,2,2,-1,6,1,1,1,1,-12,-5]
[-2,-2,10,-2,-2,-2] -> [10,-1,1,-2,-2,1,-2,-2,1,-2,-2]
[-15,15,-15] -> [15,-1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,-15,-15]
[1,2,3,4,5] -> [1,2,3,-1,4,-1,5,-1,-1,-9,-1,-1]

Gelée, 12 octets

ż~Ṣ€FxA$;L$U

Essayez-le en ligne!

Contexte

Considérez la paire d'entiers n, ~ n , où n ≥ 0 et ~ dénote NON au niveau du bit, c'est-à-dire ~ n = - (n + 1) .

En plaçant n copies de n à gauche de n + 1 copies de ~ n , si nous commençons à parcourir le tableau de pointeurs à partir de la droite ~ n , nous traverserons tous les éléments 2n + 1 et nous nous retrouverons à gauche de la gauche n .

Par exemple, si n = 4 :

X  4  4  4  4  -5 -5 -5 -5 -5
                            ^
            ^
                         ^
         ^
                      ^
      ^
                   ^
   ^
                ^
^

Pour le cas particulier n = 0 , l'élément n lui-même est répété 0 fois, laissant ceci:

X -1
   ^
^

Pour chaque entier k dans l'entrée, nous pouvons former une paire n, ~ n qui contient k en fixant n = k si k> 0 et n = ~ k si k <0 . Cela fonctionne parce que ~ est une involution, c'est-à-dire ~~ k = k .

Il ne reste plus qu'à enchaîner les tuples générés et à ajouter leurs longueurs combinées, de sorte que l'élément le plus à gauche nous ramène à celui le plus à droite.

Exemples

[1] -> [3, 1, -2, -2]
[2] -> [5, 2, 2, -3, -3, -3]
[-2] -> [3, 1, -2, -2]
[2, -2] -> [8, 1, -2, -2, 2, 2, -3, -3, -3]
[2, 2, 2] -> [15, 2, 2, -3, -3, -3, 2, 2, -3, -3, -3, 2, 2, -3, -3, -3]
[2, -4, 2] -> [17, 2, 2, -3, -3, -3, 3, 3, 3, -4, -4, -4, -4, 2, 2, -3, -3, -3]
[3, -1, 2, -2, -1, -5] -> [26, 4, 4, 4, 4, -5, -5, -5, -5, -5, -1, 1, -2, -2, 2, 2, -3, -3, -3, -1, 3, 3, 3, -4, -4, -4, -4]
[-2, -2, 10, -2, -2, -2] -> [36, 1, -2, -2, 1, -2, -2, 1, -2, -2, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, 1, -2, -2, 1, -2, -2]
[-15, 15, -15] -> [89, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15]
[1, 2, 3, 4, 5] -> [35, 5, 5, 5, 5, 5, -6, -6, -6, -6, -6, -6, 4, 4, 4, 4, -5, -5, -5, -5, -5, 3, 3, 3, -4, -4, -4, -4, 2, 2, -3, -3, -3, 1, -2, -2]

Comment ça fonctionne

ż~Ṣ€FxA$;L$U  Main link. Argument: A (list of integers)

 ~            Yield the bitwise not of each k in A.
ż             Zipwith; pair each k in A with ~k.
  Ṣ€          Sort each pair, yielding [~n, n] with n ≥ 0.
    F         Flatten the list of pairs.
       $      Combine the previous two links into a monadic chain:
      A         Yield the absolute values of all integers in the list.
                |n| = n and |~n| = |-(n + 1)| = n + 1
     x          Repeat each integer m a total of |m| times.
          $   Combine the previous two links into a monadic chain:
         L      Yield the length of the generated list.
        ;       Append the length to the list.
           U  Upend; reverse the generated list.