introduction

Bien sûr, nous avons beaucoup de défis de séquence , alors voici un autre.

La séquence de Kimberling ( A007063 ) se présente comme suit:

1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28, 22, ...

Ceci est produit en mélangeant l'itération normale:

[1] 2  3  4  5  6  7  8

Le premier terme de la séquence est 1. Après cela, nous remanions la séquence jusqu'à ce que tous les termes à gauche soient utilisés. Le mélange a le motif right - left - right - left - .... Puisqu'il n'y a pas de termes à gauche de la 1, il n'y a pas de mélange. Nous obtenons ce qui suit:

 2 [3] 4  5  6  7  8  9

À la i ^ème itération, nous jetons le i ^ème élément et le mettons dans notre séquence. Ceci est la 2ème itération, nous jetons donc le 2ème élément. La séquence devient: 1, 3. Pour notre prochaine itération, nous allons mélanger l'itération actuelle avec le modèle ci-dessus. Nous prenons le premier article inutilisé à droite du i ^ème article. Cela se trouve être 4. Nous ajouterons ceci à notre nouvelle itération:

 4

Nous allons maintenant prendre le premier élément inutilisé à gauche du i ^ème élément. C'est ça 2. Nous ajouterons ceci à notre nouvelle itération:

 4  2

Puisqu'il ne reste aucun élément à gauche du i ^ème élément, nous allons simplement ajouter le reste de la séquence à la nouvelle itération:

 4  2 [5] 6  7  8  9  10  11  ...

Ceci est notre 3ème itération, nous allons donc jeter le 3ème élément, qui est 5. Ceci est le troisième élément de notre séquence:

 1, 3, 5

Pour obtenir la prochaine itération, répétez simplement le processus. J'ai fait un gif si ce n'est pas clair:

^{Le gif m'a pris plus de temps que d'écrire le message}

Tâche

• Étant donné un entier non négatif n , sortez les n premiers termes de la séquence
• Vous pouvez fournir une fonction ou un programme
• C'est du code-golf , donc la soumission avec le moins d'octets gagne!

Cas de test:

Input: 4
Output: 1, 3, 5, 4

Input: 8
Output: 1, 3, 5, 4, 10, 7, 15, 8

Input: 15
Output: 1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28

Remarque: les virgules dans la sortie ne sont pas nécessaires. Vous pouvez par exemple utiliser des sauts de ligne, ou afficher une liste, etc.

Pyth, 22 octets

JS*3QVQ@JN=J.i>JhN_<JN

Essayez-le en ligne: Démonstration

Effectue simplement la technique de brassage décrite dans le PO.

Explication:

JS*3QVQ@JN=J.i>JhN_<JN
JS*3Q                    assign the list [1, 2, ..., 3*input-1] to J
     VQ                  for N in range(Q):
       @JN                  print J[N]
            .i              interleave 
              >JhN             J[N+1:] with
                  _<JN         reverse J[:N]
          =J                assign the resulting list to J

Julia, 78 71 octets

n->[(i=j=x;while j<2i-3 j=i-(j%2>0?1-j:j+2)÷2;i-=1end;i+j-1)for x=1:n]

Il s'agit d'une fonction sans nom qui accepte un entier et renvoie un tableau d'entiers. Pour l'appeler, affectez-le à une variable.

L'approche ici est la même que celle décrite sur OEIS.

Non golfé:

# This computes the element of the sequence
function K(x)
    i = j = x
    while j < 2i - 3
        j = i - (j % 2 > 0 ? 1 - j : j + 2)÷2
        i -= 1
    end
    return i + j - 1
end

# This gives the first n terms of the sequence
n -> [K(i) for i = 1:n]

7 octets économisés grâce à Mauris!

Mathematica 130 octets

(n=0;s={};Nest[(n++;AppendTo[s,z=#[[n]]];Flatten[TakeDrop[#,1+2(n-1)]/.{t___,z,r___}:> 
Riffle[{r},Reverse@{t}]])&,Range[3*#],#];s)&

Nous commençons par une liste comprenant la plage de 1à 3x, où xest le nombre souhaité de termes de séquence de Kimberling.

A chaque étape, n, TakeDroprompt la liste actuelle dans une liste avant de 2n+1termes (où le travail est effectué) et la liste arrière (qui sera plus tard rejoint la liste avant retravaillé). La première liste correspond au modèle suivant, {t___,z,r___}où z est le terme de Kimberling au centre de la première liste. rest Riffleavec l'inverse de tpuis la liste arrière est ajoutée. zest supprimé et ajouté à ( AppendTo) la séquence de Kimberling croissante.

nest incrémenté de 1et la liste actuelle est traitée par la même fonction viaNest.

Exemple

(n=0;s={};Nest[(n++;AppendTo[s,z=#[[n]]];Flatten[TakeDrop[#,1+2(n-1)]/.{t___,z,r___}:> 
Riffle[{r},Reverse@{t}]])&,Range[3*#],#];s)&[100]

{1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28, 22, 42, 35, 33, 46, 53, 6, 36, 23, 2 , 55, 62, 59, 76, 65, 54, 11, 34, 48, 70, 79, 99, 95, 44, 97, 58, 84, 25, 13, 122, 83, 26, 115, 82, 91 , 52, 138, 67, 90, 71, 119, 64, 37, 81, 39, 169, 88, 108, 141, 38, 16, 146, 41, 21, 175, 158, 165, 86, 191, 45 , 198, 216, 166, 124, 128, 204, 160, 12, 232, 126, 208, 114, 161, 156, 151, 249, 236, 263, 243, 101, 121, 72, 120, 47, 229 }

Python 2, 76 octets

for a in range(input()):
 b=a+1
 while-~b<2*a:b=a-(b^b%-2)/2;a-=1
 print a+b

Explication

C'est la formule OEIS après de nombreuses transformations golfiques! Cela a fonctionné magnifiquement . Le code d'origine était

i=b=a+1
while b<2*i-3:b=i-(b+2,1-b)[b%2]/2;i-=1
print i+b-1

Je me suis d'abord débarrassé de i, en le remplaçant par a+1partout et en développant les expressions:

b=a+1
while b<2*a-1:b=a+1-(b+2,1-b)[b%2]/2;a-=1
print a+b

Ensuite, récrit b<2*a-1comme -~b<2*apour sauver un octet d'espaces, et déplacé le +1dans la sélection, la division par 2, et la négation:

while-~b<2*a:b=a-(b,-b-1)[b%2]/2;a-=1

Alors, -b-1c'est juste ~b, alors on peut écrire (b,~b)[b%2]. Cela équivaut à b^0 if b%2 else b^-1utiliser l'opérateur XOR, ou à défaut b^b%-2.

while-~b<2*a:b=a-(b^b%-2)/2;a-=1

Pyth, 29 25 octets

VQ+.W<hHyN-~tN/x%Z_2Z2hNN

Jakube a enregistré 4 octets, mais je ne sais plus comment lire le code.

Voici l'ancienne solution:

VQKhNW<hKyN=K-~tN/x%K_2K2)+KN

Traduction de ma réponse Python. Je ne suis pas très bon en Pyth, alors peut-être qu'il y a encore des moyens de raccourcir cela.

VQ                              for N in range(input()):
  KhN                             K = N+1
     W<hKyN                       while 1+K < 2*N:
           =K-~tN/x%K_2K2)         K = (N--) - (K%-2 xor K) / 2
                          +KN     print K + N

APL, 56 44 octets

{⍵<⍺+⍺-3:(⍺-1)∇⍺-4÷⍨3+(1+2×⍵)ׯ1*⍵⋄⍺+⍵-1}⍨¨⍳

Il s'agit d'un train monadique sans nom qui accepte un entier à droite et renvoie un tableau. C'est à peu près la même approche que ma réponse Julia .

La fonction la plus interne est une fonction dyadique récursive qui renvoie le n ème terme dans la séquence de Kimberling, donné n comme arguments identiques à gauche et à droite.

{⍵<⍺+⍺-3:                                    ⍝ If ⍵ < 2⍺ - 3
         (⍺-1)∇⍺-4÷⍨3+(1+2×⍵)ׯ1*⍵           ⍝ Recurse, incrementing a and setting
                                             ⍝ ⍵ = ⍺ - (3 + (-1)^⍵ * (1 + 2⍵))/4
                                   ⋄⍺+⍵-1}   ⍝ Otherwise return ⍺ + ⍵ - 1

Avec cela en main, nous pouvons obtenir des termes individuels de la séquence. Cependant, le problème devient alors qu'il s'agit d'une fonction dyadique , ce qui signifie qu'elle nécessite des arguments des deux côtés. Entrez l' ⍨opérateur! Étant donné une fonction fet une entrée x, f⍨xest identique à x f x. Donc dans notre cas, en faisant référence à la fonction susmentionnée f, nous pouvons construire le train monadique suivant:

f⍨¨⍳

Nous appliquons fà chaque entier de 1 à l'entrée, ce qui donne un tableau.

Enregistré 12 octets grâce à Dennis!