Bit-Reversal-Permutationen

28

Ihr Ziel ist es, eine Funktion oder ein Programm zu erstellen, um die Bits in einem Bereich von Ganzzahlen mit einer Ganzzahl n umzukehren . Mit anderen Worten, Sie möchten die Bit-Umkehr-Permutation eines Bereichs von 2 n Elementen mit einem Index von Null ermitteln. Dies ist auch die OEIS-Sequenz A030109 . Dieser Prozess wird häufig bei der Berechnung schneller Fouriertransformationen verwendet, beispielsweise beim direkten Cooley-Tukey-Algorithmus für FFT. Es gibt auch eine Herausforderung für die Berechnung der FFT für Sequenzen, bei denen die Länge eine Potenz von 2 ist.

Bei diesem Vorgang müssen Sie den Bereich [0, 2 n -1] durchlaufen und jeden Wert in einen Binärwert umwandeln und die Bits in diesem Wert umkehren. Sie behandeln jeden Wert als eine n- stellige Zahl in Basis 2, was bedeutet, dass die Umkehrung nur zwischen den letzten n Bits erfolgt.

Wenn beispielsweise n = 3 ist, ist der Bereich von ganzen Zahlen [0, 1, 2, 3, 4, 5, 6, 7]. Diese sind

i  Regular  Bit-Reversed  j
0    000        000       0
1    001        100       4
2    010        010       2
3    011        110       6
4    100        001       1
5    101        101       5
6    110        011       3
7    111        111       7

wobei jeder Index i unter Verwendung von Bitumkehrung in einen Index j umgewandelt wird . Dies bedeutet, dass die Ausgabe ist [0, 4, 2, 6, 1, 5, 3, 7].

Die Ausgaben für n von 0 bis 4 sind

n    Bit-Reversed Permutation
0    [0]
1    [0, 1]
2    [0, 2, 1, 3]
3    [0, 4, 2, 6, 1, 5, 3, 7]

Möglicherweise haben Sie eine Musterbildung bemerkt. Mit n können Sie die vorherige Folge für n -1 nehmen und verdoppeln. Verknüpfen Sie dann diese Doppelliste mit derselben Doppelliste, aber inkrementiert um eins. Zeigen,

[0, 2, 1, 3] * 2 = [0, 4, 2, 6]
[0, 4, 2, 6] + 1 = [1, 5, 3, 7]
[0, 4, 2, 6] ⊕ [1, 5, 3, 7] = [0, 4, 2, 6, 1, 5, 3, 7]

wo darstellt Verkettung.

Sie können eine der beiden oben genannten Methoden verwenden, um Ihre Lösung zu bilden. Wenn Sie einen besseren Weg kennen, können Sie diesen auch nutzen. Jede Methode ist in Ordnung, solange sie die richtigen Ergebnisse liefert.

Regeln

  • Das ist also gewinnt die kürzeste Lösung.
  • Builtins, die diese Herausforderung als Ganzes lösen, und Builtins, die die Bitumkehr eines Werts berechnen, sind nicht zulässig. Dies schließt keine eingebauten Funktionen ein, die Binärkonvertierungen oder andere bitweise Operationen ausführen.
  • Ihre Lösung muss mindestens für n von 0 bis 31 gültig sein .
Meilen
quelle
3
"Builtins, die diese Herausforderung insgesamt lösen, und Builtins, die die Bitumkehr eines Werts berechnen, sind nicht zulässig." Awww, IntegerReverse[Range[2^#]-1,2,#]&. (Ich weiß nicht, warum Mathematica das eingebaute braucht, aber ich denke, es ist nicht viel seltsamer als Sunset...)
Martin Ender
@ MartinEnder Schöne Entdeckung. Eines Tages könnte es sein, dass in Mathematica für alles etwas eingebaut ist, einschließlich der Erzeugung von zufälligen Code-Golf-Herausforderungen.
Meilen
Können wir drucken 0statt [0]oder ist es eine Liste sein müssen?
Dennis
@ Tennis Guter Punkt. Ich werde es zulassen, da es nur wichtig ist, dass die Ausgabe eine gültige Permutation darstellt, unabhängig vom Format.
Meilen
Wäre es akzeptabel, false anstelle von 0 zurückzugeben ?
Dennis

Antworten:

2

Gelee , 7 6 Bytes

Ḥ;‘$$¡

Vielen Dank an @EriktheOutgolfer für das Abschlagen von 1 Byte!

Probieren Sie es online!

Wie es funktioniert

Ḥ;‘$$¡  Main link. No arguments.
        Implicit argument / initial return value: 0

     ¡  Read an integer n from STDIN and call the link to the left n times.
    $   Combine the two links to the left into a monadic chain, to be called
        with argument A (initially 0, later an array).
Ḥ         Unhalve; yield 2A.
   $      Combine the two links to the left into a monadic chain, to be called
          with argument 2A.
  ‘         Increment; yield 2A + 1
 ;          Concatenate 2A and 2A + 1.
Dennis
quelle
4

05AB1E , 8 Bytes

Code:

¾)IF·D>«

Erläuterung:

¾         # Constant for 0.
 )        # Wrap it up into an array.
  IF      # Do the following input times.
    ·     # Double every element.
     D    # Duplicate it.
      >   # Increment by 1.
       «  # Concatenate the first array.

Verwendet die CP-1252- Codierung. Probieren Sie es online! .

Adnan
quelle
Schön!
Schlägt
@Emigna Danke! Was war deine Version damals?
Adnan
0)ïsF·D>«war zwar nah. Hatte einige Probleme mit der '0'.
Emigna
1
Schöne Verwendung von ¾. Ich muss mich an diesen Trick erinnern.
Emigna
1
@KevinCruijssen Für Eingabe 0 sieht es schöner aus, wenn die int-Darstellung 0 und nicht die Zeichenfolgendarstellung :) ist. Ansonsten gibt es keine Unterschiede.
Adnan
4

MATL, 13 12 10 9 8 Bytes

0i:"EtQh

Probieren Sie es online

Erläuterung

0       % Push number literal 0 to the stack
i:"     % Loop n times
    E   % Multiply by two
    t   % Duplicate
    Q   % Add one
    h   % Horizontally concatenate the result
        % Implicit end of loop, and implicitly display the result

Der Vollständigkeit halber war hier meine alte Antwort unter Verwendung des nicht-rekursiven Ansatzes (9 Bytes).

W:qB2&PXB

Probieren Sie es online

Erläuterung

W       % Compute 2 to the power% ofImplicitly thegrab input (n) and compute 2^n
:       % Create an array from [1...2^n]
q       % Subtract 1 to get [0...(2^n - 1)]
B       % Convert to binary where each row is the binary representation of a number
2&P     % Flip this 2D array of binary numbers along the second dimension
XB      % Convert binary back to decimal
        % Implicitly display the result
Suever
quelle
4

J, 15 11 Bytes

2&(*,1+*)0:

Es gibt eine Alternative für 15 Bytes , die eine direkte binäre Konvertierung und Umkehrung verwendet.

2|."1&.#:@i.@^]

Verwendung

   f =: 2&(*,1+*)0:
   f 0
0
   f 1
0 1
   f 2
0 2 1 3
   f 3
0 4 2 6 1 5 3 7
   f 4
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

Erläuterung

2&(*,1+*)0:  Input: n
         0:  The constant 0
2&(     )    Repeat n times starting with x = [0]
2      *       Multiply each in x by 2
     1+        Add 1 to each
    ,          Append that to
2  *           The list formed by multiplying each in x by 2
               Return that as the next value of x
             Return the final value of x
Meilen
quelle
4

Haskell , 40 37 Bytes

f 0=[0]
f a=[(*2),(+1).(*2)]<*>f(a-1)

Probieren Sie es online!

Danke an @Laikoni für drei Bytes!

Angs
quelle
3

Oktave, 37 Bytes

@(n)bin2dec(fliplr(dec2bin(0:2^n-1)))

Erstellt eine anonyme Funktion mit dem Namen ans, die einfach mit aufgerufen werden kannans(n) .

Online Demo

Suever
quelle
3

Python 2, 56 55 54 Bytes

f=lambda n:[0][n:]or[i+j*2for i in 0,1for j in f(n-1)]

Teste es auf Ideone .

Vielen Dank an @xnor für das Golfen ab 1 Byte!

Dennis
quelle
Sie können es tun [0][n:]or.
21.
3

Java, 422 419 Bytes:

import java.util.*;class A{static int[]P(int n){int[]U=new int[(int)Math.pow(2,n)];for(int i=0;i<U.length;i++){String Q=new String(Integer.toBinaryString(i));if(Q.length()<n){Q=new String(new char[n-Q.length()]).replace("\0","0")+Q;}U[i]=Integer.parseInt(new StringBuilder(Q).reverse().toString(),2);}return U;}public static void main(String[]a){System.out.print(Arrays.toString(P(new Scanner(System.in).nextInt())));}}

Nun, ich habe endlich Java für meine zweite Programmiersprache gelernt, also wollte ich meine neuen Fähigkeiten nutzen, um eine einfache Herausforderung zu meistern, und obwohl es sich als sehr lang herausstellte , bin ich nicht enttäuscht. Ich bin nur froh, dass ich eine einfache Herausforderung in Java bewältigen konnte.

Probieren Sie es online! (Ideone)

R. Kap
quelle
Sie können ein paar Bytes speichern, die ein Int aus Argumenten analysieren, anstatt von StdIn
Pavel am
3

Mathematica, 56 33 Bytes

Die Byteanzahl setzt eine ISO 8859-1-codierte Quelle voraus.

±0={0};±x_:=Join[y=±(x-1)2,y+1]

Dies verwendet die rekursive Definition, um einen unären Operator zu definieren ±.

Martin Ender
quelle
3

Perl, 46 45 Bytes

Beinhaltet +1 für -p

Geben Sie die Eingangsnummer für STDIN ein

#!/usr/bin/perl -p
map$F[@F]=($_*=2)+1,@F for(@F=0)..$_;$_="@F"
Tonne Hospel
quelle
2

Pyth - 11 Bytes

ushMByMGQ]0

Test Suite .

Maltysen
quelle
2

Javascript ES6, 65 53 51 Bytes

f=(n,m=1)=>n?[...n=f(n-1,m+m),...n.map(i=>i+m)]:[0]

Verwendet den rekursiven Double-Increment-Concat-Algorithmus.

Beispiel läuft:

f(0) => [0]
f(1) => [0, 1]
f(2) => [0, 2, 1, 3]
f(4) => [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
Dendrobium
quelle
Wie wäre es f=n=>n>0?(r=f(n-1).map(i=>i*2)).concat(r.map(i=>i+1)):[0]?
Meilen
@ Meilen Whoops, wusste nicht, dass ich keinen Basisfall brauche n==1, danke.
Dendrobium
2
Ich glaube, ich habe es geschafft, 2 Bytes zu sparen, indem ich die Multiplikation mit zwei f=(n,m=1)=>n?[...n=f(n-1,m+m),...n.map(i=>i+m)]:[0]
Neil,
2

Python 3, 67 59 Bytes

Vielen Dank an @Dennis für -8 Bytes

lambda n:[int(bin(i+2**n)[:1:-1],2)//2for i in range(2**n)]

Wir können auch eine (modifizierte) einfache Implementierung in Python haben, auch wenn dies ziemlich lang ist.

Eine anonyme Funktion, die Eingaben von Argumenten akzeptiert und die bitumgekehrte Permutation als Liste zurückgibt.

Wie es funktioniert

lambda n                 Anonymous function with input n
...for i in range(2**n)  Range from 0 to 2**n-1
bin(i+2**n)[:1:-1]       Convert i+2**n to binary string, giving 1 more digit than needed,
                         remove '0b' from start, and reverse
int(...,2)               Convert back to decimal
...//2                   The binary representation of the decimal value has one trailing
                         bit that is not required. This is removed by integer division by 2
:[...]                   Return as list

Probieren Sie es auf Ideone

TheBikingViking
quelle
2
Dies hängt mit meiner Herangehensweise zusammen, aber Golf wird eine Portierung nach Python 3 nicht überleben.
Dennis
2

Dyalog APL , 12 Bytes

Benötigt, ⎕IO←0was auf vielen Systemen Standard ist.

2⊥⊖2⊥⍣¯12*⎕

2⊥ from-base-2 von

das drehte sich um

2⊥⍣¯1 Inverse von from-base-2 von

die ersten n ganzen Zahlen, wobei n ist

2* 2 hoch

numerische Eingabe

TryAPL online!


Zum Vergleich ist hier die andere Methode:

(2∘×,1+2∘×)⍣⎕⊢0

( der Funktionszug ...

2∘× zweimal (das Argument)

, verkettet an

1+ eins plus

2∘× zweimal (das Argument)

)⍣ angewendet so oft wie von angegeben

numerische Eingabe

auf

0 Null

Adam
quelle
(⍋,⍨)⍣⎕⊢0( ⎕io←0)
ngn
@ngn Das hat nichts mit meinem Algorithmus zu tun.
Adám
Ich dachte, es wäre ähnlich wie deine "andere Methode", aber ok, ich schreibe eine separate Antwort
ngn
2

K (ngn / k) , 11 8 Bytes

2/|!2|&:

Probieren Sie es online!

 x:3  / just for testing
 &x   / that many zeroes
0 0 0
 2|&x / max with 2
2 2 2
 !x#2 / binary words of length x, as a transposed matrix
(0 0 0 0 1 1 1 1
 0 0 1 1 0 0 1 1
 0 1 0 1 0 1 0 1)
 |!x#2 / reverse
(0 1 0 1 0 1 0 1
 0 0 1 1 0 0 1 1
 0 0 0 0 1 1 1 1)
 2/|!x#2 / base-2 decode the columns
0 4 2 6 1 5 3 7

&ist das letzte Verb in der Komposition, also müssen wir :es zwingen, monadisch zu sein

ngn
quelle
1

Julia, 23 22 Bytes

!n=n>0&&[t=2*!~-n;t+1]

Eher unkomplizierte Umsetzung des in der Challenge-Spezifikation beschriebenen Prozesses.

Probieren Sie es online!

Dennis
quelle
1

Pyth, 8 Bytes

iR2_M^U2

Probieren Sie es online aus: Demo oder Test Suite

Erläuterung:

iR2_M^U2Q   implicit Q (=input number) at the end
     ^U2Q   generate all lists of zeros and ones of length Q in order
   _M       reverse each list
iR2         convert each list to a number
Jakube
quelle
1

Clojure, 78 Bytes

Nur nach der Spezifikation ...

(defn f[n](if(= n 0)[0](let[F(map #(* 2 %)(f(dec n)))](concat F(map inc F)))))
NikoNyrh
quelle
1

Ruby, 57 Bytes:

->n{(0...a=2**n).map{|x|("%b"%x+=a).reverse[0,n].to_i 2}}
GB
quelle
1

PHP, 57 Bytes

while($i<1<<$argv[1])echo bindec(strrev(decbin($i++))),_;

Nimmt Eingaben vom Befehlszeilenparameter entgegen und gibt durch Unterstriche getrennte Werte aus. Laufen Sie mit -nr.

rekursive Lösung, 72 Bytes

function p($n){$r=[$n];if($n)foreach($r=p($n-1)as$q)$r[]=$q+1;return$r;}

Funktion nimmt Ganzzahl, gibt Array zurück

Titus
quelle
1

Perl 6 , 42 Bytes

{0,{$^p+^($_-$_/2+>lsb ++$)}...$_}o 1+<*-1

Probieren Sie es online!

Durch Inkrementieren einer Ganzzahl wird einfach eine Folge von niedrigstwertigen Bits, beispielsweise von xxxx0111bis, umgedreht xxxx1000. So kann der nächste bitumgekehrte Index aus dem vorhergehenden durch Umdrehen einer Folge von höchstwertigen Bits erhalten werden. Die XOR-Maske kann mit m - (m >> (ctz(i) + 1))for m = 2**noder berechnet werdenm = 2**n-1 .

Perl 6 , 30 Bytes

my&f={$_&&(^2 X+(f($_-1)X*2))}

Probieren Sie es online!

Rekursiver Ansatz.

nwellnhof
quelle
1

JavaScript (Firefox 30-57), 48 Byte

f=n=>n?[for(x of[0,1])for(y of f(n-1))x+y+y]:[0]

Port von @ Dennis ♦ 's Python 2-Lösung.

Neil
quelle
ReferenceError: f ist nicht definiert
l4m2
1

Japt , 14 13 Bytes

2pU Ǥw ú0U Í

Probieren Sie es online!

Ausgepackt und wie es funktioniert

2pU o_s2 w ú0U n2

2pU    2**n
o_     range(2**n).map(...)
s2       convert to binary string
w        reverse
ú0U      right-pad to length n, filling with '0'
n2       convert binary string to number

Einfache Implementierung.

Bubbler
quelle
Es gibt tatsächlich eine undokumentierte Abkürzung für n2:Í
Oliver
1

APL (Dyalog Classic) , 9 Bytes

(⍋,⍨)⍣⎕⊢0

Probieren Sie es online!

ausgewertete Eingabe

( )⍣⎕⊢0wende das Ding so ( )oft an, beginnend mit0

,⍨ verketten das aktuelle Ergebnis mit sich selbst

Indizes einer sortier aufsteigenden Permutation

ngn
quelle
0

x86, 31 Bytes

Nimmt ein ausreichend großes int[] bufferin eaxund n in ecxund gibt den Puffer in zurückeax .

Implementiert den in der Challenge-Anweisung angegebenen Verkettungsalgorithmus. Es kann möglich sein, Bytes zu speichern, indem die Zeiger um 4 erhöht werden, anstatt Array-Zugriffe direkt zu verwenden, aber lea/ movist bereits ziemlich kurz (3 Bytes für 3 Register und ein Multiplikator).

.section .text
.globl main
main:
        mov     $buf, %eax          # buf addr
        mov     $3, %ecx            # n 

start:
        xor     %ebx, %ebx
        mov     %ebx, (%eax)        # init buf[0] = 0 
        inc     %ebx                # x = 1

l1:
        mov     %ebx, %edi          
        dec     %edi                # i = x-1
        lea     (%eax,%ebx,4), %edx # buf+x 

l2:
        mov     (%eax,%edi,4), %esi # z = buf[i]
        sal     %esi                # z *= 2
        mov     %esi, (%eax,%edi,4) # buf[i] = z
        inc     %esi                # z += 1
        mov     %esi, (%edx,%edi,4) # buf[x+i] = z

        dec     %edi                # --i 
        jns     l2                  # do while (i >= 0)

        sal     %ebx                # x *= 2
        loop    l1                  # do while (--n)

        ret

.data
buf:    .space 256, -1

Hexdump:

00000507  31 db 89 18 43 89 df 4f  8d 14 98 8b 34 b8 d1 e6  |1...C..O....4...|
00000517  89 34 b8 46 89 34 ba 4f  79 f1 d1 e3 e2 e7 c3     |.4.F.4.Oy......|
qwr
quelle