Números de saída até 2 ^ n-1, "classificados"

38

Tome um número inteiro positivo n como entrada e dê saída (alguns dos) números decimais que podem ser criados usando n bits, ordenados da seguinte maneira:

Primeiro, liste todos os números que podem ser criados com apenas um 1e o restante 0na representação binária (classificada), depois todos os números que podem ser criados com dois consecutivos 1 , o restante 0, depois três consecutivos 1 e assim por diante.

Vamos ver como é isso para n = 4 :

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

Portanto, a saída para n = 4 é: 1, 2, 4, 8, 3, 6, 12, 7, 14, 15 (formato de saída opcional).

Casos de teste:

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

Isso é , então o código mais curto em cada idioma vence!

Boas explicações são altamente encorajadas , também para soluções em "idiomas regulares"!

Stewie Griffin
fonte
2
@ zeppelin Eu também pensava assim no começo, mas este é muito diferente.
ETHproductions
1
Relacionado. (Ligeiramente).
Martin Ender
6
Bônus imaginário se alguém fizer isso sem nenhuma forma de conversão básica (usando simples matemática antiga).
Stewie Griffin
Escrevi isso, que é uma mistura entre os dois, eu acho. Experimente online!
PrincePolka

Respostas:

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)

Experimente online!

A função recursiva gera a lista classificada como uma pré-ordem percorrida nesta árvore (exemplo com n=4):

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

1 2 4 8 3 6 12 7 14 15

As ramificações esquerdas dobram o valor, e as ramificações direitas i->i*2+1existem e existem apenas para ímpares i. Portanto, a caminhada de pré-encomenda para não-folhas é T(i)=[i]+T(i*2)+i%2*T(i*2+1).

A árvore termina em profundidade n, onde nestá a entrada. Isso é obtido decrementando na cada passo e parando quando é 0.

Uma estratégia alternativa seria terminar com valores que iexcedam 2**n, em vez de rastrear a profundidade. Eu achei que esse fosse um byte a mais:

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
fonte
4
Uau. Não é apenas um truque muito legal / inteligente, mas é extremamente eficaz. +1, resposta muito boa!
DJMcMayhem
2
O [f]toque é divertido, não posso dizer que já vi isso antes.
FryAmTheEggman
18

Gelatina , 6 bytes

Ḷ2*ẆS€

Isso se qualifica para o bônus imaginário .

Experimente online!

Como 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
fonte
1
é um componente ideal para esse desafio e é implementado para que os resultados estejam na ordem certa para esse desafio. Bem feito :-)
ETHproductions
Não são esses 12 bytes (pelo menos em UTF-8)?
Gareth
1
@Gareth Sim, mas o Jelly também suporta um conjunto de caracteres de byte único , que contém os únicos 256 símbolos que entende.
Dennis
9

Mathematica, 40 bytes

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

Cada número na lista desejada é a diferença de duas potências de 2; portanto, simplesmente as geramos em ordem, usando Tablee achatando a lista. Eu acho que isso ganha o bônus imaginário de Stewie Griffin :)

Mathematica, 35 bytes

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

Uma porta do algoritmo Jelly de Dennis . Eu não sabia Subsequencesantes disso! (Também não vi que as milhas haviam postado essa resposta exata ... vá com uma votação!)

Greg Martin
fonte
1
Nota: Esta solução é idêntica ao código Mathematica de @mile , publicado 5 horas antes da edição de @GregMartin. No entanto, por meta consenso , essa resposta ainda é válida.
JungHwan Min
Ugh, eu não vi isso - obrigado por apontar.
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)

Um programa completo que recebe informações por meio de um prompt e alerta cada número em sucessão. Isso também se qualifica para o bônus imaginário .

Snippet de teste

(Nota: usa em console.logvez de alert)

ETHproductions
fonte
Sugestão (depois de verificar "não mostrar mais pop-ups"): Altere para console.log para o trecho de teste.
Tejas Kale
@TejasKale Boa ideia, obrigado!
ETHproductions
7

JavaScript (ES6), 55 51 bytes

Retorna uma lista separada por espaços de números inteiros.

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

Bônus imaginário amigável.

Formatado e 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 teste

Arnauld
fonte
6

Python 2 , 64 61 bytes

-3 bytes graças a Dennis

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

Experimente online!

Cajado
fonte
6

Mathematica, 35 bytes

Tr/@Rest@Subsequences[2^Range@#/2]&
milhas
fonte
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]

Experimente online!

Dennis
fonte
1
Passei uma hora inventando essa fórmula (2<<i)-1<<j... e você já descobriu. Bom trabalho! Além disso, bom trabalho em se livrar das faixas duplas
TheNumberOne
4

Haskell, 47 bytes

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

Exemplo de uso: f 4-> [1,2,4,8,3,6,12,7,14,15]. Experimente online! .

Como funciona: para cada número bem [1..n], comece com 2^b-1e repetidamente dobrar o valor e tomar n-b+1elementos desta lista.

nimi
fonte
4

Groovy, 90 89 bytes

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

A conversão binária é tão burra no groovy.

-1 graças a Gurupad Mamadapur

Urna de polvo mágico
fonte
3
Clichê de conversão binária de 28 bytes, tão doloroso.
Magic Octopus Urn
1
{(1..<2**it)...salva um byte.
Gurupad Mamadapur
3

Utilitários Bash + Unix, 51 bytes

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

Experimente online!

A entrada n é passada em um argumento.

Use seq para imprimir todos os números com n ou menos dígitos. (Estes são os números da base 10, portanto, existem muitos números extras aqui. É um desperdício e consome tempo, mas isso é código de golfe!)

A chamada para grep mantém apenas os números que consistem precisamente em 1s seguidos por 0s.

Em seguida, use sort -r para classificá-los em ordem lexicográfica reversa.

Por fim, dc está definido como entrada de base 2 - empurra os números classificados em uma pilha e depois imprime a pilha de cima para baixo. (Isso imprime o último item enviado primeiro, etc., e é por isso que estou usando sort -r em vez de apenas sort.)

Corrigido um erro: eu havia omitido a opção -f% .f para seq, necessária para contagens de números inteiros a partir de 1000000 em diante. (Agradecemos a @TobySpeight por apontar que havia um problema.)

Mitchell Spector
fonte
" Desperdício e demorado " ... e inteligente ! Obrigado por isso - é um bom lembrete de ignorar deliberadamente a eficiência computacional ao jogar golfe. Isso é realmente difícil quando você passar o resto de seus dias escrevendo rápido e código claro ...
Toby Speight
Alguns valores estão faltando: dc<<<2i`seq $[10**7-1]|grep ^1*0*$|sort -r`f | wc -relata apenas 12 valores. Eu acho que você quer, em grep ^1[01]*$vez disso.
Toby Speight
@ TobySpeight Obrigado - houve um erro que eu corrigi. O problema não estava na regex; a questão era que seq exigia uma opção. (Não sei por que você estava obtendo apenas 12 valores de saída - mesmo a versão incorreta produziu 21 valores em vez dos 28 corretos. .) Eu testei isso no Linux e no OS X agora.
Mitchell Spector
1
Na verdade, eu não entendi bem a pergunta - a palavra importante "consecutiva" de alguma forma passou direto por mim!
precisa
2

Perl 6 , 38 bytes

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

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

Ou seja, constrói os números assim:

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

O código:


Perl 6 , 44 bytes

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

Essa foi a minha primeira abordagem antes de pensar na solução de mudança de bits (na verdade mais simples) acima.

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

Ou seja, constrói os números assim:

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

Haskell 59 46 Bytes

Eu comecei com f n=[0..n]>>= \b->take(n-b).iterate(*2).sum.map(2^)$[0..b]

da resposta de nimi acima ganhou o insight que sum.map(2^)$[0..x]pode ser condensado até2^x-1

Terminando com

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

[1..n] - lista com o número de bits consecutivos que queremos percorrer`

>> = - traduzido aproximadamente para cada elemento da lista à esquerda, passe-o para a função à direita e concatene todos os resultados

\ x -> - declaração da função lambda com um argumento

map xy - aplica a função x a todos os membros da lista y

No nosso caso x = (\ y-> 2 ^ y * (2 ^ x-1)) - outra função lambda 2 ^ y * (2 ^ x-1)). Essa fórmula surge da multiplicação por duas adicionando um zero à direita em binário (exemplo 0001 a 0010). 2 ^ x - 1 é o número de bits com os quais estamos trabalhando. portanto, para 11, temos 2 ^ 0 * 3 (isto é, não mude nada) == 0011, então 2 ^ 1 * 3 = 0110 e, em seguida, 2 ^ 2 * 3-1100.

[0..nx] Cria a lista de quantas vezes podemos mudar os bits. Se estivermos trabalhando com um único 1, olhando para 0001, queremos mudar 3 vezes (4-1). Se estamos trabalhando com dois 11, queremos 4-2 e assim por diante.

brander
fonte
2

Python 3, 59 bytes

Nota: isso foi feito independentemente das soluções de ovs e de Dennis , embora seja muito semelhante a ambas.

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

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

Experimente online!

Dicas (codificação e dinheiro) são sempre bem-vindas!

O número um
fonte
2

Japonês , 11 bytes

o@o!²ãXÄ mx

Teste online!

Explicação

Isso praticamente usa a abordagem 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
fonte
2

Python , 61 59 bytes

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

Experimente online!

ovs
fonte
2

PHP, 59 56 53 bytes

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

recebe entrada do STDIN; corra com -R.

demolir

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
fonte
Você pode usar $argnmuito boa ideia. Depois de ler a pergunta que eu tenho na minha cabeça uma solução com mais de 200 Bytes
Jörg Hülsermann
@ JörgHülsermann Obrigado por me lembrar de STDIN. Eu simplesmente amo mesclar loops.
Titus
1

J , 19 bytes

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

Isso usa o mesmo método na solução @Dennis ' .

Experimente online!

Explicação

(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
milhas
fonte
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, com saída separada por vírgula + espaço, conforme especificado.

Explicação:

A notação em estrela descompacta as listas. Então print(*[1,2,3])é o mesmo que print(1,2,3). Passe ao int()construtor uma sequência de '1's consecutivos.

-~bavalia como b+1, mas você não precisa cercá-lo entre colchetes ao multiplicar uma sequência.

Bitshift o número inteiro produzido um número crescente de vezes. print()possui o argumento sep opcional, especificando a sequência a ser inserida entre cada item em uma lista descompactada.

mypetlion
fonte
2
Você pode apenas imprimir a lista. O formato de saída não é tão rigoroso.
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);}}

Dobra o valor inicial desde que o resultado seja menor que 2^n. Posteriormente, atualiza o valor inicial a ser (initial_value * 2) + 1e inicia novamente a partir daí até que finalmente chegue (2^n)-1.

por exemplo, 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

Experimente online!

QBrute
fonte
1

Ruby, 50 bytes

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

Tentei algumas abordagens "inteligentes", mas essa parece ser a mais curta (literalmente, siga as instruções)

Explicação:

Cada iteração começa com 2 ^ n-1 e multiplica por 2 até que o limite superior seja atingido. Nada extravagante, apenas matemática básica.

GB
fonte
1

QBIC , 37 bytes - bônus imaginário = ainda 37 bytes ...

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

Pena que ainda não while-wendintegrei o QBIC ... Explicação:

:       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 agora tem suporte para WHILE:

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

Isso é apenas 26 bytes! Aqui está o 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
fonte
1

MATL, 19 18 bytes

1 byte salvo graças a @Luis

:q2w^XJfP"J@YC2&sv

Experimente Online

Suever
fonte
1
@LuisMendo muito esperto! Obrigado
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 correspondente aos do i in 1..nsistema binário é multiplicado por 2^(0..n-i), ou seja, primeiras n-i+1potências de dois (1, 2, 4, ...).

Experimente online!

Robert Hacken
fonte
1

Stax , 9 bytes

übg▓}╥é►╪

Execute e depure online!

Explicação

Bônus imaginário se alguém fizer isso sem nenhuma forma de conversão básica (usando simples matemática antiga).

Bem, não há conversão básica aqui.

Usa a versão descompactada (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
fonte
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(

Subtraindo 0 para o bônus imaginário de @ StewieGriffin.

Neil
fonte