Nésimo subconjunto de um conjunto

13

A tarefa

Dado o conjunto

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

e um inteiro

0≤N<2|S|

encontre o enésimo subconjunto.

Entrada / Saída

N é dado como um número inteiro não assinado em stdin. Você deve imprimir o subconjunto Nth em um formato adequado para o seu idioma (pode incluir [1,2,3], {1,2,3}, [1, 2, 3], 1 2 3, 1,2,3etc. durante o tempo que é uma legível texto formato).

Um pouco sobre subconjuntos

Há um relacionamento entre subconjuntos e números na base dois. Cada dígito especifica se o i- ésimo elemento do conjunto está dentro do subconjunto. Por exemplo, 00000000 seria o conjunto vazio e 10000001 é o subconjunto que contém (o último e o primeiro elemento). Você obtém o enésimo subconjunto convertendo o número na base 2 e, em seguida, o subconjunto inclui todos os elementos em que . O terceiro subconjunto (3 = 00000011) contém assim . O dígito mais à direita é o número 0. Está tudo bem para imprimir . O conjunto não precisa ser classificado.

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

Adendos:

Sim, o conjunto está fixo em 1..8. O aparelho não faz parte da entrada. A entrada é apenas N .

Sim, você pode usar formulários de entrada alternativos.

Todas as saídas esperadas para todos os N : https://tio.run/##SyotykktLixN/f/fyNS02qIoP8soJd1CwSAg2kY32LPWPaoqs7jg/38A

code-golf mroman
fonte
1
O conjunto é especificamente 1para 8, ou é um conjunto?
Jo rei
2
Estou surpreso que ninguém tenha perguntado antes: você seria tão gentil em permitir funções como envios que tomam a entrada como argumento e não forçam as linguagens a usar stdin (o que alguns não conseguem)? A questão é sobre subconjuntos e não mexer com entradas.
ბიმო
5
Você não precisa dizer a todos se a solução está correta, você pode se restringir a dizer quando não está.
ბიმო
1
Como o conjunto é limitado a 1..8 , uma saída como "123"seria inequívoca. Isso é válido?
Arnauld
2
Podemos usar [0,7] indexado a 0 em vez de [1,8]?
Erik the Outgolfer

Respostas:

17

Geléia , 3 bytes

BUT

Experimente online!

Como 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
fonte
5
Mas, mas, MAS ...?!
Arnauld
2
@ Arnauld MAS tudo é mentira! Você acha que tudo é binário, não é? Bem ... que Upended é a verdade! Então, não, nem tudo é binário. Bem-vindo à área cinzenta!
Erik the Outgolfer
7

R , 52 26 bytes

which(intToBits(scan())>0)

Experimente online!

Converte a entrada em seus bits e retorna os índices baseados em 1 de onde eles estão TRUE. Isso faz deste um porto da resposta de Dennis 'Jelly .

Retorna integer(0), a lista vazia de números inteiros, para entrada de 0.

Giuseppe
fonte
Embora esta resposta não contenha IFs, ANDs ou BUTs.
ngm
2

K4 , 7 bytes

Solução:

1+&|2\:

Exemplo:

10 primeiros ...

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

Explicação:

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

MATLAB / Oitava , 31 29 27 bytes

@(n)9-find(dec2bin(n,8)-48)

Experimente online!

PieCot
fonte
1
@(n)9-find(dec2bin(n,8)-48)
Alephalpha #
@alephalpha Thanks!
PieCot
2

Japonês, 7 bytes

ì2 Ôi ð

Tente

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

¤¬²Ôð¥1

Tente

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

Casca , 5 bytes

`fN↔ḋ

Recebe a entrada como argumento da linha de comando e não no stdin ( espero que esteja tudo bem ), tente online!

Explicação

`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]
ბიმო
fonte
1

Haskell , 55 54 bytes

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

Emite o conjunto na ordem inversa, experimente online!

Versão geral, 56 bytes

{Eu}Eu=18

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

Experimente online!

Explicação

O termo mapM (pure [0,1]) [1..n]gera a lista ( n=4) [[0,0,0,0],[0,0,0,1],[0,0,1,0],..,[1,1,1,1]]- ie. as representações binárias de [0..2^n-1]. A indexação nele com nnos dá a representação binária de n.

Agora podemos fazer zipisso apenas com os números invertidos [1..n]e manter apenas os elementos onde o dígito binário é diferente de zero:

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

Carvão , 11 bytes

↓⭆⮌↨Ｎ²×ιＩ⊕κ

Experimente online! Link é a versão detalhada do código. Se a impressão da resposta horizontalmente sem espaços for aceitável, o primeiro caractere poderá ser removido. Explicação:

    Ｎ       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
fonte
1

JavaScript (ES6), 37 bytes

+4 bytes se um separador for obrigatório
+3 bytes se esse separador for uma vírgula e uma vírgula inicial for permitida

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

Experimente online!

Arnauld
fonte
1

Lisp comum, 57 bytes

(lambda(x)(dotimes(i 7)(format(logbitp i x)"~a "(1+ i))))

Experimente online!

Renzo
fonte
1

J , 13 10 bytes

-3 bytes thanks to Bubbler

1+I.@|.@#:

Experimente online!

Galen Ivanov
fonte
1
10 bytes .
Bubbler
Obrigado @Bubbler! Eu pensei que eu tentei isso - aparentemente não :)
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
fonte
0

APL + WIN, 13 bytes

Solicita N:

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

Experimente online! Cortesia de Dyalog Classic

Explicação:

((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

Retorna o subconjunto na ordem inversa

Graham
fonte
0

Oracle SQL, 77 bytes

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

Teste no 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
fonte
0

MathGolf , 8 bytes

â^mÉ┤\*─

Experimente online!

Explicação

â         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 saída alternativo

Com um formato de saída mais flexível (que eu pessoalmente acho muito bom), posso criar um 6-byter:

â^É┤\*

Em vez de mapear, uso o implícito para cada um e pulo o achatamento. A saída fica assim:

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

F # (Mono) , 45 bytes

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

Experimente online!

Também implementei uma função genérica / recursiva, mas é muito feia e a contagem de bytes é muito maior ...

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

Experimente online!

dana
fonte
0

05AB1E , 6 bytes

bRSƶ0K

Experimente online ou verifique todos os casos de teste possíveis .

Explicação:

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
fonte
0

Java 8, 58 bytes

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

Experimente online.

Explicação:

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
fonte