Enésimo subconjunto de un conjunto

13

La tarea

Dado el conjunto

S=[1,2,3,4,5,6,7,8]

y un entero

0≤N<2|S|

encuentra el enésimo subconjunto.

De entrada y salida

N se da como un entero sin signo en stdin. Debe imprimir el subconjunto enésima en un formato adecuado para su idioma (esto puede incluir [1,2,3], {1,2,3}, [1, 2, 3], 1 2 3, 1,2,3etc durante el tiempo que se trata de una legible por humanos del texto de formato).

Un poco sobre subconjuntos

Existe una relación entre subconjuntos y números en la base dos. Cada dígito especifica si el i- ésimo elemento del conjunto está dentro del subconjunto. Por ejemplo, 00000000 sería el conjunto vacío y 10000001 es el subconjunto que contiene (el último y el primer elemento). Obtiene el enésimo subconjunto al convertir el número en la base 2 y luego el subconjunto incluye todos los elementos donde . El tercer subconjunto (3 = 00000011) contiene así . El dígito más a la derecha es el dígito # 0. Está bien imprimir . El conjunto no tiene que ser ordenado.

di
[1,8]
di>0
[1,2][2,1]

Addendums:

Sí, el conjunto está fijado a 1..8. El conjunto no es parte de la entrada. Entrada es simplemente N .

Sí, puede usar formularios de entrada alternativos.

Todas las salidas esperadas para todos los N : https://tio.run/##SyotykktLixN/f/fyNS02qIoP8soJd1CwSAg2kY32LPWPaoqs7jg/38A

code-golf mroman
fuente
1
Es el conjunto específicamente 1a 8, o es cualquier conjunto?
Jo King
2
Me sorprende que nadie haya preguntado antes: ¿Sería tan amable de permitir funciones como presentaciones que toman la entrada como argumento y no obligan a los idiomas a usar stdin (que algunos no pueden)? La pregunta es sobre subconjuntos y no jugar con entradas.
ბიმო
55
No necesita decirle a todos si su solución es correcta, puede limitarse a decir cuándo no lo es.
ბიმო
1
Como el conjunto está limitado a 1..8 , una salida como "123"sería inequívoca. Es valido?
Arnauld
2
¿Podemos usar 0-indexado [0,7] en lugar de [1,8]?
Erik the Outgolfer

Respuestas:

17

Jalea , 3 bytes

BUT

Pruébalo en línea!

Cómo funciona

BUT  Main link. Argument: n

B    Binary; convert n to base 2.
 U   Upend; reverse the resulting array, so it starts with the LSB.
  T  Truth; find all 1-based indices of set bits.
Dennis
fuente
55
Pero pero pero...?!
Arnauld
2
@Arnauld PERO todo es mentira! Crees que todo es binario, ¿eh? Bueno ... eso invertido es la verdad! Entonces, no, no todo es binario. ¡Bienvenido a la zona gris!
Erik the Outgolfer el
7

R , 52 26 bytes

which(intToBits(scan())>0)

Pruébalo en línea!

Convierte la entrada a sus bits y devuelve los índices basados ​​en 1 de dónde están TRUE. Eso lo convierte en un puerto de la respuesta de Dennis 'Jelly .

Devuelve integer(0), la lista vacía de enteros, para la entrada de 0.

Giuseppe
fuente
Aunque esta respuesta no contiene IFs, ANDs o BUTs.
ngm
2

K4 , 7 bytes

Solución:

1+&|2\:

Ejemplo:

Primero 10 ...

q)k)(1+&|2\:)@'!10
`long$()
,1
,2
1 2
,3
1 3
2 3
1 2 3
,4
1 4

Explicación:

1+&|2\: / the solution
    2\: / convert to base-2
   |    / reverse
  &     / indices where true
1+      / add 1
callejero
fuente
2

Japt, 7 bytes

ì2 Ôi ð

Intentalo

ì2          :Convert to base-2 digit array
   Ô        :Reverse
    i       :Prepend null element
      ð     :0-based indices of truthy elements

¤¬²Ôð¥1

Intentalo

¤           :Convert to base-2 string
 ¬          :Split
  ²         :Push 2
   Ô        :Reverse
    ð       :0-based indices of elements
     ¥1     :  Equal to 1
Lanudo
fuente
1

Casco , 5 bytes

`fN↔ḋ

Toma datos como argumento de línea de comandos no en stdin ( espero que esto esté bien ), ¡ pruébelo en línea!

Explicación

`fN↔ḋ  -- example input: 6
    ḋ  -- convert to binary: [1,1,0]
   ↔   -- reverse: [0,1,1]
`      -- flip the arguments of
 fN    -- | filter the natural numbers by another list
       -- : [2,3]
ბიმო
fuente
1

Haskell , 55 54 bytes

s n=[x|(x,d)<-zip[8,7..]$mapM(pure[0,1])[1..8]!!n,d>0]

Emite el conjunto en orden inverso, ¡ pruébelo en línea!

Versión general, 56 bytes.

{i}i=18

s n=[x|(x,d)<-zip[n,n-1..]$mapM(pure[0,1])[1..n]!!n,d>0]

Pruébalo en línea!

Explicación

El término mapM (pure [0,1]) [1..n]genera la lista ( n=4) [[0,0,0,0],[0,0,0,1],[0,0,1,0],..,[1,1,1,1]], es decir. las representaciones binarias de [0..2^n-1]. La indexación en él con nnos da la representación binaria de n.

Ahora podemos simplemente ziphacerlo con los números invertidos [1..n]y solo mantener los elementos donde el dígito binario no es cero:

 [ x | (x,digit) <- zip [n,n-1,..1] binaryRepN, digit > 0 ]
ბიმო
fuente
1

Carbón , 11 bytes

↓⭆⮌↨Ｎ²×ιＩ⊕κ

Pruébalo en línea! El enlace es a la versión detallada del código. Si imprimir la respuesta horizontalmente sin espacios es aceptable, entonces se puede quitar el primer carácter. Explicación:

    Ｎ       Input as a number
   ↨        Converted to base
     ²      Literal 2
  ⮌         Reversed
 ⭆          Map over bits and join
          κ Current index (0-indexed)
         ⊕  Incremented
        Ｉ   Cast to string
       ι    Current bit
      ×     Repeat string
↓           Print vertically
Neil
fuente
1

JavaScript (ES6), 37 bytes

+4 bytes si un separador es obligatorio
+3 bytes si este separador es una coma y se permite una coma inicial

f=(n,i=1)=>n?(n&1?i:'')+f(n/2,i+1):''

Pruébalo en línea!

Arnauld
fuente
1

J , 13 10 bytes

-3 bytes thanks to Bubbler

1+I.@|.@#:

Pruébalo en línea!

Galen Ivanov
fuente
1
10 bytes .
Bubbler
@Bubbler ¡Gracias! Pensé que había intentado esto, aparentemente no :)
Galen Ivanov
0

Python 3.6, 58 bytes

f=lambda n:[8-v for v,i in enumerate(f'{n:08b}')if int(i)]
PieCot
fuente
0

APL + WIN, 13 bytes

Indicaciones para N:

((8⍴2)⊤⎕)/⌽⍳8

Pruébalo en línea! Cortesía de Dyalog Classic.

Explicación:

((8⍴2)⊤⎕) prompt for N and convert to binary

/⌽⍳8 generate a vector from 1 to 8, reverse and select integers according to 1s in binary

Devuelve el subconjunto en orden inverso

Graham
fuente
0

Oracle SQL, 77 bytes

select*from(select rownum r,value(p)from t,table(powermultiset(x))p)where:n=r

Prueba en SQL Plus

SQL> var n number
SQL> exec :n:=67;

PL/SQL procedure successfully completed.

SQL> with t as (select ku$_vcnt(1,2,3,4,5,6,7,8) x from dual)
  2  select*from(select rownum r,value(p)from t,table(powermultiset(x))p)where:n=r
  3  /
        67
KU$_VCNT('1', '2', '7')
Dr. Y Wit
fuente
0

MathGolf , 8 bytes

â^mÉ┤\*─

Pruébalo en línea!

Explicación

â         Convert first input to binary list
 ^        Zip with [1,2,3,4,5,6,7,8] (other input)
  mÉ      Map 2D array using the next 3 instuctions
    ┤     Pop from right of array
     \*   Swap top two elements and repeat array either 0 or 1 times
       ─  Flatten to 1D array

Formato de salida alternativo

Con un formato de salida más flexible (que personalmente creo que se ve bastante bien) puedo obtener un 6-byter:

â^É┤\*

En lugar de mapear, uso el implícito for-each y omito el aplanamiento. La salida se ve así:

[1][2][][4][5][6][7][]
maxb
fuente
0

F # (Mono) , 45 bytes

let m x=Seq.where(fun y->x>>>y-1&&&1>0)[1..8]

Pruébalo en línea!

También implementé una función genérica / recursiva, pero es bastante fea y el recuento de bytes es mucho más grande ...

F # (Mono) , 107 bytes

let rec g y i=
 if y>0 then seq{
  if y%2>0 then yield i
  yield!g(y/2)(i+1)
 }else Seq.empty
let f x=g x 1

Pruébalo en línea!

dana
fuente
0

05AB1E , 6 bytes

bRSƶ0K

Pruébelo en línea o verifique todos los casos de prueba posibles .

Explicación:

b         # Convert the (implicit) integer input to binary
          #  i.e. 22 → "10110"
 R        # Reverse it
          #  i.e. "10110" → "01101"
  S       # Convert it to a list of 0s and 1s
          #  i.e. "01101" → ["0","1","1","0","1"]
   ƶ      # Multiply each with its 1-indexed index
          #  i.e. ["0","1","1","0","1"] → [0,2,3,0,5]
    0K    # Remove all 0s (and output implicitly)
          #  i.e. [0,2,3,0,5] → [2,3,5]
Kevin Cruijssen
fuente
0

Java 8, 58 bytes

n->{for(int i=0;i<8;)if((1&n>>i++)>0)System.out.print(i);}

Pruébalo en línea.

Explicación:

n->{                        // Method with integer as parameter and no return-type
  for(int i=0;i<8;)         //  Loop `i` in the range [0,8):
    if((1&n>>i++)>0)        //   If 1 AND `n` bitwise right-shifted to `i` is larger than 0
                            //   (with `i` increased by 1 afterwards with `i++`)
      System.out.print(i);} //    Print `i+1`
Kevin Cruijssen
fuente