Wyjściowe liczby do 2 ^ n-1, „posortowane”

38

Weź jako liczbę całkowitą dodatnią n i wyślij (niektóre z) liczby dziesiętne, które można utworzyć za pomocą n bitów, uporządkowane w następujący sposób:

Najpierw wypisz wszystkie liczby, które można utworzyć za pomocą tylko jednej 1, a pozostałe 0w reprezentacji binarnej (posortowane), a następnie wszystkie liczby, które można utworzyć za pomocą dwóch kolejnych 1 , reszty 0, a następnie trzech kolejnych 1 i tak dalej.

Zobaczmy, jak to wygląda dla n = 4 :

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

Zatem dane wyjściowe dla n = 4 to: 1, 2, 4, 8, 3, 6, 12, 7, 14, 15 (opcjonalny format wyjściowy).

Przypadki testowe:

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

To jest , więc wygrywa najkrótszy kod w każdym języku !

Zachęcamy do dobrych wyjaśnień , także dla rozwiązań w „zwykłych językach”!

Stewie Griffin
źródło
2
@zeppelin Na początku też tak myślałem, ale ten jest zupełnie inny.
ETHprodukcje
1
Związane z. (Nieznacznie.)
Martin Ender,
6
Wyimaginowany bonus, jeśli ktoś zrobi to bez jakiejkolwiek formy konwersji podstawowej (używając zwykłych starych matematyki).
Stewie Griffin,
Napisałem to, co jest mieszanką dwóch. Myślę, że wypróbuj online!
PrincePolka

Odpowiedzi:

38

Python , 53 bajty

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

Wypróbuj online!

Funkcja rekurencyjna generuje posortowaną listę jako spacer w dół tego drzewa (przykład z n=4):

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

1 2 4 8 3 6 12 7 14 15

Lewe gałęzie podwoją wartość, a prawe gałęzie i->i*2+1istnieją i istnieją tylko dla nieparzystych i. Tak więc spacer w przedsprzedaży dla osób niebędących liśćmi jest T(i)=[i]+T(i*2)+i%2*T(i*2+1).

Drzewo kończy się na głębokości n, gdzie njest wejście. Osiąga się to poprzez zmniejszanie nz każdym krokiem w dół i zatrzymywanie, gdy wynosi 0.

Alternatywną strategią byłoby kończenie na wartościach iprzekraczających 2**n, a nie śledzenie głębokości. Znalazłem to o jeden bajt dłużej:

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
źródło
4
Łał. To nie tylko naprawdę fajna / sprytna sztuczka, ale także niezwykle skuteczna. +1, naprawdę fajna odpowiedź!
DJMcMayhem
2
To [f]zabawny dotyk, nie mogę powiedzieć, że widziałem to wcześniej.
FryAmTheEggman
18

Galaretka , 6 bajtów

Ḷ2*ẆS€

To kwalifikuje się do wyimaginowanej premii .

Wypróbuj online!

Jak to działa

Ḷ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
źródło
1
jest idealnym rozwiązaniem dla tego wyzwania i jest zaimplementowany w taki sposób, aby wyniki były w odpowiedniej kolejności dla tego wyzwania. Dobra robota :-)
ETHproductions
Czy to nie jest 12 bajtów (przynajmniej w UTF-8)?
Gareth,
1
@Gareth Tak, ale Jelly obsługuje również zestaw znaków jednobajtowych , który zawiera tylko 256 symboli, które rozumie.
Dennis
9

Mathematica, 40 bajtów

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

Każda liczba na pożądanej liście jest różnicą dwóch potęg 2, więc po prostu generujemy je w kolejności, używając, Tablea następnie spłaszczając listę. Myślę, że to zarabia wymyśloną premię Stewie Griffin :)

Mathematica, 35 bajtów

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

Port algorytmu Jelnisa ​​Jelly . Nie wiedziałem o Subsequencestym wcześniej! (Nie widziałem też, żeby mile opublikowały tę dokładną odpowiedź ... idź to zagłosować!)

Greg Martin
źródło
1
Uwaga: To rozwiązanie jest identyczne z kodem Mathematica @mile opublikowanym 5 godzin przed edycją @GregMartin. Jednak zgodnie z meta konsensusem ta odpowiedź jest nadal aktualna.
JungHwan Min
Ugh, nie widziałem tego - dziękuję za zwrócenie na to uwagi.
Greg Martin
8

JavaScript (ES6), 59 58 55 bajtów

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

Pełny program, który pobiera dane z monitu i ostrzega kolejno o każdym numerze. To także kwalifikuje się do wyimaginowanej premii .

Testowy fragment kodu

(Uwaga: używa console.logzamiast alert)

ETHprodukcje
źródło
Sugestia (po sprawdzeniu „nie wyświetlaj więcej wyskakujących okienek”): Zmień na console.log dla fragmentu testowego.
Tejas Kale
@TejasKale Dobry pomysł, dzięki!
ETHprodukcje
7

JavaScript (ES6), 55 51 bajtów

Zwraca rozdzieloną spacjami listę liczb całkowitych.

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

Wyobrażony bonus przyjazny.

Sformatowane i skomentowane

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

Przypadki testowe

Arnauld
źródło
6

Python 2 , 64 61 bajtów

-3 bajty dzięki Dennisowi

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

Wypróbuj online!

Pręt
źródło
6

Mathematica, 35 bajtów

Tr/@Rest@Subsequences[2^Range@#/2]&
mile
źródło
5

Python 2 , 65 63 58 bajtów

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

Wypróbuj online!

Dennis
źródło
1
Właśnie spędziłem godzinę wymyślając tę ​​formułę (2<<i)-1<<j... a ty już to rozgryzłeś. Dobra robota! Dobra robota w pozbyciu się podwójnych zakresów
TheNumberOne
4

Haskell, 47 bajtów

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

Przykład użycia: f 4-> [1,2,4,8,3,6,12,7,14,15]. Wypróbuj online! .

Jak to działa: dla każdego numeru bw [1..n], początek 2^b-1i wielokrotnie podwoić wartość i zabrać n-b+1elementy z tej listy.

nimi
źródło
4

Groovy, 90 89 bajtów

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

Konwersja binarna jest tak głupia.

-1 dzięki Gurupad Mamadapur

Urna Magicznej Ośmiornicy
źródło
3
28-bajtowy bojler konwersji binarnej, taki bolesny.
Magic Octopus Urn
1
{(1..<2**it)...zapisuje bajt.
Gurupad Mamadapur
3

Narzędzia Bash + Unix, 51 bajtów

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

Wypróbuj online!

Dane wejściowe n są przekazywane w argumencie.

Użyj seq, aby wydrukować wszystkie liczby z n lub mniej cyframi. (Są to liczby podstawowe 10, więc jest tu wiele dodatkowych liczb. Jest to marnotrawstwo i czasochłonne, ale to jest golf golfowy!)

Wezwanie grep zachowuje tylko te liczby, które składają się dokładnie z 1, a następnie 0.

Następnie użyj sort -r, aby posortować je w odwrotnej kolejności leksykograficznej.

Na koniec, dc jest ustawiane na dane wejściowe podstawy 2 - wypycha posortowane liczby na stosie, a następnie drukuje stos od góry do dołu. (Spowoduje to wydrukowanie ostatniego elementu wypchniętego jako pierwszy itd., Dlatego używam sort -r zamiast sortować).

Poprawiony błąd: Pominąłem opcję -f% .f do seq, która jest wymagana dla liczb całkowitych od 1000000. (Podziękowania dla @TobySpeight za zwrócenie uwagi na problem.)

Mitchell Spector
źródło
Marnotrawstwo i czasochłonność ” ... i sprytne ! Dzięki za to - dobrym przypomnieniem jest celowe ignorowanie wydajności obliczeniowej podczas gry w golfa. To naprawdę trudne, gdy spędzasz resztę dni na pisaniu szybkiego i przejrzystego kodu ...
Toby Speight
Brak niektórych wartości: dc<<<2i`seq $[10**7-1]|grep ^1*0*$|sort -r`f | wc -zgłasza tylko 12 wartości. Myślę, że grep ^1[01]*$zamiast tego chcesz .
Toby Speight
@TobySpeight Dzięki - wystąpił błąd, który poprawiłem. Problem nie dotyczył wyrażenia regularnego; problemem było to, że seq wymagała opcji. (Nie jestem jednak pewien, dlaczego otrzymywałeś tylko 12 wartości wyjściowych - nawet niepoprawna wersja wygenerowała 21 wartości wyjściowych zamiast prawidłowych 28. Jeśli korzystałeś z tego na TIO, być może przekroczył 1-minutowy limit czasu TIO .) Testowałem to teraz zarówno w systemie Linux, jak i OS X.
Mitchell Spector,
1
Właściwie źle zrozumiałem pytanie - ważne słowo „konsekutywne” minęło mnie jak najbardziej!
Toby Speight,
2

Perl 6 , 38 bajtów

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

Jak to działa

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

To znaczy konstruuje takie liczby:

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

Kod:


Perl 6 , 44 bajtów

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

To było moje pierwsze podejście, zanim pomyślałem o (właściwie prostszym) rozwiązaniu z przesunięciem bitów powyżej.

Jak to działa

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

To znaczy konstruuje takie liczby:

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
źródło
2

Haskell 59 46 bajtów

Zacząłem od f n=[0..n]>>= \b->take(n-b).iterate(*2).sum.map(2^)$[0..b]

z powyższej odpowiedzi nich uzyskał wgląd, który sum.map(2^)$[0..x]można skondensować2^x-1

Kończąc z

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

[1..n] - lista z liczbą kolejnych bitów, przez które chcemy przechodzić`

>> = - przetłumaczone do końca dla każdego elementu na liście po lewej stronie, przekazujemy go do funkcji po prawej i łączymy wszystkie wyniki

\ x -> - deklaracja funkcji lambda z jednym argumentem

map xy - stosuje funkcję x do wszystkich członków listy y

W naszym przypadku x = (\ y-> 2 ^ y * (2 ^ x-1)) - kolejna funkcja lambda 2 ^ y * (2 ^ x-1)). Ta formuła wynika z mnożenia przez dwa dodawanie zera do binarnego (przykład 0001 do 0010). 2 ^ x - 1 to liczba bitów, z którymi pracujemy. więc dla 11 mamy 2 ^ 0 * 3 (tj. wcale nie przesuwaj) == 0011, następnie 2 ^ 1 * 3 = 0110, a następnie 2 ^ 2 * 3 - 1100.

[0..nx] Buduje listę, ile razy możemy przesunąć bity. Jeśli pracujemy z jednym 1, to patrząc na 0001, chcemy przesunąć 3 razy (4-1). Jeśli pracujemy dwa 11, chcemy 4-2 i tak dalej.

brander
źródło
2

Python 3, 59 bajtów

Uwaga: zostało to zrobione niezależnie od rozwiązań ovsa i Dennisa , mimo że jest bardzo podobne do obu.

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

Jak to działa:

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.

Wypróbuj online!

Wskazówki (zarówno kodowania, jak i gotówki) są zawsze mile widziane!

Numer jeden
źródło
2

Japt , 11 bajtów

o@o!²ãXÄ mx

Przetestuj online!

Wyjaśnienie

To w zasadzie wykorzystuje podejście @ Dennisa:

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
ETHprodukcje
źródło
2

Python , 61 59 bajtów

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

Wypróbuj online!

ovs
źródło
2

PHP, 59 56 53 bajtów

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

pobiera dane wejściowe ze STDIN; biegać z -R.

awaria

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
Tytus
źródło
Możesz użyć $argnBardzo dobry pomysł. Po przeczytaniu pytania mam w głowie rozwiązanie z ponad 200
bajtami
@ JörgHülsermann Dziękujemy za przypomnienie STDIN. Uwielbiam łączyć pętle.
Tytus
1

J , 19 bajtów

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

Używa tej samej metody w rozwiązaniu @Dennis .

Wypróbuj online!

Wyjaśnienie

(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
mile
źródło
1

Python 3, 91 bajtów

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

Pełny program, z wyjściem oddzielonym przecinkami i spacjami, jak określono.

Wyjaśnienie:

Notacja gwiazdowa rozpakowuje listy. Więc print(*[1,2,3])to samo co print(1,2,3). Przekaż int()konstruktorowi ciąg kolejnych „1”.

-~bocenia na b+1, ale nie musisz otaczać go nawiasami podczas mnożenia łańcucha.

Przesunięcie bitowe wyprodukowanej liczby całkowitej rośnie coraz częściej. print()ma opcjonalny argument sep, określający ciąg znaków, który należy wstawić między każdy element na rozpakowanej liście.

mypetlion
źródło
2
Możesz po prostu wydrukować listę. Format wyjściowy nie jest tak ścisły.
mbomb007
1

Java 7, 108 bajtów

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

Podwaja wartość początkową, o ile wynik jest mniejszy niż 2^n. Następnie aktualizuje wartość początkową (initial_value * 2) + 1i zaczyna od tego momentu, aż w końcu osiągnie (2^n)-1.

np. dla 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

Wypróbuj online!

QBrute
źródło
1

Rubinowy, 50 bajtów

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

Próbowałem kilku „sprytnych” podejść, ale wydaje się to być najkrótsze (dosłownie postępuj zgodnie z instrukcjami)

Wyjaśnienie:

Każda iteracja rozpoczyna się od 2 ^ n-1 i mnoży przez 2, aż do osiągnięcia górnego limitu. Nic szczególnego, tylko podstawowa matematyka.

GB
źródło
1

QBIC , 37 bajtów - wymyślony bonus = wciąż 37 bajtów ...

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

Szkoda, że ​​nie while-wendwbudowałem jeszcze QBIC ... Objaśnienie:

:       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

EDYCJA: QBIC obsługuje teraz WHILE:

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

To tylko 26 bajtów! Oto 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
źródło
1

MATL, 19 18 bajtów

1 bajt zapisany dzięki @Luis

:q2w^XJfP"J@YC2&sv

Wypróbuj online

Suever
źródło
1
@LuisMendo bardzo sprytny! Dzięki
Suever,
1

R , 69 48 46 bajtów

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

Każda liczba dziesiętna odpowiadająca liczbie i in 1..nw systemie binarnym jest mnożona przez 2^(0..n-i), tj. Pierwsze n-i+1potęgi dwóch (1, 2, 4, ...).

Wypróbuj online!

Robert Hacken
źródło
1

Stax , 9 bajtów

übg▓}╥é►╪

Uruchom i debuguj online!

Wyjaśnienie

Wyimaginowany bonus, jeśli ktoś zrobi to bez jakiejkolwiek formy konwersji podstawowej (używając zwykłych starych matematyki).

Cóż, tutaj nie ma konwersji podstawowej.

Używa do rozpakowania wersji (10 bajtów).

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
źródło
0

Partia, 92-0 = 92 bajty

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

Odejmowanie 0 za wymyślony bonus @ StewieGriffin.

Neil
źródło