Permutaciones de inversión de bits

28

Su objetivo es crear una función o un programa para invertir los bits en un rango de enteros dado un entero n . En otras palabras, desea encontrar la permutación de inversión de bits de un rango de 2 n elementos, indexados a cero. Esta es también la secuencia OEIS A030109 . Este proceso a menudo se usa en la computación de transformaciones rápidas de Fourier, como el algoritmo Cooley-Tukey en el lugar para FFT. También hay un desafío para calcular la FFT para secuencias donde la longitud es una potencia de 2.

Este proceso requiere que itere sobre el rango [0, 2 n -1] y que convierta cada valor en binario e invierta los bits en ese valor. Tratará cada valor como un número de n dígitos en la base 2, lo que significa que la inversión solo ocurrirá entre los últimos n bits.

Por ejemplo, si n = 3, el rango de enteros es [0, 1, 2, 3, 4, 5, 6, 7]. Estos son

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

donde cada índice i se convierte en un índice j usando la inversión de bits. Esto significa que la salida es [0, 4, 2, 6, 1, 5, 3, 7].

La salida para n de 0 a 4 son

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

Es posible que haya notado que se forma un patrón. Dado n , puede tomar la secuencia anterior para n -1 y duplicarla. Luego concatena esa lista duplicada a la misma lista doble pero incrementada en una. Mostrar,

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

donde representa la concatenación.

Puede utilizar cualquiera de los dos métodos anteriores para formar su solución. Si conoce una mejor manera, también puede usarla. Cualquier método está bien siempre que genere los resultados correctos.

Reglas

  • Este es el por lo que gana la solución más corta.
  • No se permiten las construcciones que resuelven este desafío como un todo y las construcciones que calculan la inversión de bits de un valor. Esto no incluye las incorporaciones que realizan la conversión binaria u otras operaciones bit a bit.
  • Su solución debe ser, como mínimo, válida para n de 0 a 31.
millas
fuente
3
"No se permiten las acciones integradas que resuelven este desafío en su conjunto y las funciones integradas que calculan la inversión de bits de un valor". Awww, IntegerReverse[Range[2^#]-1,2,#]&. (No sé por qué Mathematica necesita esa función, pero supongo que no es mucho más raro que Sunset...)
Martin Ender
@MartinEnder Buen hallazgo. Algún día, podría ser que habrá algo incorporado para todo en Mathematica, incluida la generación de desafíos aleatorios de código de golf.
millas
¿Podemos imprimir en 0lugar de [0]o tiene que ser una lista?
Dennis
@Dennis Buen punto. Lo permitiré, ya que solo es importante que la salida represente una permutación válida independientemente del formato.
millas
¿ Sería aceptable devolver falso en lugar de 0 ?
Dennis

Respuestas:

2

Gelatina , 7 6 bytes

Ḥ;‘$$¡

¡Gracias a @EriktheOutgolfer por jugar golf en 1 byte!

Pruébalo en línea!

Cómo funciona

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

05AB1E , 8 bytes

Código:

¾)IF·D>«

Explicación:

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

Utiliza la codificación CP-1252 . Pruébalo en línea! .

Adnan
fuente
¡Buena esa! Es mejor que la que tenía :)
Emigna
@Emigna ¡Gracias! ¿Cuál era tu versión entonces?
Adnan
0)ïsF·D>«aunque estaba cerca. Tuve algunos problemas con el '0'.
Emigna
1
Buen uso de ¾. Voy a tener que recordar ese truco.
Emigna
1
@KevinCruijssen Para la entrada 0 , parece más bonito tener la representación int de 0 y no la representación de cadena :). Aparte de eso, no hay diferencias.
Adnan
4

MATL, 13 12 10 9 8 bytes

0i:"EtQh

Pruébalo en línea

Explicación

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

En aras de la exhaustividad, aquí estaba mi vieja respuesta usando el enfoque no recursivo (9 bytes).

W:qB2&PXB

Pruébalo en línea

Explicación

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

J, 15 11 bytes

2&(*,1+*)0:

Hay una alternativa para 15 bytes que usa conversión y reversión binarias directas.

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

Uso

   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

Explicación

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
millas
fuente
3

Octava, 37 bytes

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

Crea una función anónima llamada ansque simplemente se puede llamar con ans(n).

Demo en línea

Suever
fuente
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)]

Pruébalo en Ideone .

¡Gracias a @xnor por jugar golf en 1 byte!

Dennis
fuente
Puedes hacer [0][n:]or.
xnor
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())));}}

Bueno, finalmente aprendí Java para mi segundo lenguaje de programación, por lo que quería usar mis nuevas habilidades para completar un desafío simple, y aunque resultó ser muy largo, no estoy decepcionado. Me alegra haber podido completar un desafío simple en Java.

¡Pruébelo en línea! (Ideone)

R. Kap
fuente
Puede guardar algunos bytes analizando un int desde args en lugar de leer desde StdIn
Pavel
3

Mathematica, 56 33 bytes

El recuento de bytes supone una fuente codificada ISO 8859-1.

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

Esto utiliza la definición recursiva para definir un operador unario ±.

Martin Ender
fuente
3

Perl, 46 45 bytes

Incluye +1 para -p

Dar el número de entrada en STDIN

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

Javascript ES6, 65 53 51 bytes

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

Utiliza el algoritmo recursivo de doble incremento-concat.

Ejecuciones de ejemplo:

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
fuente
¿Qué tal f=n=>n>0?(r=f(n-1).map(i=>i*2)).concat(r.map(i=>i+1)):[0]?
millas
@miles Whoops, no me di cuenta de que no necesito un caso base para n==1, gracias.
Dendrobium
2
Creo que logré reducir 2 bytes moviendo la multiplicación por dos:f=(n,m=1)=>n?[...n=f(n-1,m+m),...n.map(i=>i+m)]:[0]
Neil
2

Python 3, 67 59 bytes

Gracias a @Dennis por -8 bytes

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

También podríamos tener una implementación directa (modificada) en Python, incluso si esto es bastante largo.

Una función anónima que toma datos por argumento y devuelve la permutación de bits invertidos como una lista.

Cómo funciona

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

Pruébalo en Ideone

TheBikingViking
fuente
2
Esto se relaciona con mi enfoque, pero el golf no sobrevivirá a un puerto a Python 3.
Dennis
2

Dyalog APL , 12 bytes

Requiere ⎕IO←0cuál es el predeterminado en muchos sistemas.

2⊥⊖2⊥⍣¯12*⎕

2⊥ desde-base-2 de

el volteado

2⊥⍣¯1 inversa de desde-base-2 de

los primeros n enteros, donde n es

2* 2 al poder de

entrada numérica

TryAPL en línea!


A modo de comparación, aquí está el otro método:

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

( el tren funcional ...

2∘× dos veces (el argumento)

, concatenado a

1+ uno más

2∘× dos veces (el argumento)

)⍣ aplicado tantas veces como lo especifique

entrada numérica

en

0 cero

Adán
fuente
(⍋,⍨)⍣⎕⊢0( ⎕io←0)
ngn
@ngn Eso no tiene nada que ver con mi algoritmo.
Adám
pensé que era similar a su "otro método", pero está bien, voy a escribir una respuesta por separado
NGN
2

K (ngn / k) , 11 8 bytes

2/|!2|&:

Pruébalo en línea!

 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

&es el último verbo en la composición por lo que necesitamos una :para forzarlo a ser monádico

ngn
fuente
1

Julia, 23 22 bytes

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

Implementación bastante sencilla del proceso descrito en la especificación de desafío.

Pruébalo en línea!

Dennis
fuente
1

Pyth, 8 bytes

iR2_M^U2

Pruébelo en línea: Demostración o conjunto de pruebas

Explicación:

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

Clojure, 78 bytes

Solo siguiendo las especificaciones ...

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

Ruby, 57 bytes:

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

PHP, 57 bytes

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

toma datos del parámetro de línea de comando, imprime valores delimitados por guiones bajos Corre con -nr.

solución recursiva, 72 bytes

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

la función toma un entero, devuelve una matriz

Titus
fuente
1

Perl 6 , 42 bytes

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

Pruébalo en línea!

Incrementar un número entero simplemente voltea una secuencia de bits menos significativos, por ejemplo, de xxxx0111a xxxx1000. Por lo tanto, el siguiente índice de bits invertidos se puede obtener del anterior volteando una secuencia de bits más significativos. La máscara XOR se puede calcular con m - (m >> (ctz(i) + 1))for m = 2**no m = 2**n-1.

Perl 6 , 30 bytes

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

Pruébalo en línea!

Enfoque recursivo.

nwellnhof
fuente
1

JavaScript (Firefox 30-57), 48 bytes

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

Puerto de la solución Python 2 de @ Dennis ♦.

Neil
fuente
ReferenceError: f no está definido
l4m2
1

Japt , 14 13 bytes

2pU Ǥw ú0U Í

Pruébalo en línea!

Desempaquetado y cómo funciona

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

Implementación directa.

Bubbler
fuente
En realidad hay un atajo indocumentado para n2:Í
Oliver
1

APL (Dyalog Classic) , 9 bytes

(⍋,⍨)⍣⎕⊢0

Pruébalo en línea!

entrada evaluada

( )⍣⎕⊢0aplicar la cosa ( )muchas veces, comenzando con0

,⍨ concatenar el resultado actual consigo mismo

índices de una permutación ascendente

ngn
fuente
0

x86, 31 bytes

Toma una suficientemente grande int[] bufferen eaxy n en ecx, y devuelve el búfer en eax.

Implementa el algoritmo de concatenación dado en la declaración de desafío. Puede ser posible guardar bytes incrementando los punteros en 4 en lugar de usar los accesos de matriz directamente, pero lea/ movya es bastante corto (3 bytes para 3 registros y un multiplicador).

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