Ausgangsnummern bis 2 ^ n-1, "sortiert"

38

Nehmen Sie eine positive Ganzzahl n als Eingabe und geben Sie (einige der) Dezimalzahlen aus, die mit n Bits in der folgenden Reihenfolge erstellt werden können:

Listen Sie zuerst alle Nummern auf, die mit nur einer erstellt werden können 1, und den Rest 0in der Binärdarstellung (sortiert), dann alle Nummern, die mit zwei aufeinanderfolgenden 1 , den Rest 0, dann drei aufeinanderfolgenden 1 usw. erstellt werden können.

Mal sehen, wie das für n = 4 aussieht :

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

Die Ausgabe für n = 4 ist also: 1, 2, 4, 8, 3, 6, 12, 7, 14, 15 (optionales Ausgabeformat).

Testfälle:

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

Das ist , also gewinnt der kürzeste Code in jeder Sprache !

Gute Erklärungen sind sehr erwünscht , auch für Lösungen in "regulären Sprachen"!

Stewie Griffin
quelle
2
@zeppelin habe ich mir anfangs auch gedacht, aber dieser ist ganz anders.
ETHproductions
1
Verbunden. (Etwas.)
Martin Ender
6
Imaginärer Bonus, wenn jemand dies ohne irgendeine Form der Basisumwandlung tut (mit einfachen alten Berechnungen).
Stewie Griffin
Schrieb dieses, das eine Mischung zwischen den zwei ist, denke ich, versuchen Sie es online!
PrincePolka

Antworten:

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)

Probieren Sie es online!

Die rekursive Funktion generiert die sortierte Liste als Vorbestellung in diesem Baum (Beispiel mit n=4):

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

1 2 4 8 3 6 12 7 14 15

Linke Zweige verdoppeln den Wert und rechte Zweige i->i*2+1existieren nur für ungerade i. Der Vorbestellungsspaziergang für Nicht-Blätter ist also T(i)=[i]+T(i*2)+i%2*T(i*2+1).

Der Baum endet in der Tiefe n, wo ndie Eingabe ist. Dies wird erreicht, indem nmit jedem Abwärtsschritt verringert und angehalten wird, wenn es 0 ist.

Eine alternative Strategie besteht darin, bei Werten zu enden, idie die 2**nTiefe überschreiten , anstatt sie zu verfolgen. Ich fand das ein Byte länger:

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
quelle
4
Wow. Dies ist nicht nur ein wirklich cooler / cleverer Trick, sondern auch äußerst effektiv. +1, wirklich schöne Antwort!
DJMcMayhem
2
Das [f]ist eine amüsante Geste, ich kann nicht sagen, dass ich das schon mal gesehen habe.
FryAmTheEggman
18

Gelee , 6 Bytes

Ḷ2*ẆS€

Dies qualifiziert sich für den imaginären Bonus .

Probieren Sie es online!

Wie es funktioniert

Ḷ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
quelle
1
ist ein idealer Baustein für diese Herausforderung und wird so implementiert, dass die Ergebnisse genau in der richtigen Reihenfolge für diese Herausforderung sind. Gut gemacht :-)
ETHproductions
Sind das nicht 12 Bytes (zumindest in UTF-8)?
Gareth
1
@Gareth Ja, aber Jelly unterstützt auch einen Einzelbyte- Zeichensatz , der nur 256 Symbole enthält, die es versteht.
Dennis
9

Mathematica, 40 Bytes

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

Jede Zahl in der gewünschten Liste ist der Unterschied zwischen zwei Zweierpotenzen, daher generieren wir sie einfach in der Reihenfolge, in der Tabledie Liste verwendet und dann abgeflacht wird. Ich denke, das bringt Stewie Griffins imaginären Bonus :)

Mathematica, 35 Bytes

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

Ein Port von Dennis 'Jelly-Algorithmus . Ich wusste es Subsequencesvorher nicht! (Ich habe auch nicht gesehen, dass Miles genau diese Antwort gepostet hat ... stimmt dem zu!)

Greg Martin
quelle
1
Hinweis: Diese Lösung ist identisch mit @miles Mathematica-Code , der 5 Stunden vor der Bearbeitung von @GregMartin veröffentlicht wurde. Jedoch pro Meta Konsens , ist diese Antwort noch gültig ist .
JungHwan Min
Ugh, das habe ich nicht gesehen - danke, dass du darauf hingewiesen hast.
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)

Ein vollständiges Programm, das Eingaben über eine Eingabeaufforderung vornimmt und jede Nummer nacheinander benachrichtigt. Dies gilt auch für den imaginären Bonus .

Testschnipsel

(Hinweis: verwendet console.loganstelle von alert)

ETHproductions
quelle
Vorschlag (nachdem "keine Popups mehr anzeigen" angekreuzt werden müssen): Wechseln Sie für das Test-Snippet zu console.log.
Tejas Kale
@ TejasKale Gute Idee, danke!
ETHproductions
7

JavaScript (ES6), 55 51 Byte

Gibt eine durch Leerzeichen getrennte Liste von Ganzzahlen zurück.

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

Imaginärer Bonus freundlich.

Formatiert und kommentiert

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

Testfälle

Arnauld
quelle
6

Python 2 , 64 61 Bytes

-3 Bytes dank Dennis

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

Probieren Sie es online!

Stange
quelle
6

Mathematica, 35 Bytes

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

Probieren Sie es online!

Dennis
quelle
1
Ich habe gerade eine Stunde damit verbracht, mir diese Formel auszudenken (2<<i)-1<<j... und du hast es bereits herausgefunden. Gut gemacht! Auch gute Arbeit bei der Beseitigung der doppelten Bereiche
TheNumberOne
4

Haskell, 47 Bytes

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

Anwendungsbeispiel: f 4-> [1,2,4,8,3,6,12,7,14,15]. Probieren Sie es online! .

So funktioniert es: Beginnen Sie für jede Zahl bin und verdoppeln Sie wiederholt den Wert und nehmen Sie Elemente aus dieser Liste.[1..n]2^b-1n-b+1

nimi
quelle
4

Groovy, 90 89 Bytes

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

Binäre Konvertierung ist in Groovy so dumm.

-1 danke an Gurupad Mamadapur

Magische Kraken-Urne
quelle
3
28 Bytes binäre Konvertierung Boilerplate, so schmerzhaft.
Magic Octopus Urn
1
{(1..<2**it)...Speichert ein Byte.
Gurupad Mamadapur
3

Bash + Unix-Dienstprogramme, 51 Bytes

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

Probieren Sie es online!

Die Eingabe n wird in einem Argument übergeben.

Verwenden Sie seq, um alle Zahlen mit n oder weniger Ziffern zu drucken. (Dies sind Basis-10-Zahlen, daher gibt es hier viele zusätzliche Zahlen. Es ist verschwenderisch und zeitaufwändig, aber das ist Codegolf!)

Der Aufruf von grep behält nur die Zahlen bei, die genau aus einer 1 gefolgt von einer 0 bestehen.

Verwenden Sie dann sort -r, um diese in umgekehrter lexikografischer Reihenfolge zu sortieren.

Als letztes wird dc auf die Eingabe zur Basis 2 gesetzt - es schiebt die sortierten Zahlen auf einen Stapel und druckt den Stapel dann von oben nach unten. (Dies druckt das letzte Element, das zuerst verschoben wurde usw., weshalb ich sort -r anstelle von sort verwende.)

Fehler behoben: Ich habe die Option -f% .f für seq weggelassen, die ab 1000000 für ganzzahlige Zählungen erforderlich ist. (Vielen Dank an @TobySpeight für den Hinweis, dass ein Problem aufgetreten ist.)

Mitchell Spector
quelle
" Verschwenderisch und zeitraubend " ... und clever ! Vielen Dank dafür - es ist eine gute Erinnerung, die Recheneffizienz beim Golfen absichtlich zu ignorieren. Das ist wirklich schwierig, wenn Sie den Rest Ihrer Tage damit verbringen, schnellen und klaren Code zu schreiben ...
Toby Speight,
Einige Werte fehlen: Es werden dc<<<2i`seq $[10**7-1]|grep ^1*0*$|sort -r`f | wc -nur 12 Werte gemeldet. Ich denke du willst grep ^1[01]*$stattdessen.
Toby Speight
@TobySpeight Danke - es gab einen Fehler, den ich behoben habe. Das Problem lag nicht am Regex; Das Problem war, dass seq eine Option erforderte. (Ich bin mir nicht sicher, warum Sie nur 12 Ausgabewerte erhalten haben - selbst die falsche Version hat 21 Ausgabewerte anstelle der korrekten 28 erzeugt. Wenn Sie dies auf TIO ausgeführt haben, hat es möglicherweise das 1-Minuten-Limit von TIO überschritten Ich habe dies jetzt sowohl unter Linux als auch unter OS X getestet.
Mitchell Spector
1
Eigentlich habe ich die Frage falsch verstanden - das wichtige Wort "konsekutiv" ging da irgendwie direkt an mir vorbei!
Toby Speight
2

Perl 6 , 38 Bytes

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

Wie es funktioniert

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

Dh es konstruiert die Zahlen wie folgt:

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

Der Code:


Perl 6 , 44 Bytes

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

Dies war mein erster Ansatz, bevor ich über die (eigentlich einfachere) Bit-Shift-Lösung nachdachte.

Wie es funktioniert

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

Dh es konstruiert die Zahlen wie folgt:

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

Haskell 59 46 Bytes

Ich habe angefangen mit f n=[0..n]>>= \b->take(n-b).iterate(*2).sum.map(2^)$[0..b]

Aus Nimis Antwort oben ist die Erkenntnis hervorgegangen, sum.map(2^)$[0..x]die sich auf diese Weise zusammenfassen lässt2^x-1

Am Ende mit

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

[1..n] - Liste mit der Anzahl der aufeinanderfolgenden Bits, die wir durchlaufen wollen`

>> = --grob übersetzt für jedes Element in der Liste auf der linken Seite übergeben Sie es an die Funktion auf der rechten Seite und verketten Sie alle Ergebnisse

\ x -> - Lambda-Funktionsdeklaration mit einem Argument

map xy - Wendet die Funktion x auf alle Mitglieder der Liste y an

In unserem Fall ist x = (\ y-> 2 ^ y * (2 ^ x-1)) - eine andere Lambda-Funktion 2 ^ y * (2 ^ x-1)). Diese Formel ergibt sich aus der Multiplikation mit zwei und der Addition einer Null nach rechts im Binärformat (Beispiel 0001 bis 0010). 2 ^ x - 1 ist die Anzahl der Bits, mit denen wir arbeiten. also haben wir für 11 2 ^ 0 * 3 (dh überhaupt nicht verschieben) == 0011, dann 2 ^ 1 * 3 = 0110, dann 2 ^ 2 * 3 - 1100.

[0..nx] Erstellt die Liste, wie oft wir die Bits verschieben können. Wenn wir mit einer einzelnen 1 arbeiten und dann 0001 betrachten, möchten wir 3-mal verschieben (4-1). Wenn wir zwei 11 arbeiten, wollen wir 4-2 und so weiter.

Brander
quelle
2

Python 3, 59 Bytes

Hinweis: Dies wurde unabhängig von den Lösungen von ovs und Dennis gemacht , obwohl es beiden sehr ähnlich ist.

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

Wie es funktioniert:

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.

Probieren Sie es online!

Trinkgelder (sowohl Codierung als auch Bargeld) sind immer willkommen!

Die Nummer eins
quelle
2

Japt , 11 Bytes

o@o!²ãXÄ mx

Online testen!

Erläuterung

Dies verwendet ziemlich genau den Ansatz von @ 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
quelle
2

PHP, 59 56 53 Bytes

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

nimmt Eingaben von STDIN entgegen; renn mit -R.

Nervenzusammenbruch

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
quelle
Sie können $argnsehr gute Idee verwenden. Nach dem Lesen der Frage habe ich eine Lösung mit über 200 Bytes im Kopf
Jörg Hülsermann
@ JörgHülsermann Danke, dass du mich an STDIN erinnert hast. Ich liebe es einfach, Loops zu verschmelzen.
Titus
1

J , 19 Bytes

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

Dies geschieht in @Dennis ' Lösung auf die gleiche Weise .

Probieren Sie es online!

Erläuterung

(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
Meilen
quelle
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=', ')

Vollständiges Programm mit durch Kommas und Leerzeichen getrennter Ausgabe, wie angegeben.

Erläuterung:

Sternnotation entpackt Listen. So print(*[1,2,3])ist das gleiche wie print(1,2,3). Übergeben Sie dem int()Konstruktor eine Folge aufeinanderfolgender Einsen.

-~bergibt b+1, aber Sie müssen es nicht mit eckigen Klammern umgeben, wenn Sie eine Zeichenfolge multiplizieren.

Verschieben Sie die erzeugte Ganzzahl mehrmals mit Bits. print()hat das optionale Argument sep, das die Zeichenfolge angibt, die zwischen die einzelnen Elemente in einer entpackten Liste eingefügt werden soll.

mypetlion
quelle
2
Sie können die Liste einfach ausdrucken. Das Ausgabeformat ist nicht so streng.
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);}}

Verdoppelt den Anfangswert, solange das Ergebnis kleiner als ist 2^n. Anschließend wird der Anfangswert aktualisiert (initial_value * 2) + 1und von dort erneut gestartet, bis er schließlich erreicht wird (2^n)-1.

zB für 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

Probieren Sie es online!

QBrute
quelle
1

Ruby, 50 Bytes

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

Ich habe einige "clevere" Ansätze ausprobiert, aber dies scheint die kürzeste zu sein (befolge buchstäblich die Anweisungen)

Erläuterung:

Jede Iteration beginnt mit 2 ^ n-1 und multipliziert sich mit 2, bis die Obergrenze erreicht ist. Nichts Besonderes, nur einfache Mathematik.

GB
quelle
1

QBIC , 37 Bytes - imaginärer Bonus = noch 37 Bytes ...

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

while-wendSchade, dass ich QBIC noch nicht eingebaut habe ... Erläuterung:

:       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 unterstützt jetzt WHILE:

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

Das sind nur 26 Bytes! Hier ist der 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
quelle
1

MATL, 19 18 Bytes

1 Byte gespart dank @Luis

:q2w^XJfP"J@YC2&sv

Probieren Sie es online

Suever
quelle
1
@ LuisMendo sehr klug! Vielen Dank
Suever
1

R , 69 48 46 Byte

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

Jede Dezimalzahl, die einer Zahl i in 1..nim Binärsystem entspricht, wird mit der 2^(0..n-i)ersten n-i+1Zweierpotenz (1, 2, 4, ...) multipliziert .

Probieren Sie es online!

Robert Hacken
quelle
1

Stax , 9 Bytes

übg▓}╥é►╪

Online ausführen und debuggen!

Erläuterung

Imaginärer Bonus, wenn jemand dies ohne irgendeine Form der Basisumwandlung tut (unter Verwendung einfacher alter Mathematik).

Nun, hier gibt es keine Basiskonvertierung.

Verwendet die entpackte Version (10 Bytes), um zu erklären.

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

Stapel, 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(

Subtrahieren von 0 für den imaginären Bonus von @ StewieGriffin.

Neil
quelle