Números de salida hasta 2 ^ n-1, "ordenados"

38

Tome un número entero positivo n como entrada y envíe (algunos de los) números decimales que se pueden crear usando n bits, ordenados de la siguiente manera:

Primero, enumere todos los números que se pueden crear con solo uno 1, y el resto 0en la representación binaria (ordenada), luego todos los números que se pueden crear con dos consecutivos 1 , el resto 0, luego tres consecutivos, 1 etc.

Veamos cómo se ve esto para n = 4 :

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

Entonces, la salida para n = 4 es: 1, 2, 4, 8, 3, 6, 12, 7, 14, 15 (formato de salida opcional).

Casos de prueba:

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

Este es el , por lo que gana el código más corto en cada idioma .

Se recomiendan buenas explicaciones , también para soluciones en "idiomas regulares".

Stewie Griffin
fuente
2
@zeppelin También lo pensé al principio, pero este es muy diferente.
ETHproductions
1
Relacionado. (Ligeramente)
Martin Ender
66
Bonificación imaginaria si alguien hace esto sin ninguna forma de conversión de base (usando matemáticas antiguas).
Stewie Griffin
Escribí esto, que es una mezcla entre los dos, supongo ¡ Pruébalo en línea!
PrincePolka

Respuestas:

38

Python , 53 bytes

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

Pruébalo en línea!

La función recursiva genera la lista ordenada como un pedido anticipado de este árbol (ejemplo con n=4):

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

1 2 4 8 3 6 12 7 14 15

Las ramas izquierdas duplican el valor, y las ramas derechas i->i*2+1existen y existen solo para impar i. Entonces, la caminata de pre-orden para las no hojas es T(i)=[i]+T(i*2)+i%2*T(i*2+1).

El árbol termina en profundidad n, donde nestá la entrada. Esto se logra disminuyendo ncon cada paso hacia abajo y deteniéndose cuando es 0.

Una estrategia alternativa sería terminar con valores que iexceden 2**n, en lugar de seguir la profundidad. Encontré que esto es un byte más:

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
fuente
44
Guau. No solo es un truco realmente genial / inteligente, sino que es extremadamente efectivo. +1, muy buena respuesta!
DJMcMayhem
2
El [f]es un toque divertido, no puedo decir que haya visto eso antes.
FryAmTheEggman
18

Jalea , 6 bytes

Ḷ2*ẆS€

Esto califica para el bono imaginario .

Pruébalo en línea!

Cómo funciona

Ḷ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
fuente
1
es un complemento ideal para este desafío, y se implementa para que los resultados estén en el orden correcto para este desafío. Bien hecho :-)
ETHproductions
¿No son estos 12 bytes (al menos en UTF-8)?
Gareth
1
@Gareth Sí, pero Jelly también admite un conjunto de caracteres de un solo byte , que contiene los únicos 256 símbolos que comprende.
Dennis
9

Mathematica, 40 bytes

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

Cada número en la lista deseada es la diferencia de dos potencias de 2, por lo que simplemente los generamos en orden usando Tabley luego aplanamos la lista. Creo que esto gana el bono imaginario de Stewie Griffin :)

Mathematica, 35 bytes

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

Un puerto del algoritmo Jelly de Dennis . ¡No lo sabía Subsequencesantes de esto! (Tampoco vi que millas habían publicado esta respuesta exacta ... ¡vota!)

Greg Martin
fuente
1
Nota: Esta solución es idéntica al código de Mathematica de @mile , publicado 5 horas antes de la edición de @GregMartin. Sin embargo, por meta consenso , esta respuesta sigue siendo válida.
JungHwan Min
Ugh, no lo vi, gracias por señalarlo.
Greg Martin
8

JavaScript (ES6), 59 58 55 bytes

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

Un programa completo que recibe información a través de un aviso y alerta cada número sucesivamente. Esto también califica para el bono imaginario .

Fragmento de prueba

(Nota: utiliza en console.loglugar de alert)

ETHproducciones
fuente
Sugerencia (después de tener que marcar "no mostrar más ventanas emergentes"): cambie a console.log para el fragmento de prueba.
Tejas Kale
@TejasKale Buena idea, gracias!
ETHproductions
7

JavaScript (ES6), 55 51 bytes

Devuelve una lista de enteros separados por espacios.

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

Bono imaginario amigable.

Formateado y comentado

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

Casos de prueba

Arnauld
fuente
6

Mathematica, 35 bytes

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

Python 2 , 65 63 58 bytes

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

Pruébalo en línea!

Dennis
fuente
1
Acabo de pasar una hora con esa fórmula (2<<i)-1<<j... y ya lo has descubierto. ¡Gran trabajo! Además, buen trabajo para deshacerse de los rangos dobles
TheNumberOne
4

Haskell, 47 bytes

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

Ejemplo de uso: f 4-> [1,2,4,8,3,6,12,7,14,15]. Pruébalo en línea! .

Cómo funciona: para cada número ben [1..n], comenzar con 2^b-1y doblar varias veces el valor y tomar n-b+1elementos de esta lista.

nimi
fuente
4

Groovy, 90 89 bytes

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

La conversión binaria es tan tonta en groovy.

-1 gracias a Gurupad Mamadapur

Urna de pulpo mágico
fuente
3
Repetitivo de conversión binaria de 28 bytes, muy doloroso.
Urna mágica del pulpo
1
{(1..<2**it)...Guarda un byte.
Gurupad Mamadapur
3

Utilidades Bash + Unix, 51 bytes

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

Pruébalo en línea!

La entrada n se pasa en un argumento.

Use seq para imprimir todos los números con no menos dígitos. (Estos son números de base 10, por lo que hay muchos números adicionales aquí. Es un desperdicio y consume mucho tiempo, ¡pero este es el código golf!)

La llamada a grep mantiene solo aquellos números que consisten precisamente en 1s seguidos de 0s.

Luego use sort -r para ordenarlos en orden lexicográfico inverso.

Finalmente, dc se establece en la entrada de base 2: empuja los números ordenados en una pila y luego imprime la pila de arriba a abajo. (Esto imprime el último elemento empujado primero, etc., por eso estoy usando sort -r en lugar de simplemente ordenar).

Se corrigió un error: había omitido la opción -f% .f a seq, que se requiere para el recuento de enteros desde 1000000 en adelante. (Gracias a @TobySpeight por señalar que hubo un problema).

Mitchell Spector
fuente
" Derrochador y lento " ... ¡e inteligente ! Gracias por esto: es un buen recordatorio para ignorar deliberadamente la eficiencia computacional cuando se juega al golf. Eso es realmente difícil cuando pasas el resto de tus días escribiendo código rápido y claro ...
Toby Speight
Faltan algunos valores: dc<<<2i`seq $[10**7-1]|grep ^1*0*$|sort -r`f | wc -solo informa 12 valores. Creo que quieres en su grep ^1[01]*$lugar.
Toby Speight
@TobySpeight Gracias: hubo un error que he corregido. El problema no era con la expresión regular; el problema era que seq requería una opción. (Sin embargo, no estoy seguro de por qué solo estaba obteniendo 12 valores de salida; incluso la versión incorrecta produjo 21 valores de salida en lugar de los 28 correctos. Si estaba ejecutando esto en TIO, es posible que haya excedido el límite de tiempo de 1 minuto de TIO .) He probado esto en Linux y OS X ahora.
Mitchell Spector
1
En realidad, no entendí la pregunta: ¡la palabra importante "consecutiva" de alguna manera me pasó de largo!
Toby Speight
2

Perl 6 , 38 bytes

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

Cómo funciona

->\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.

Es decir, construye los números así:

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

El código:


Perl 6 , 44 bytes

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

Este fue mi primer enfoque antes de pensar en la solución de cambio de bits (en realidad más simple) anterior.

Cómo funciona

->\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.

Es decir, construye los números así:

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
fuente
2

Haskell 59 46 Bytes

Empecé con f n=[0..n]>>= \b->take(n-b).iterate(*2).sum.map(2^)$[0..b]

de la respuesta anterior de nimi obtuvo la idea que sum.map(2^)$[0..x]se puede condensar a2^x-1

Terminando con

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

[1..n] - lista con el número de bits consecutivos que queremos recorrer`

>> = - traducido completamente para cada elemento en la lista de la izquierda, pásalo a la función de la derecha y concatena todos los resultados

\ x -> - declaración de función lambda con un argumento

map xy : aplica la función x a todos los miembros de la lista y

En nuestro caso x = (\ y-> 2 ^ y * (2 ^ x-1)) - otra función lambda 2 ^ y * (2 ^ x-1)). Esta fórmula surge de la multiplicación por dos agregando un cero a la derecha en binario (ejemplo 0001 a 0010). 2 ^ x - 1 es el número de bits con los que estamos trabajando. entonces para 11 tenemos 2 ^ 0 * 3 (es decir, no cambiar en absoluto) == 0011, luego 2 ^ 1 * 3 = 0110 luego 2 ^ 2 * 3 - 1100.

[0..nx] Construye la lista de cuántas veces podemos cambiar los bits. Si estamos trabajando con un solo 1, entonces mirando 0001 queremos cambiar 3 veces (4-1). Si estamos trabajando dos 11 queremos 4-2 y así sucesivamente.

brander
fuente
2

Python 3, 59 bytes

Nota: esto se hizo independientemente de las soluciones de ovs y Dennis , aunque es muy similar a ambas.

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

Cómo funciona:

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.

Pruébalo en línea!

¡Las propinas (codificación y efectivo) son siempre bienvenidas!

El numero uno
fuente
2

Japt , 11 bytes

o@o!²ãXÄ mx

¡Pruébelo en línea!

Explicación

Esto usa más o menos el enfoque 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
ETHproducciones
fuente
2

PHP, 59 56 53 bytes

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

toma entrada de STDIN; correr con -R.

Descompostura

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
fuente
Puedes usar $argnMuy buena idea. Después de leer la pregunta, tengo en mi cabeza una solución con más de 200 Bytes
Jörg Hülsermann
@ JörgHülsermann Gracias por recordarme STDIN. Me encanta fusionar bucles.
Tito el
1

J , 19 bytes

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

Esto usa el mismo método en @Dennis ' solución de .

Pruébalo en línea!

Explicación

(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
millas
fuente
1

Python 3, 91 bytes

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

Programa completo, con salida separada por comas y espacios, como se especifica.

Explicación:

La notación en estrella desempaqueta listas. Entonces print(*[1,2,3])es lo mismo que print(1,2,3). Pase al int()constructor una cadena de '1' consecutivos.

-~bevalúa a b+1, pero no tiene que rodearlo con corchetes al multiplicar una cadena.

Bitshift el número entero producido un número creciente de veces. print()tiene el argumento opcional sep, que especifica la cadena que se colocará entre cada elemento en una lista desempaquetada.

mypetlion
fuente
2
Simplemente puede imprimir la lista. El formato de salida no es tan estricto.
mbomb007
1

Java 7, 108 bytes

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);}}

Duplica el valor inicial siempre que el resultado sea menor que 2^n. Luego, actualiza el valor inicial a ser (initial_value * 2) + 1y comienza de nuevo desde allí hasta que finalmente alcanza(2^n)-1 .

por ejemplo para 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

Pruébalo en línea!

QBrute
fuente
1

Ruby, 50 bytes.

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

Intenté algunos enfoques "inteligentes", pero este parece ser el más corto (literalmente, siga las instrucciones)

Explicación:

Cada iteración comienza con 2 ^ n-1 y se multiplica por 2 hasta alcanzar el límite superior. Nada lujoso, solo matemática básica.

GB
fuente
1

QBIC , 37 bytes - bonificación imaginaria = todavía 37 bytes ...

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

Es una pena que aún no haya incorporado while-wendQBIC ... Explicación:

:       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

EDITAR: QBIC ahora tiene soporte para WHILE:

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

¡Esto es solo 26 bytes! Aquí está el 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
fuente
1

MATL, 19 18 bytes

1 byte guardado gracias a @Luis

:q2w^XJfP"J@YC2&sv

Pruébalo en línea

Suever
fuente
1
@LuisMendo muy inteligente! Gracias
Suever
1

R , 69 48 46 bytes

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

Cada número decimal correspondiente a i in 1..nunos en el sistema binario se multiplica por 2^(0..n-i), es decir, las primeras n-i+1potencias de dos (1, 2, 4, ...).

Pruébalo en línea!

Robert Hacken
fuente
1

Stax , 9 bytes

übg▓}╥é►╪

Ejecutar y depurar en línea!

Explicación

Bonificación imaginaria si alguien hace esto sin ninguna forma de conversión de base (usando matemáticas antiguas).

Bueno, no hay conversión de base aquí.

Utiliza la versión desempaquetada (10 bytes) para explicar.

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
fuente
0

Lote, 92-0 = 92 bytes

@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(

Restando 0 para la bonificación imaginaria de @ StewieGriffin.

Neil
fuente