Permutasi Bit-Reversal

28

Tujuan Anda adalah membuat fungsi atau program untuk membalikkan bit dalam rentang bilangan bulat yang diberi bilangan bulat n . Dengan kata lain, Anda ingin menemukan permutasi bit-reversal dari rentang 2 n item, diindeks nol. Ini juga merupakan urutan OEIS A030109 . Proses ini sering digunakan dalam komputasi Fast Fourier Transforms, seperti algoritma Cooley-Tukey di tempat untuk FFT. Ada juga tantangan untuk menghitung FFT untuk urutan di mana panjangnya adalah kekuatan 2.

Proses ini mengharuskan Anda untuk mengulangi rentang [0, 2 n -1] dan mengubah setiap nilai menjadi biner dan membalikkan bit dalam nilai tersebut. Anda akan memperlakukan setiap nilai sebagai n- digit angka dalam basis 2 yang berarti pembalikan hanya akan terjadi di antara n bit terakhir .

Misalnya, jika n = 3, kisaran bilangan bulat adalah [0, 1, 2, 3, 4, 5, 6, 7]. Ini adalah

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

di mana setiap indeks i dikonversi ke indeks j menggunakan bit-reversal. Ini berarti outputnya adalah [0, 4, 2, 6, 1, 5, 3, 7].

Output untuk n dari 0 hingga 4 adalah

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

Anda mungkin telah memperhatikan pembentukan pola. Diberikan n , Anda dapat mengambil urutan sebelumnya untuk n -1 dan menggandakannya. Kemudian gabungkan daftar yang digandakan ke daftar ganda yang sama tetapi bertambah satu. Memperlihatkan,

[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]

dimana merupakan gabungan.

Anda dapat menggunakan salah satu dari dua metode di atas untuk membentuk solusi Anda. Jika Anda tahu cara yang lebih baik, Anda bebas untuk menggunakannya juga. Metode apa pun baik-baik saja asalkan menghasilkan hasil yang benar.

Aturan

  • Ini adalah sehingga solusi terpendek menang.
  • Builtin yang memecahkan tantangan ini secara keseluruhan dan builtin yang menghitung bit-reversal dari suatu nilai tidak diperbolehkan. Ini tidak termasuk builtin yang melakukan konversi biner atau operasi bitwise lainnya.
  • Solusi Anda setidaknya harus valid untuk n dari 0 hingga 31.
mil
sumber
3
"Builtin yang memecahkan tantangan ini secara keseluruhan dan builtin yang menghitung bit-reversal dari suatu nilai tidak diperbolehkan." Awww IntegerReverse[Range[2^#]-1,2,#]&,. (Saya tidak tahu mengapa Mathematica membutuhkan built-in tapi saya kira itu tidak jauh lebih aneh daripada Sunset...)
Martin Ender
@ Martin Menemukan yang bagus. Suatu hari, mungkin akan ada builtin untuk semua yang ada di Mathematica, termasuk menghasilkan tantangan kode-golf acak.
mil
Bisakah kita mencetak 0alih-alih [0]atau haruskah itu daftar?
Dennis
@ Dennis Poin yang bagus. Saya akan mengizinkannya, karena hanya penting bahwa output mewakili permutasi yang valid terlepas dari formatnya.
mil
Apakah pengembalian false sebagai ganti 0 dapat diterima?
Dennis

Jawaban:

2

Jelly , 7 6 byte

Ḥ;‘$$¡

Terima kasih kepada @EriktheOutgolfer untuk bermain golf 1 byte!

Cobalah online!

Bagaimana itu bekerja

Ḥ;‘$$¡  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
sumber
4

05AB1E , 8 byte

Kode:

¾)IF·D>«

Penjelasan:

¾         # 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.

Menggunakan pengkodean CP-1252 . Cobalah online! .

Adnan
sumber
Yang bagus! Mengalahkan yang saya punya :)
Emigna
@Emigna Terima kasih! Lalu apa versimu?
Adnan
0)ïsF·D>«meskipun dekat. Punya beberapa masalah dengan '0'.
Emigna
1
Penggunaan bagus ¾. Harus ingat trik itu.
Emigna
1
@KevinCruijssen Untuk input 0 , sepertinya lebih cantik untuk memiliki representasi int 0 dan bukan representasi string :). Selain itu, tidak ada perbedaan.
Adnan
4

MATL, 13 12 10 9 8 byte

0i:"EtQh

Cobalah secara Online

Penjelasan

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

Demi kelengkapan, inilah jawaban lama saya menggunakan pendekatan non-rekursif (9 byte).

W:qB2&PXB

Cobalah secara Online

Penjelasan

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

J, 15 11 byte

2&(*,1+*)0:

Ada alternatif untuk 15 byte yang menggunakan konversi dan pembalikan biner lurus ke depan.

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

Pemakaian

   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

Penjelasan

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
mil
sumber
4

Haskell , 40 37 byte

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

Cobalah online!

Terima kasih kepada @Laikoni selama tiga byte!

Angs
sumber
3

Oktaf, 37 byte

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

Membuat fungsi anonim bernama ansyang hanya bisa dipanggil dengan ans(n).

Demo online

Suever
sumber
3

Python 2, 56 55 54 byte

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

Uji di Ideone .

Terima kasih kepada @xnor karena bermain golf 1 byte!

Dennis
sumber
Anda bisa melakukannya [0][n:]or.
xnor
3

Java, 422 419 byte:

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

Yah, saya akhirnya belajar Java untuk bahasa pemrograman kedua saya, jadi saya ingin menggunakan keterampilan baru saya untuk menyelesaikan tantangan sederhana, dan meskipun ternyata sangat lama, saya tidak kecewa. Saya senang saya bisa menyelesaikan tantangan sederhana di Jawa.

Cobalah secara Online! (Ideone)

R. Kap
sumber
Anda dapat menyimpan beberapa byte parsing int dari args daripada membaca dari StdIn
Pavel
3

Mathematica, 56 33 byte

Hitungan byte mengasumsikan sumber yang disandikan ISO 8859-1.

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

Ini menggunakan definisi rekursif untuk mendefinisikan operator unary ±.

Martin Ender
sumber
3

Perl, 46 45 byte

Termasuk +1 untuk -p

Berikan nomor input pada STDIN

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

Pyth - 11 byte

ushMByMGQ]0

Test Suite .

Maltysen
sumber
2

Javascript ES6, 65 53 51 byte

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

Menggunakan algoritma rekursif double-increment-concursive.

Contoh berjalan:

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
sumber
Bagaimana dengan f=n=>n>0?(r=f(n-1).map(i=>i*2)).concat(r.map(i=>i+1)):[0]?
mil
@miles Whoops, tidak sadar aku tidak butuh kasing untuk n==1, terima kasih.
Dendrobium
2
Saya pikir saya berhasil mencukur 2 byte dengan memindahkan perkalian dengan dua:f=(n,m=1)=>n?[...n=f(n-1,m+m),...n.map(i=>i+m)]:[0]
Neil
2

Python 3, 67 59 byte

Berkat @ Dennis untuk -8 byte

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

Kami mungkin juga memiliki implementasi langsung (dimodifikasi) dengan Python, meskipun ini cukup lama.

Fungsi anonim yang mengambil input dengan argumen dan mengembalikan permutasi bit-terbalik sebagai daftar.

Bagaimana itu bekerja

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

Cobalah di Ideone

TheBikingViking
sumber
2
Ini terkait dengan pendekatan saya, tetapi golfiness tidak akan bertahan port ke Python 3.
Dennis
2

Dyalog APL , 12 byte

Membutuhkan ⎕IO←0yang default pada banyak sistem.

2⊥⊖2⊥⍣¯12*⎕

2⊥ dari-base-2 of

membalik

2⊥⍣¯1 kebalikan dari-base-2 dari

n bilangan bulat pertama , di mana n adalah

2* 2 pangkat dari

input numerik

TryAPL online!


Sebagai perbandingan, berikut adalah metode lain:

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

( kereta fungsi ...

2∘× dua kali (argumen)

, digabungkan ke

1+ satu ditambah

2∘× dua kali (argumen)

)⍣ diterapkan sebanyak yang ditentukan oleh

input numerik

di

0 nol

Adm
sumber
(⍋,⍨)⍣⎕⊢0( ⎕io←0)
ngn
@ Ngn Itu tidak ada hubungannya dengan algoritma saya.
Adám
saya pikir itu mirip dengan "metode lain" Anda tetapi ok, saya akan menulis jawaban yang terpisah
ngn
2

K (ngn / k) , 11 8 byte

2/|!2|&:

Cobalah 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

&adalah kata kerja terakhir dalam komposisi sehingga kita perlu :memaksanya menjadi monadik

ngn
sumber
1

Julia, 23 22 byte

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

Implementasi proses yang agak mudah dijelaskan dalam spec tantangan.

Cobalah online!

Dennis
sumber
1

Pyth, 8 byte

iR2_M^U2

Cobalah online: Demonstrasi atau Test Suite

Penjelasan:

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

Clojure, 78 byte

Cukup mengikuti spesifikasi ...

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

Ruby, 57 byte:

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

PHP, 57 byte

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

mengambil input dari parameter baris perintah, mencetak nilai garis bawah-dibatasi. Jalankan dengan -nr.

solusi rekursif, 72 byte

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

fungsi mengambil integer, mengembalikan array

Titus
sumber
1

Ruby , 51 byte

f=->n{n<1?[0]:(a=f[n-1].map{|i|i*2})+a.map(&:next)}

Cobalah online!

Asone Tuhid
sumber
1

Perl 6 , 42 byte

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

Cobalah online!

Menambah integer hanya membalik urutan bit paling tidak signifikan, misalnya dari xxxx0111ke xxxx1000. Jadi indeks bit-reversed berikutnya dapat diperoleh dari yang sebelumnya dengan membalik urutan bit paling signifikan. Topeng XOR dapat dihitung dengan m - (m >> (ctz(i) + 1))untuk m = 2**natau m = 2**n-1.

Perl 6 , 30 byte

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

Cobalah online!

Pendekatan rekursif.

nwellnhof
sumber
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 of @ Dennis ♦ adalah solusi Python 2.

Neil
sumber
ReferenceError: f tidak didefinisikan
l4m2
1

Japt , 14 13 byte

2pU Ǥw ú0U Í

Cobalah online!

Dibongkar & Cara kerjanya

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

Implementasi langsung.

Bubbler
sumber
Sebenarnya ada jalan pintas tanpa dokumen untuk n2:Í
Oliver
1

APL (Dyalog Classic) , 9 byte

(⍋,⍨)⍣⎕⊢0

Cobalah online!

input yang dievaluasi

( )⍣⎕⊢0terapkan benda ( )itu berkali-kali, dimulai dengan0

,⍨ menggabungkan hasil saat ini dengan dirinya sendiri

indeks permutasi sort-ascending

ngn
sumber
0

x86, 31 byte

Membawa cukup besar int[] bufferdi eaxdan n di ecx, dan mengembalikan buffer dieax .

Menerapkan algoritma gabungan yang diberikan dalam pernyataan tantangan. Dimungkinkan untuk menyimpan byte dengan menambah pointer dengan 4 daripada menggunakan akses array secara langsung, tetapi lea/ movsudah cukup singkat (3 byte untuk 3 regs dan pengganda).

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