Задание

Учитывая набор

$$S = \left[{1,2,3,4,5,6,7,8}\right]$$

и целое число

$$0 \leq N < 2^{|S|}$$

найти N-е подмножество.

Ввод, вывод

N задается как целое число без знака на стандартном вводе. Вы должны напечатать подмножество Nth в формате , подходящем для вашего языка (это может включать в себя [1,2,3], {1,2,3}, [1, 2, 3], 1 2 3, и 1,2,3т.д., пока это человек читаемый текст формат).

Немного о подмножествах

Существует связь между подмножествами и числами в базе два. Каждая цифра

$$d_{i}$$ указывает, находится ли i- й элемент набора в подмножестве. Например, 00000000 будет пустым набором, а 10000001 - подмножеством, содержащим [1,8](последний и первый элемент). Вы получаете N-е подмножество путем преобразования числа в основание 2, а затем подмножество включает в себя все элементы, где $$d_{i} > 0$$ . 3-е подмножество (3 = 00000011), таким образом, содержит [1,2]. Самая правая цифра - цифра № 0. Это нормально для печати [2,1]. Набор не должен быть отсортирован.

Дополнения:

Да, набор фиксируется на 1..8. Набор не является частью ввода. Ввод только N .

Да, вы можете использовать альтернативные формы ввода.

Все ожидаемые результаты для всех N : https://tio.run/##SyotykktLixN/f/fyNS02qIoP8soJd1CwSAg2kY32LPWPaoqs7jg/38A

Желе , 3 байта

BUT

Попробуйте онлайн!

Как это устроено

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.

R , 52 26 байт

which(intToBits(scan())>0)

Попробуйте онлайн!

Преобразует входные данные в его биты и возвращает основанные на 1 индексы того, где они находятся TRUE. Это делает это портом ответа Желе Денниса .

Возвращает integer(0)пустой список целых чисел для ввода 0.

Python 2 , 40 байт

lambda x:[i+1for i in range(8)if x>>i&1]

Попробуйте онлайн!

Perl 6 , 33 байта

(1..*Zxx*.base(2).flip.comb).flat

Попробуйте онлайн!

Python 2 , 42 байта

f=lambda n,k=1:n*[k]and n%2*[k]+f(n/2,k+1)

Попробуйте онлайн!

К4 , 7 байт

Решение:

1+&|2\:

Пример:

Первые 10 ...

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

Объяснение:

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

MATLAB / Octave , 31 29 27 байт

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

• уменьшено на 2 байта благодаря alephalpha

• уменьшено на 2 байта благодаря Джузеппе

Попробуйте онлайн!

Japt, 7 байт

ì2 Ôi ð

Попытайся

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

---

¤¬²Ôð¥1

Попытайся

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

Шелуха , 5 байт

`fN↔ḋ

Принимает ввод в качестве аргумента командной строки, а не в stdin ( надеюсь, это нормально ), попробуйте это онлайн!

объяснение

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

Haskell , 55 54 байта

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

Выводит набор в обратном порядке, попробуйте онлайн!

Общая версия, 56 байт

$\{i\}_{i=1}^8$

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

Попробуйте онлайн!

объяснение

Термин mapM (pure [0,1]) [1..n]генерирует список ( n=4) [[0,0,0,0],[0,0,0,1],[0,0,1,0],..,[1,1,1,1]]- т.е. двоичные представления [0..2^n-1]. Индексирование в это nдает нам двоичное представление n.

Теперь мы можем просто сделать zipэто с перевернутыми числами [1..n]и сохранить только те элементы, где двоичная цифра не равна нулю:

 [ x | (x,digit) <- zip [n,n-1,..1] binaryRepN, digit > 0 ]

Древесный уголь , 11 байт

↓⭆⮌↨Ｎ²×ιＩ⊕κ

Попробуйте онлайн! Ссылка на подробную версию кода. Если печать ответа по горизонтали без пробелов допустима, то первый символ может быть удален. Объяснение:

    Ｎ       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

JavaScript (ES6), 37 байт

+4 байта, если разделитель обязателен
+3 байта, если этот разделитель является запятой и допускается начальная запятая

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

Попробуйте онлайн!

Perl 6 , 21 байт

{1 X+grep $_+>*%2,^8}

Попробуйте онлайн!

Альтернатива:

{grep $_*2+>*%2,1..8}

Common Lisp, 57 байт

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

Попробуйте онлайн!

Haskell , 33 байта

s n=[x+1|x<-[0..7],odd$div n$2^x]

Попробуйте онлайн!

---

37 байт

concat.(mapM(\i->[[],[i]])[8,7..1]!!)

Попробуйте онлайн!

Тестовые случаи от Ними.

J , 13 10 байт

-3 bytes thanks to Bubbler

1+I.@|.@#:

Попробуйте онлайн!

Japt, 7 байт

¢Ô¬ðÍmÄ

Протестируйте это онлайн

---

Japt, 7 байт

¤Ôð1 mÄ

Протестируйте это онлайн

C # (интерактивный компилятор Visual C #) , 47 байт

x=>{for(int y=0;y<8;)if((1&x>>y++)>0)Print(y);}

Попробуйте онлайн!

Выглядит похоже на решение Java сейчас, хотя я придумал свое самостоятельно.

Python 3.6, 58 байт

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

Wolfram Language (Mathematica) , 32 байта

Pick[r=Range@8,BitGet[#,r-1],1]&

Попробуйте онлайн!

Пари / ГП , 31 байт

n->[x|x<-[1..8],bittest(n,x-1)]

Попробуйте онлайн!

APL + WIN, 13 байт

Подсказки для N:

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

Попробуйте онлайн! Предоставлено Dyalog Classic

Объяснение:

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

Возвращает подмножество в обратном порядке

Бурлеск - 8 байт

8roR@j!!

Попробуйте онлайн.

Oracle SQL, 77 байт

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

Тест в 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')

MathGolf , 8 байт

â^mÉ┤\*─

Попробуйте онлайн!

объяснение

â         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

Альтернативный формат вывода

С более гибким форматом вывода (который я лично считаю довольно неплохим) я могу придумать 6-байтовый:

â^É┤\*

Вместо отображения я использую неявный for-each и пропускаю выравнивание. Вывод выглядит так:

[1][2][][4][5][6][7][]

Рубин , 31 байт

->n{n.times{|a|n[a]>0&&p(-~a)}}

Попробуйте онлайн!

F # (моно) , 45 байтов

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

Попробуйте онлайн!

Я также реализовал универсальную / рекурсивную функцию, но она довольно уродливая, а количество байтов намного больше ...

F # (моно) , 107 байт

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

Попробуйте онлайн!

05AB1E , 6 байтов

bRSƶ0K

Попробуйте онлайн или проверьте все возможные тестовые случаи .

Объяснение:

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]

Java 8, 58 байт

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

Попробуйте онлайн.

Объяснение:

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`