Output angka hingga 2 ^ n-1, "diurutkan"

38

Ambil bilangan bulat positif n sebagai input, dan hasilkan (beberapa) angka desimal yang dapat dibuat menggunakan n bit, diurutkan dengan cara berikut:

Pertama daftar semua angka yang dapat dibuat hanya dengan satu 1, dan sisanya 0di representasi biner (diurutkan), lalu semua angka yang dapat dibuat dengan dua berturut-turut 1 , sisanya 0, lalu tiga berturut 1 - turut dan seterusnya.

Mari kita lihat seperti apa bentuk ini untuk n = 4 :

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

Jadi, output untuk n = 4 adalah: 1, 2, 4, 8, 3, 6, 12, 7, 14, 15 (format output opsional).

Kasus uji:

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

Ini adalah , jadi kode terpendek di setiap bahasa menang!

Penjelasan yang baik sangat dianjurkan , juga untuk solusi dalam "bahasa reguler"!

Stewie Griffin
sumber
Sebuah dup dari codegolf.stackexchange.com/q/98322/61904 ?
zeppelin
2
@ zeppelin Saya juga berpikir begitu pada awalnya, tetapi yang ini sangat berbeda.
ETHproduksi
1
Terkait (Sedikit.)
Martin Ender
6
Bonus imajiner jika seseorang melakukan ini tanpa bentuk konversi basis (menggunakan matematika lama biasa).
Stewie Griffin
Tulis ini yang merupakan campuran antara keduanya Saya kira Coba online!
PrincePolka

Jawaban:

38

Python , 53 byte

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

Cobalah online!

Fungsi rekursif menghasilkan daftar yang disortir sebagai pre-order walk down tree ini (contoh dengan n=4):

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

1 2 4 8 3 6 12 7 14 15

Cabang kiri menggandakan nilainya, dan cabang kanan melakukan i->i*2+1dan ada hanya untuk ganjil i. Jadi, jalan pre-order untuk non-daun adalah T(i)=[i]+T(i*2)+i%2*T(i*2+1).

Pohon berakhir di kedalaman n, di mana ninput. Ini dicapai dengan mengurangi nsetiap langkah ke bawah dan berhenti ketika itu 0.

Strategi alternatif adalah untuk mengakhiri nilai-nilai yang imelebihi 2**n, daripada melacak kedalaman. Saya menemukan ini satu byte lebih lama:

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)
Tidak
sumber
4
Wow. Tidak hanya itu trik yang sangat keren / pintar, tetapi juga sangat efektif. +1, jawaban yang sangat bagus!
DJMcMayhem
2
Itu [f]adalah sentuhan yang lucu, tidak bisa mengatakan saya pernah melihatnya sebelumnya.
FryAmTheEggman
18

Jelly , 6 byte

Ḷ2*ẆS€

Ini memenuhi syarat untuk bonus imajiner .

Cobalah online!

Bagaimana itu bekerja

Ḷ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
sumber
1
adalah built-in yang ideal untuk tantangan ini, dan itu diterapkan sehingga hasilnya berada dalam urutan yang tepat untuk tantangan ini. Bagus sekali :-)
ETHproduk
Bukankah ini 12 byte (setidaknya dalam UTF-8)?
Gareth
1
@ Gareth Ya, tetapi Jelly juga mendukung satu set karakter byte tunggal , yang berisi hanya 256 simbol yang dimengerti.
Dennis
9

Mathematica, 40 byte

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

Setiap angka dalam daftar yang diinginkan adalah selisih dua kekuatan 2, jadi kami cukup membuatnya dalam rangka menggunakan Tabledan kemudian meratakan daftar. Saya pikir ini menghasilkan bonus imajiner Stewie Griffin :)

Mathematica, 35 byte

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

Port algoritme Dennis's Jelly . Saya tidak tahu tentang Subsequencesini sebelumnya! (Saya juga tidak melihat bahwa mil telah mengirimkan jawaban yang tepat ini ... lanjutkan!)

Greg Martin
sumber
1
Catatan: Solusi ini identik dengan kode Mathematica @mile , yang diposting 5 jam sebelum edit @GregMartin. Namun, per konsensus meta , jawaban ini masih valid.
JungHwan Min
Ugh, aku tidak melihat itu — terima kasih sudah menunjukkannya.
Greg Martin
8

JavaScript (ES6), 59 58 55 byte

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

Program lengkap yang menerima input melalui prompt dan memberi tahu setiap nomor secara berurutan. Ini juga memenuhi syarat untuk bonus imajiner .

Cuplikan tes

(Catatan: gunakan console.logbukan alert)

Produksi ETH
sumber
Saran (setelah memeriksa "jangan tampilkan munculan lagi"): Ubah ke console.log untuk cuplikan uji.
Tejas Kale
@TejasKale Ide bagus, terima kasih!
ETHproduk
7

JavaScript (ES6), 55 51 byte

Mengembalikan daftar bilangan bulat yang dipisahkan oleh ruang.

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

Bonus imajiner ramah.

Diformat dan dikomentari

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

Uji kasus

Arnauld
sumber
6

Python 2 , 64 61 byte

-3 byte terima kasih kepada Dennis

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

Cobalah online!

tongkat
sumber
6

Mathematica, 35 byte

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

Python 2 , 65 63 58 byte

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

Cobalah online!

Dennis
sumber
1
Saya baru saja menghabiskan satu jam membuat formula itu (2<<i)-1<<j... dan Anda sudah menemukan jawabannya. Kerja bagus! Juga, pekerjaan yang baik untuk menyingkirkan rentang ganda
TheNumberOne
4

Haskell, 47 byte

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

Contoh penggunaan: f 4-> [1,2,4,8,3,6,12,7,14,15]. Cobalah online!.

Cara kerjanya: untuk setiap angka bdalam [1..n], mulailah dengan 2^b-1dan gandakan nilai berulang kali dan ambil n-b+1elemen dari daftar ini.

nimi
sumber
4

05AB1E , 6 byte

L<oΎO

Cobalah online! atau sebagai Test suite

Penjelasan

Menggunakan trik daftar-jumlah seperti yang ditunjukkan dalam jawaban Dennis 'Jelly

L       # range [1 ... input]
 <      # decrement each
  o     # raise 2 to each power
   Œ    # get all sublists
    é   # sort by length
     O  # sum
Emigna
sumber
4

Groovy, 90 89 byte

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

Konversi biner begitu bodoh di groovy.

-1 terima kasih kepada Gurupad Mamadapur

Guci Gurita Ajaib
sumber
3
28 byte konversi biner boilerplate, sangat menyakitkan.
Magic Octopus Mm
1
{(1..<2**it)...menghemat satu byte.
Gurupad Mamadapur
3

Utilitas Bash + Unix, 51 byte

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

Cobalah online!

Input n diteruskan dalam argumen.

Gunakan seq untuk mencetak semua angka dengan n atau lebih sedikit digit. (Ini adalah angka dasar-10, jadi ada banyak angka tambahan di sini. Ini boros dan memakan waktu, tapi ini kode golf!)

Panggilan untuk grep hanya menyimpan angka-angka yang terdiri dari 1s diikuti oleh 0s.

Kemudian gunakan sort -r untuk mengurutkan ini dalam urutan leksikografis terbalik.

Akhirnya, dc diatur ke input basis 2 - mendorong angka yang diurutkan pada tumpukan dan kemudian mencetak tumpukan dari atas ke bawah. (Ini mencetak item terakhir yang didorong pertama kali, dll., Itulah sebabnya saya menggunakan sort -r bukan hanya sortir.)

Memperbaiki bug: Saya telah menghilangkan opsi -f% .f ke seq, yang diperlukan untuk penghitungan bilangan bulat dari 1000000 pada. (Terima kasih kepada @TobySpeight untuk menunjukkan bahwa ada masalah.)

Mitchell Spector
sumber
" Boros dan menyita waktu " ... dan pintar ! Terima kasih untuk ini - ini adalah pengingat yang baik untuk sengaja mengabaikan efisiensi komputasi saat bermain golf. Itu sangat sulit ketika Anda menghabiskan sisa hari-hari Anda menulis kode yang cepat dan jelas ...
Toby Speight
Beberapa nilai hilang: dc<<<2i`seq $[10**7-1]|grep ^1*0*$|sort -r`f | wc -hanya melaporkan 12 nilai. Saya pikir Anda ingin yang grep ^1[01]*$sebaliknya.
Toby Speight
@TobySpeight Terima kasih - ada bug, yang saya koreksi. Masalahnya bukan dengan regex; masalahnya adalah seq membutuhkan opsi. (Saya tidak yakin mengapa Anda hanya mendapatkan 12 nilai keluaran - bahkan versi yang salah menghasilkan 21 nilai keluaran sebelum yang benar 28. Jika Anda menjalankan ini pada TIO, itu mungkin telah melampaui batas waktu 1 menit TIO 1 menit. .) Saya sudah menguji ini pada Linux dan OS X sekarang.
Mitchell Spector
1
Sebenarnya, saya salah paham pertanyaan - kata penting "berturut-turut" di sana entah bagaimana langsung melewati saya!
Toby Speight
2

Mathematica / Mathics , 69 bytes

{0,1}~Tuples~#~SortBy~Count@1/.n:{a=0...,1..,a}:>Print@Fold[#+##&,n]&

Cobalah online!

JungHwan Min
sumber
2

Perl 6 , 38 byte

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

Bagaimana itu bekerja

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

Yaitu itu membangun angka-angka seperti ini:

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

Kode:


Perl 6 , 44 byte

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

Ini adalah pendekatan pertama saya sebelum saya memikirkan solusi bit-shift (sebenarnya lebih sederhana) di atas.

Bagaimana itu bekerja

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

Yaitu itu membangun angka-angka seperti ini:

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
seseorang
sumber
2

Haskell 59 46 Bytes

Saya mulai dengan f n=[0..n]>>= \b->take(n-b).iterate(*2).sum.map(2^)$[0..b]

dari jawaban nimi di atas diperoleh wawasan yang sum.map(2^)$[0..x]bisa diringkas menjadi2^x-1

Berakhir dengan

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

[1..n] - daftar dengan jumlah bit berurutan yang ingin kami daur ulang`

>> = --diterjemahkan secara otomatis untuk setiap elemen dalam daftar di sebelah kiri, serahkan ke fungsi di sebelah kanan dan gabungkan semua hasil

\ x -> - deklarasi fungsi lambda dengan satu argumen

map xy - menerapkan fungsi x untuk semua anggota daftar y

Dalam kasus kami x = (\ y-> 2 ^ y * (2 ^ x-1)) - fungsi lambda lain 2 ^ y * (2 ^ x-1)). Rumus ini muncul dari perkalian dengan dua menambahkan nol ke kanan dalam biner (misalnya 0001 hingga 0010). 2 ^ x - 1 adalah jumlah bit yang kami kerjakan. jadi untuk 11 kita memiliki 2 ^ 0 * 3 (yaitu tidak bergeser sama sekali) == 0011, kemudian 2 ^ 1 * 3 = 0110 kemudian 2 ^ 2 * 3 - 1100.

[0..nx] Membuat daftar berapa kali kami dapat menggeser bit. Jika kita bekerja dengan satu 1 maka melihat 0001 kita ingin bergeser 3 kali (4-1). Jika kita bekerja dua 11 kita ingin 4-2 dan seterusnya.

brander
sumber
2

Python 3, 59 byte

Catatan: ini dibuat secara terpisah dari solusi ovs dan Dennis , meskipun sangat mirip dengan keduanya.

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

Bagaimana itu bekerja:

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.

Cobalah online!

Tips (baik coding dan uang tunai) selalu diterima!

TheNumberOne
sumber
2

Japt , 11 byte

o@o!²ãXÄ mx

Uji secara online!

Penjelasan

Ini cukup banyak menggunakan pendekatan @ 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
Produksi ETH
sumber
2

Python , 61 59 byte

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

Cobalah online!

ovs
sumber
2

PHP, 59 56 53 byte

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

menerima input dari STDIN; jalankan bersama -R.

kerusakan

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
sumber
Anda dapat menggunakan $argnide yang sangat bagus. Setelah membaca pertanyaan yang saya miliki di kepala saya solusi dengan lebih dari 200 Bytes
Jörg Hülsermann
@ JörgHülsermann Terima kasih telah mengingatkan saya pada STDIN. Saya suka menggabungkan loop.
Titus
1

J , 19 byte

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

Ini menggunakan metode yang sama dalam solusi @Dennis .

Cobalah online!

Penjelasan

(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
mil
sumber
1

Python 3, 91 byte

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

Program lengkap, dengan output yang dipisahkan koma + ruang, seperti yang ditentukan.

Penjelasan:

Notasi bintang membongkar daftar. Begitu print(*[1,2,3])juga dengan print(1,2,3). Berikan int()konstruktor string berturut-turut '1's.

-~bmengevaluasi b+1, tetapi Anda tidak harus mengelilinginya dengan tanda kurung saat mengalikan string.

Bitshift integer yang dihasilkan semakin banyak kali. print()memiliki argumen sep opsional, menentukan string untuk dimasukkan di antara setiap item dalam daftar yang belum dibongkar.

mypetlion
sumber
2
Anda cukup mencetak daftar. Format output tidak begitu ketat.
mbomb007
1

Java 7, 108 byte

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

Menggandakan nilai awal selama hasilnya lebih kecil dari 2^n. Setelah itu, perbarui nilai awal menjadi (initial_value * 2) + 1dan mulai lagi dari sana hingga akhirnya tercapai(2^n)-1 .

misalnya untuk 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

Cobalah online!

QBrute
sumber
1

Ruby, 50 byte

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

Saya mencoba beberapa pendekatan "pintar", tetapi ini tampaknya yang terpendek (secara harfiah mengikuti instruksi)

Penjelasan:

Setiap iterasi dimulai dengan 2 ^ n-1 dan dikalikan 2 hingga batas atas tercapai. Tidak ada yang mewah, hanya matematika dasar.

GB
sumber
1

QBIC , 37 byte - bonus imajiner = masih 37 byte ...

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

Sayang saya belum memiliki while-wendQBIC ... Penjelasan:

:       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 sekarang memiliki dukungan untuk WHILE :

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

Ini hanya 26 byte! Inilah 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
sumber
1

MATL, 19 18 byte

1 byte disimpan berkat @Luis

:q2w^XJfP"J@YC2&sv

Cobalah secara Online

Suever
sumber
1
@LuisMendo sangat pintar! Terima kasih
Suever
1

R , 69 48 46 byte

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

Setiap angka desimal yang sesuai dengan i in 1..nyang ada dalam sistem biner dikalikan dengan 2^(0..n-i), yaitu n-i+1kekuatan pertama dari dua (1, 2, 4, ...).

Cobalah online!

Robert Hacken
sumber
1

Stax , 9 byte

übg▓}╥é►╪

Jalankan dan debug online!

Penjelasan

Bonus imajiner jika seseorang melakukan ini tanpa bentuk konversi basis (menggunakan matematika lama biasa).

Ya, tidak ada konversi basis di sini.

Menggunakan versi yang belum dibongkar (10 byte) untuk menjelaskan.

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

Batch, 92 - 0 = 92 byte

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

Mengurangi 0 untuk bonus imajiner @ StewieGriffin.

Neil
sumber