Numéros en sortie jusqu'à 2 ^ n-1, «triés»

38

Prenez un entier positif n comme entrée et indiquez (parmi certains) les nombres décimaux pouvant être créés à l'aide de n bits, classés de la manière suivante:

Commencez par lister tous les nombres pouvant être créés avec un seul 1et le reste 0dans la représentation binaire (triés), puis tous les nombres pouvant être créés avec deux consécutives 1 , les autres 0, trois consécutives 1 , etc.

Voyons à quoi cela ressemble pour n = 4 :

0001  -  1
0010  -  2
0100  -  4
1000  -  8
0011  -  3
0110  -  6
1100  -  12
0111  -  7
1110  -  14
1111  -  15

Ainsi, la sortie pour n = 4 est la suivante: 1, 2, 4, 8, 3, 6, 12, 7, 14, 15 (format de sortie optionnel).

Cas de test:

n = 1
1

n = 2
1 2 3

n = 3
1, 2, 4, 3, 6, 7

n = 8
1, 2, 4, 8, 16, 32, 64, 128, 3, 6, 12, 24, 48, 96, 192, 7, 14, 28, 56, 112, 224, 15, 30, 60, 120, 240, 31, 62, 124, 248, 63, 126, 252, 127, 254, 255

n = 17
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 3, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 7, 14, 28, 56, 112, 224, 448, 896, 1792, 3584, 7168, 14336, 28672, 57344, 114688, 15, 30, 60, 120, 240, 480, 960, 1920, 3840, 7680, 15360, 30720, 61440, 122880, 31, 62, 124, 248, 496, 992, 1984, 3968, 7936, 15872, 31744, 63488, 126976, 63, 126, 252, 504, 1008, 2016, 4032, 8064, 16128, 32256, 64512, 129024, 127, 254, 508, 1016, 2032, 4064, 8128, 16256, 32512, 65024, 130048, 255, 510, 1020, 2040, 4080, 8160, 16320, 32640, 65280, 130560, 511, 1022, 2044, 4088, 8176, 16352, 32704, 65408, 130816, 1023, 2046, 4092, 8184, 16368, 32736, 65472, 130944, 2047, 4094, 8188, 16376, 32752, 65504, 131008, 4095, 8190, 16380, 32760, 65520, 131040, 8191, 16382, 32764, 65528, 131056,16383, 32766, 65532, 131064, 32767, 65534, 131068, 65535, 131070, 131071

C'est du , donc le code le plus court dans chaque langue gagne!

Les bonnes explications sont vivement encouragées , y compris pour les solutions dans les "langages normaux"!

Stewie Griffin
la source
2
@zeppelin Je le pensais aussi au début, mais celui-ci est très différent.
ETHproductions
1
En relation. (Légèrement.)
Martin Ender
6
Bonus imaginaire si quelqu'un le fait sans aucune forme de conversion de base (en utilisant de vieux maths simples).
Stewie Griffin
A écrit ceci qui est un mélange entre les deux Je suppose Essayez-le en ligne!
PrincePolka

Réponses:

38

Python , 53 octets

f=lambda n,i=1:n*[f]and[i]+f(n-1,2*i)+i%2*f(n-1,i-~i)

Essayez-le en ligne!

La fonction récursive génère la liste triée sous forme de promenade de pré-commande dans cet arbre (exemple avec n=4):

      1
     / \
    2   3
   /   / \
  4   6   7
 /   /   / \
8   12  14  15

1 2 4 8 3 6 12 7 14 15

Les branches de gauche doublent la valeur et les branches de droite n'existent i->i*2+1et n'existent que pour les impairs i. Donc, la marche de pré-commande pour les non-feuilles est T(i)=[i]+T(i*2)+i%2*T(i*2+1).

L'arbre se termine en profondeur n, où se ntrouve l'entrée. Ceci est réalisé en décrémentant nà chaque pas en bas et en s’arrêtant quand il est 0.

Une autre stratégie serait de mettre fin aux valeurs qui idépassent 2**nplutôt que de suivre la profondeur. J'ai trouvé que c'était un octet de plus:

f=lambda n,i=1:2**n/i*[f]and[i]+f(n,2*i)+i%2*f(n,i-~i)
f=lambda n,i=1:[f][i>>n:]and[i]+f(n,2*i)+i%2*f(n,i-~i)
Xnor
la source
4
Sensationnel. Non seulement c'est un truc vraiment cool / intelligent, mais c'est aussi extrêmement efficace. +1, réponse vraiment sympa!
DJMcMayhem
2
C'est [f]une touche amusante, je ne peux pas dire que j'ai déjà vu ça auparavant.
FryAmTheEggman
18

Gelée , 6 octets

Ḷ2*ẆS€

Cela qualifie pour le bonus imaginaire .

Essayez-le en ligne!

Comment ça marche

Ḷ2*ẆS€  Main link. Argument: n

Ḷ       Unlength; yield [0, ..., n-1].
 2*     Yield [2**0, ..., 2**(n-1)].
   Ẇ    Sliding window; yield all subarrays of consecutive elements.
        The subarrays are sorted by length, then from left to right.
    S€  Map the sum atom over the substrings.
Dennis
la source
1
est un idéal intégré pour ce défi, et il est mis en œuvre pour que les résultats soient dans le bon ordre pour ce défi. Bien fait :-)
ETHproductions
N'est-ce pas 12 octets (au moins en UTF-8)?
Gareth
1
@Gareth Oui, mais Jelly prend également en charge un jeu de caractères à un octet , contenant les 256 symboles uniquement compris.
Dennis
9

Mathematica, 40 octets

Join@@Table[2^j(2^i-1),{i,#},{j,0,#-i}]&

Chaque nombre dans la liste désirée est la différence de deux puissances de 2, nous les générons simplement dans l’ordre en utilisant Tablepuis aplatissant la liste. Je pense que cela mérite le bonus imaginaire de Stewie Griffin :)

Mathematica, 35 octets

Tr/@Rest@Subsequences[2^Range@#/2]&

Un port de l'algorithme Jelly de Dennis . Je ne savais pas Subsequencesavant ça! (Je n'ai pas vu non plus que Miles avait posté cette réponse exacte ... allez-y!)

Greg Martin
la source
1
Remarque: cette solution est identique au code Mathematica de @mile , publié 5 heures avant la modification de @GregMartin. Cependant, par méta-consensus , cette réponse est toujours valide.
JungHwan Min
Ugh, je ne l'ai pas vu — merci de l'avoir signalé.
Greg Martin
8

JavaScript (ES6), 59 58 55 octets

for(q=prompt(n=1);p=q--;n-=~n)for(m=n;p--;m*=2)alert(m)

Un programme complet qui prend une entrée par une invite et alerte chaque numéro successivement. Cela se qualifie également pour le bonus imaginaire .

Extrait de test

(Note: utilise console.logau lieu de alert)

ETHproductions
la source
Suggestion (après avoir coché la case "Ne plus afficher les popups"): Passez à console.log pour l'extrait de test.
Tejas Kale
@ TejasKale Bonne idée, merci!
ETHproductions
7

JavaScript (ES6), 55 51 octets

Retourne une liste d'entiers séparés par des espaces.

n=>(F=k=>k>>n?--j?F(k>>j|1):'':k+' '+F(k*2))(1,j=n)

Bonus imaginaire convivial.

Formaté et commenté

n => (                    // main function, takes n as input
  F = k =>                // recursive function, takes k as input
    k >> n ?              // if k is greater or equal to 1 << n:
      --j ?               //   decrement j ; if j is > 0:
        F(k >> j | 1)     //     do a recursive call with an additional bit set
      :                   //   else
        ''                //     stop recursion
    :                     // else
      k + ' ' + F(k * 2)  //   append k to output and do a recursive call with k * 2
  )(1, j = n)             // start the recursion with k = 1 and j = n

Cas de test

Arnauld
la source
6

Python 2 , 64 61 octets

-3 octets grâce à Dennis

n=2**input()
j=i=1
while j<n:
 print i;i*=2
 if i/n:i=j=2*j+1

Essayez-le en ligne!

Barre
la source
6

Mathematica, 35 octets

Tr/@Rest@Subsequences[2^Range@#/2]&
milles
la source
5

Python 2 , 65 63 58 octets

lambda n:[(2<<k/n)-1<<k%n for k in range(n*n)if k/n+k%n<n]

Essayez-le en ligne!

Dennis
la source
1
Je viens de passer une heure à élaborer cette formule (2<<i)-1<<j... et vous l'avez déjà compris. Bon travail! En outre, bon travail pour se débarrasser des gammes doubles
TheNumberOne
4

Haskell, 47 octets

f n=[1..n]>>= \b->take(n-b+1)$iterate(2*)$2^b-1

Exemple d'utilisation: f 4-> [1,2,4,8,3,6,12,7,14,15]. Essayez-le en ligne! .

Comment ça marche: pour chaque nombre bdans [1..n], commencez par 2^b-1et doublez plusieurs fois la valeur et prenez des n-b+1éléments de cette liste.

nimi
la source
4

Groovy, 90 89 octets

{(0..<2**it).collect{0.toBinaryString(it)}.sort{it.count("1")}.collect{0.parseInt(it,2)}}

La conversion binaire est tellement stupide en groovy.

-1 grâce à Gurupad Mamadapur

Urne Magique De Pieuvre
la source
3
28 octets passe-partout binaire, si douloureux.
Urne magique Octopus
1
{(1..<2**it)...enregistre un octet.
Gurupad Mamadapur
3

Utilitaires Bash + Unix, 51 octets

dc<<<2i`seq -f%.f $[10**$1-1]|grep ^1*0*$|sort -r`f

Essayez-le en ligne!

L'entrée n est passée dans un argument.

Utilisez seq pour imprimer tous les nombres de n chiffres ou moins. (Ce sont des chiffres en base 10, donc il y a beaucoup de chiffres supplémentaires ici. C'est une perte de temps et de perte de temps, mais c'est du code golf!)

L'appel à grep ne conserve que les nombres composés précisément de 1, suivis de 0.

Ensuite, utilisez sort -r pour les trier par ordre lexicographique inverse.

Enfin, le courant continu est réglé sur l’entrée base 2: il pousse les nombres triés sur une pile, puis l’imprime de haut en bas. (Ceci imprime le dernier élément poussé en premier, etc., c'est pourquoi j'utilise plutôt -r au lieu de simplement trier.)

Correction d'un bug: j'avais omis l'option -f% .f dans seq, qui est requise pour les nombres entiers à partir de 1000000. (Merci à @TobySpeight pour avoir signalé qu'il y avait un problème.)

Mitchell Spector
la source
" Gaspillage de temps " ... et intelligent ! Merci pour cela. C’est un bon rappel d’ignorer délibérément l’efficacité des calculs lors de la pratique du golf. C'est vraiment difficile quand vous passez le reste de vos jours à écrire du code clair et rapide ...
Toby Speight
Certaines valeurs manquent: dc<<<2i`seq $[10**7-1]|grep ^1*0*$|sort -r`f | wc -seulement 12 valeurs sont rapportées. Je pense que tu veux à la grep ^1[01]*$place.
Toby Speight
@TobySpeight Merci - il y a eu un bug que j'ai corrigé. Le problème n'était pas avec la regex; le problème était que seq nécessitait une option. (Je ne suis pas sûr de savoir pourquoi vous n’obteniez que 12 valeurs de sortie, même si la version incorrecte donnait 21 valeurs de sortie au lieu des 28 correctes. Si vous l’utilisiez sur TIO, il se peut qu’il ait dépassé le délai d’une minute de TIO. .) Je l’ai déjà testé sous Linux et OS X.
Mitchell Spector
1
En fait, j’ai mal compris la question: le mot important "consécutif" est passé de l’autre côté de moi!
Toby Speight le
2

Perl 6 , 38 octets

->\n{map {|(2**$_-1 X+<0..n-$_)},1..n}

Comment ça marche

->\n{                                }  # A lambda with argument n.
                                 1..n   # Numbers from 1 to n.
     map {                     },       # Replace each one with a list:
            2**$_-1                     #   2 to that power minus 1,
                    X+<                 #   bit-shifted to the left by each element of
                       0..n-$_          #   the range from 0 to n minus the number.
          |(                  )         #   Slip the list into the outer list.

C'est-à-dire qu'il construit les nombres comme ceci:

1 2 4 8 = (2^1)-1 bit-shifted to the left by 0 1 2 3 places
3 6 12  = (2^2)-1 bit-shifted to the left by 0 1 2   places
7 14    = (2^3)-1 bit-shifted to the left by 0 1     places
15      = (2^4)-1 bit-shifted to the left by 0       places      n rows
                                                  
             n                                     n-1

Le code:


Perl 6 , 44 octets

->\n{map {|(2**$_-1,* *2...^*>2**n-1)},1..n}

C’était ma première approche avant de penser à la solution de transfert de bits (en réalité plus simple) ci-dessus.

Comment ça marche

->\n{                                      }  # A lambda with argument n.
                                       1..n   # Numbers from 1 to n.
     map {                           }        # Replace each one with:
            2**$_-1                              # 2 to that power minus 1,
                   ,* *2                         # followed by the result of doubling it,
                        ...^                     # repeated until (but not including)
                            *>2**n-1             # it's larger than 2^n-1.
          |(                        )            # Slip the list into the outer list.

C'est-à-dire qu'il construit les nombres comme ceci:

1 2 4 8 = (2^1)-1, times 2, times 2, times 2
3 6 12  = (2^2)-1, times 2, times 2
7 14    = (2^3)-1, times 2
15      = (2^4)-1                                 n rows
                                    
             n                       as many columns as possible in
                                     each row without exceeding (2^n)-1
smls
la source
2

Haskell 59 46 octets

J'ai commencé avec f n=[0..n]>>= \b->take(n-b).iterate(*2).sum.map(2^)$[0..b]

de la réponse de nimi ci-dessus a gagné la perspicacité qui sum.map(2^)$[0..x]peut être condensée à2^x-1

Finir avec

e n=[1..n]>>= \x->map(\y->2^y*(2^x-1))[0..n-x]

[1..n] - liste avec le nombre de bits consécutifs que nous voulons parcourir`

>> = --roughly traduit pour chaque élément de la liste de gauche, le passer à la fonction de droite et concaténer tous les résultats

\ x -> - déclaration de fonction lambda avec un argument

carte xy - applique la fonction x à tous les membres de la liste y

Dans notre cas x = (\ y-> 2 ^ y * (2 ^ x-1)) - une autre fonction lambda 2 ^ y * (2 ^ x-1)). Cette formule découle de la multiplication par deux en ajoutant un zéro à droite en binaire (exemple 0001 à 0010). 2 ^ x - 1 est le nombre de bits avec lequel nous travaillons. Donc, pour 11, nous avons 2 ^ 0 * 3 (c'est-à-dire qu'il ne faut pas changer du tout) == 0011, puis 2 ^ 1 * 3 = 0110, puis 2 ^ 2 * 3 - 1100.

[0..nx] Construit la liste du nombre de fois où nous pouvons décaler les bits. Si nous travaillons avec un seul 1, puis sur 0001, nous souhaitons passer trois fois (4-1). Si nous travaillons deux 11 nous voulons 4-2 et ainsi de suite.

Brander
la source
2

Python 3, 59 octets

Note: ceci a été fait indépendamment des solutions de ovs et de Dennis , même si c'est très similaire aux deux.

lambda n:[(2<<i)-1<<j for i in range(n)for j in range(n-i)]

Comment ça marche:

for i in range(n)for j in range(n-i)  # Iterate over number of ones, then number of places
                                      # shifted over. i = ones, j = shifts

(2<<i)                                # Create a one followed by i zeroes
      -1                              # Subtract one from above to get i ones.
        <<j                           # Shift j places.

Essayez-le en ligne!

Les pourboires (codage et espèces) sont toujours les bienvenus!

Le numéro un
la source
2

Japt , 11 octets

o@o!²ãXÄ mx

Testez-le en ligne!

Explication

Ceci utilise assez bien l'approche de @ Dennis:

o@ o!²  ãXÄ  mx
oX{o!p2 ãX+1 mx}
                  // Implicit: U = input integer
oX{            }  // Create the range [0...U) and map each item X by this function:
   o              //   Create the range [0...U)
    !p2           //     and map each item Z to 2.p(Z); that is, 2**Z.
                  //     (p2 would map each item Z to Z.p(2); ! reverses the arguments.)
        ãX+1      //   Get all overlapping slices of length X + 1.
             mx   //   Map each of these slices Z through Z.x(); that is, sum each slice.
                  // Implicit: output result of last expression
ETHproductions
la source
2

PHP, 59 56 53 octets

for(;$p>($k*=2)?:($p=1<<$argn)>$k=$i+=$i+1;)echo$k,_;

prend les entrées de STDIN; courir avec -R.

panne

for(;$p>($k*=2)         // 3. inner loop: shift-0 $k while $k<$p (false in first iteration)
    ?:
    ($p=1<<$argvn)      // 1. init $p=2^N, outer loop:
    >$k=$i+=$i+1        // 2. shift-1 $i while $i<$p, init $k to new $i
;)
    echo$k,_;           // 4. print $k
Titus
la source
Vous pouvez utiliser une $argntrès bonne idée. Après avoir lu la question, j'ai en tête une solution de plus de 200 octets
Jörg Hülsermann
@ JörgHülsermann Merci de me rappeler STDIN. J'adore fusionner des boucles.
Titus
1

J , 19 octets

(0-.~&,>:+/\2&^)@i.

Ceci utilise la même méthode dans la solution de @Dennis .

Essayez-le en ligne!

Explication

(0-.~&,>:+/\2&^)@i.  Input: integer n
                 i.  Range [0, 1, ..., n-1]
(              )@    Operate on that range
            2&^        Compute 2^x for each x in that range
       >:              Increment each in that range
           \           For each overlapping sublist of size (previous) in powers of 2
         +/              Reduce by addition
 0                     The constant 0
     &,                Flatten each
  -.~                  Remove zeroes
milles
la source
1

Python 3, 91 octets

a=int(input())
print(*[int('1'*-~b,2)<<c for b in range(a)for c in range(a-b)],sep=', ')

Programme complet, avec sortie séparée par des virgules + espaces, comme spécifié.

Explication:

La notation étoile décompresse les listes. Ainsi print(*[1,2,3])est la même chose que print(1,2,3). Passez au int()constructeur une chaîne de '1 consécutifs.

-~b évalue à b+1 , mais vous n'avez pas à l'entourer de crochets pour multiplier une chaîne.

Décalage binaire de l'entier produit un nombre croissant de fois. print()a l'argument optionnel sep, spécifiant la chaîne à insérer entre chaque élément de la liste décompressée.

mypetlion
la source
2
Vous pouvez simplement imprimer la liste. Le format de sortie n'est pas si strict.
mbomb007
1

Java 7, 108 octets

static void x(int i){int a=0,t=1<<i,b;while((a=(a<<1)+1)<t){b=a;do System.out.println(b);while((b<<=1)<t);}}

Double la valeur initiale tant que le résultat est inférieur à 2^n. Ensuite, met à jour la valeur initiale (initial_value * 2) + 1et recommence à partir de là jusqu'à ce qu'elle atteigne (2^n)-1.

par exemple pour n=4:

0001 -> init
0010
0100
1000
return, double init and add one
0011 -> init
0110
1100
return, double init and add one
0111 -> init
1110
return, double init and add one
1111 -> init
done

Essayez-le en ligne!

QBrute
la source
1

Ruby, 50 octets

->r{1.upto(r){|x|p a=2**x-1;p a while(a*=2)<2**r}}

J'ai essayé des approches "intelligentes", mais cela semble être la plus courte (suivez littéralement les instructions)

Explication:

Chaque itération commence par 2 ^ n-1 et se multiplie par 2 jusqu'à ce que la limite supérieure soit atteinte. Rien d'extraordinaire, juste des mathématiques de base.

GB
la source
1

QBIC , 37 octets - bonus imaginaire = encore 37 octets ...

:[a|e=2^b-1┘while e<2^a┘?e┘e=e*2┘wend

Dommage que je n'ai pas encore intégré while-wendQBIC ... Explication:

:       Get N from the command line
[a|     For b = 1 to N; The sequence is reset N times
e=2^b-1 Set the first number of this sub-sequence (yields 1, 3, 7, 15 ...)
┘       Line-break - syntactic separation of commands because there's no command for WHILE yet.
while   Pure QBasic code - lower-case is not (really) interpreted by QBIC
e<2^a   Continue as long as we don't exceed the maximum value
┘?e     Print the number in the sequence
┘e=e*2  Double the number
┘wend   And loop as long as we're not exceeding maximum, reset the sequence otherwise.
        FOR loop auto-closed by QBIC

EDIT: QBIC a maintenant un support pour WHILE:

:[a|e=2^b-1≈e<2^a|?e┘e=e*2

Ce n'est que 26 octets! Voici le WHILE:

≈e<2^a|          ≈ = WHILE, and the TRUE condition is everything up to the |
       ...       Loop code goes here
          ]      Close construct: adds a WEND instruction
                 In the program above, this is done implicitly because of EOF.
Steenbergh
la source
1

MATL, 19 18 octets

1 octet enregistré grâce à @Luis

:q2w^XJfP"J@YC2&sv

Essayez-le en ligne

Suever
la source
1
@ LuisMendo très intelligent! Merci
Suever
1

R , 69 48 46 octets

n=scan();for(i in 1:n)print((2^i-1)*2^(i:n-i))

Chaque nombre décimal correspondant à i in 1..nceux du système binaire est multiplié par2^(0..n-i) , c'est-à-dire les premières n-i+1puissances de deux (1, 2, 4, ...).

Essayez-le en ligne!

Robert Hacken
la source
1

Stax , 9 octets

übg▓}╥é►╪

Exécuter et déboguer en ligne!

Explication

Bonus imaginaire si quelqu'un le fait sans aucune forme de conversion de base (en utilisant de vieux maths simples).

Eh bien, il n’ya pas de conversion de base ici.

Utilise la version décompressée (10 octets) pour expliquer.

m|2vx_-DQH
m             For input=`n`, loop over `1..n`
 |2v          Power of two minus one
    x_-D      Do `n-j` times, where `j` is the current 1-based loop index
        Q     Output the current value
         H    And double it
Weijun Zhou
la source
0

Lot, 92 - 0 = 92 octets

@for /l %%i in (1,1,%1)do @for /l %%j in (%%i,1,%1)do @cmd/cset/a"(1<<%%i)-1<<%%j-%%i"&echo(

Soustraire 0 pour le bonus imaginaire de @ StewieGriffin.

Neil
la source