Lista ordenada de secuencias binarias de múltiples dimensiones.

8

Dado un entero positivo n, genera las 2^nsecuencias binarias de longitud nordenadas en el siguiente orden preciso.

Casos de prueba:

0:

0 or 1 (defining this is a matter of debate)

1:

0
1

2:

00
01
10
11

3:

000
001
010
100
011
101
110
111

4:

0000
0001
0010
0100
1000
0011
0101
1001
0110
1010
1100
0111
1011
1101
1110
1111

etc.

Además, el patrón de combinatoria está relacionado con el Triángulo de Pascal.

0:

1 (this is given regardless of the definition given to 2^0)

1:

1
1

2:

1
2
1

3:

1
3
3
1

4:

1
4
6
4
1

etc.

desarmar
fuente
1
Para mi anterior podría ser el resultado de un fallo en una clasificación algo ...
RosLuP

Respuestas:

3

Haskell, 78 bytes

import Data.List
f n=sortOn(\x->sum x:reverse(map(1-)x))$mapM id$[0,1]<$[1..n]

Ejemplo de uso: f 2-> [[0,0],[0,1],[1,0],[1,1]].

Cómo funciona:

         [0,1]<$[1..n]  -- make n copies of the list [0,1]
     mapM id            -- make all lists where the ith element is from the ith list.
                        -- that gives us all binary sequences
sortOn                  -- sort this list of list
    sum x               -- first by number of ones
      reverse(map(1-)x) -- then by the reversed list with bits flipped
nimi
fuente
Utilicé un compilador Haskell de Apple Store, y no estoy seguro de si eso no me permitirá ejecutar este código. Tomé una captura de pantalla de lo que sucede cuando lo ejecuto: m.imgur.com/VIByUah
desarme el
@DreadVim: parece que no tienes la última versión de las bibliotecas ( Preludepor <$y Data.Listpara sortOn). Además: mi código no es un programa completo, por lo que no se compilará.
nimi
Ah Eso tiene sentido. Tendré que hacerlo en mi computadora portátil.
desarme el
TIL sobre sortOn. Voy a extrañar sortBy (compare `on` f).
Angs
2

Python 2, 146 bytes

from itertools import*
lambda i:sum([sorted({''.join(b)for b in permutations((i-n)*"0"+"1"*n)},key=lambda x:x[::-1])[::-1]for n in range(i+1)],[])

Todavía estoy trabajando en esto, ¡aunque cualquier sugerencia sería muy apreciada!

Sin golf

i=input()   
import itertools
p=[]
for n in range(i+1):
    x=(i-n)*"0"+"1"*n
    t=[]
    for b in itertools.permutations(x):t+=[''.join(b)] if ''.join(b) not in t else []
    p.append(sorted(t, key=lambda x:x[::-1])[::-1])

p=sum(p,[])
print
for line in p:print line
Daniel
fuente
hacer from itertools import*y luego simplemente usar permutationsen la lambda. ahorra 1 byte
FlipTack
1

Python 2, 122 120 102 98 bytes

18 bytes guardados gracias a Flp.Tkc

4 bytes guardados gracias a xnor

lambda x:sorted([bin(i)[2:].zfill(x)for i in range(2**x)],key=lambda x:(sorted(x),int(x[::-1],2)))

Explicación

Esto hace que todas las cadenas binarias de longitud x con:

[bin(i)[2:].xfill(x)for i in range(2**x)]

Luego los clasifico según:

lambda x:(sorted(x),int(x[::-1],2))

sorted(x)prioriza el número de 1s mientras int(x[::-1],2)prioriza la segunda condición

Por último, estos se unen con líneas nuevas y se imprimen.

Ad Hoc Garf Hunter
fuente
Esto no es elegible.
desarme el
@DreadVim Ahora es
Ad Hoc Garf Hunter
Convenido. Buen trabajo.
desarme el
Esto parece recortar los ceros a la izquierda.
xnor
La versión de 106 bytes parece dar un orden diferente para n = 4. El tuyo da 0110 y luego 1001, que se cambia al caso de prueba. No estoy seguro de cómo se especifica realmente el orden correcto.
xnor
1

Perl, 63 bytes

-4 gracias a @Ton Hospel.
-2 gracias a @Gabriel Benamy.

say~~reverse for sort{$b=~y/0//-$a=~y/0//||$b-$a}glob"{1,0}"x<>

Ejecutar con -E(que habilita la función say):

perl -E 'say~~reverse for sort{$b=~y/0//-$a=~y/0//||$b-$a}glob"{1,0}"x<>' <<< 5


Explicaciones cortas :

  • "{1,0}"x$_crea una cadena compuesta de $_veces {1,0}( $_es la entrada). Por ejemplo, con 3: {1,1}{1,0}{1,0}.
  • Luego globhace algo de magia y genera todas las combinaciones de un elemento de cada grupo de llaves (es decir, todas las combinaciones que queremos imprimir).
  • Y luego el orden: $b=~y/1//c-$a=~y/1//ccompara el número de 1en cada cadena, y si tienen el mismo número, $b-$ase ordenará de acuerdo con la segunda regla.
Dada
fuente
Creo que puede guardar dos bytes cambiando y/1//ca y/0//ambas veces
Gabriel Benamy, el
@GabrielBenamy De hecho, gracias. Estoy demasiado acostumbrado a usar y///c!
Dada
Reemplazar <=>por-
Ton Hospel
@TonHospel editado, gracias!
Dada
0

Perl, 116 106 105 102 bytes

sub e{sprintf"%0$%b",@_}sub f{$_=e@_;/0*$/;$%*y/1//-$-[0]}map{say e$_}sort{f($a)<=>f$b}0..2**($%=<>)-1

Legible:

sub e{
    sprintf"%0$%b",@_
}
sub f{
    $_=e@_;/0*$/;$%*y/1//-$-[0]
}
map{
    say e$_
} sort {
    f($a)<=>f$b
} 0..2**($%=<>)-1

La subrutina econvierte su argumento en un valor binario, rellenado con ceros, para que sea la longitud de entrada (por ejemplo, entrada de 5 pads con ceros hasta que tenga 5 caracteres de longitud). La subrutina ftoma un valor binario de este tipo y le otorga un peso de clasificación de acuerdo con cómo debe procesarse.

El rango 0 .. [input] 2 -1 se coloca en una clasificación estable, ordenando por el peso (aquí, "estable" significa que cuando dos valores tienen el mismo peso, se devuelven en el mismo orden en que aparecen en el entrada), y luego se retroalimentan a la subrutina ey salida.

Algunos de ustedes pueden haber visto mi publicación original, pero ayer entendí mal el problema y lo eliminé inmediatamente después de darme cuenta.

Gabriel Benamy
fuente
Esto no produce la salida requerida para n>=5. Por ejemplo, with n>=5, 01101viene antes 10011pero debería ser después.
Dada
0

Raqueta 109 bytes

(let loop((s ""))(if(= n(string-length s))(displayln s)(for((i '("0" "1")))(loop(string-append s i)))))

Sin golf:

(define (f n)
  (let loop ((s ""))
    (if (= n (string-length s))
        (displayln s)
        (for ((i '("0" "1")))
          (loop (string-append s i))))))

Pruebas:

(f 2)
(println "-------------")
(f 3)
(println "-------------")
(f 4)

Salida:

00
01
10
11
"-------------"
000
001
010
011
100
101
110
111
"-------------"
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
rnso
fuente
1
En caso de que n = 3 arriba no sea lo mismo para ejercitar el texto 000 001 010 100 etc.
RosLuP
Este ejercicio podría estar a punto de escribir la función correcta para ordenar una lista de números (y de imprimir la forma binaria)
RosLuP
0

Ruby 2.x, 129 bytes

f=->(n){z='0';p=n.bit_length;(0..n).map{|i|sprintf("%0#{p}d",i.to_s(2))}.sort{|a,b|a=a.delete(z).size-(b=b.delete(z).size)||b-a}}
freakyfelt
fuente
2
¡Bienvenido a Programming Puzzles & Code Golf! Desafortunadamente, esto no parece hacer lo que pide el desafío. Por ejemplo, la entrada 5 imprime las primeras cinco líneas de la salida que corresponden a 3 .
Dennis
0

PHP, 49 bytes

while($i<1<<$n=$argv[1])printf("%0${n}b\n",$i++);

Corre con -r.

Tito
fuente
0

MATLAB, 68 bytes

d=@(n)dec2bin(sortrows([sum(dec2bin(0:2^n-1)');0:2^n-1]')*~eye(2,1))
PieCot
fuente
0

Bash, 65 bytes

Golfed

seq -f "obase=2;%g+2^$1-1" $[2**$1]|bc|cut -c2-|tr 0 ~|sort|tr ~ 0

Prueba

>./binseq 4

0000
0001
0010
0100
1000
0011
0101
0110
1001
1010
1100
0111
1011
1101
1110
1111
zepelín
fuente
Está mal ... Copio y pego la salida anterior: 0011 0101 1001 0110 1010 1100 después de 0101 hay 1001 y no 0110
RosLuP
De hecho, imgur.com/a/yxBLp , supongo, es que probablemente solo esté ejecutando un sistema con una configuración regional diferente (yo uso "en_US.UTF-8"), por lo que se aplican las diferentes reglas de clasificación (lo cual es una expectativa y documentado "ordenar" el comportamiento). Intente cambiar la configuración regional, o dígame la suya, y veré qué carácter debe usar en lugar de ~.
zeppelin
Otra cosa que puede intentar es imponer el orden del diccionario en orden con "-d" (que debería producir menos resultados específicos de la configuración regional)
zeppelin
digo que el resultado impreso arriba para n = 4 [0000 0001 0010 0100 1000 0011 0101 0110 1001 1010 1100 0111 1011 1101 1110 1111] es diferente del resultado de la pregunta para n = 4 [0000 0001 0010 0100 1000 0011 0101 1001 0110 1010 1100 0111 1011 1101 1110 1111] de hecho, la novena posición de esa matriz tiene un valor diferente
RosLuP
@RosLup Creo que 0101 => 1001 es un error en los datos del caso de prueba, no en mi implementación, vea la discusión sobre la respuesta "Python 2" a continuación: "El suyo da 0110 y luego 1001, que se cambia del caso de prueba. No estoy seguro de cómo se especifica realmente el orden correcto. - xnor "" Mi error. En realidad se volcó ... - Dread Vim "(OP)
zeppelin