N-ty podzbiór zestawu

13

Zadanie

Biorąc pod uwagę zestaw

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

i liczba całkowita

0≤N<2|S|

znajdź N-ty podzbiór.

Wejście wyjście

N jest podane jako liczba całkowita bez znaku na standardowym wejściu. Musisz wydrukować podzbiór n-tym w formacie odpowiednim dla danego języka (może to obejmować [1,2,3], {1,2,3}, [1, 2, 3], 1 2 3, 1,2,3itd. Tak długo, jak jest to czytelny dla człowieka text format).

Trochę o podzbiorach

Istnieje związek między podzbiorami i liczbami w podstawie drugiej. Każda cyfra określa, czy i- ty element zestawu należy do podzbioru. Na przykład 00000000 będzie pustym zestawem, a 10000001 jest podzbiorem zawierającym (ostatni i pierwszy element). Otrzymujesz N-ty podzbiór, przekształcając liczbę w podstawę 2, a następnie ten podzbiór zawiera wszystkie elementy, w których . Trzeci podzbiór (3 = 00000011) zawiera zatem . Najbardziej prawą cyfrą jest cyfra 0. Można drukować . Zestaw nie musi być sortowany.

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

Dodatki:

Tak, zestaw jest ustawiony na 1..8. Zestaw nie jest częścią danych wejściowych. Wejście jest tylko N .

Tak, możesz użyć alternatywnych formularzy wprowadzania.

Wszystkie oczekiwane wyniki dla wszystkich N : https://tio.run/##SyotykktLixN/f/fyNS02qIoP8soJd1CwSAg2kY32LPWPaoqs7jg/38A

code-golf mroman
źródło
1
Jest to zestaw specjalnie 1do 8, czy też dowolny zestaw?
Jo King
2
Dziwi mnie, że nikt wcześniej nie pytał: czy byłbyś tak miły, aby zezwolić na funkcje takie jak przekazywanie, które przyjmują dane wejściowe jako argument i nie zmuszają języków do używania standardowego wejścia (czego niektórzy nie są w stanie)? Pytanie dotyczy podzbiorów i nie bawi się danymi wejściowymi.
ბიმო
5
Nie musisz mówić wszystkim, czy ich rozwiązanie jest poprawne, możesz ograniczyć się do powiedzenia, kiedy tak nie jest.
ბიმო
1
Ponieważ zestaw jest ograniczony do 1..8 , dane wyjściowe takie jak "123"byłyby jednoznaczne. Czy to jest ważne
Arnauld
2
Czy możemy użyć indeksowania 0 [0,7] zamiast [1,8]?
Erik the Outgolfer

Odpowiedzi:

17

Galaretka , 3 bajty

BUT

Wypróbuj online!

Jak to działa

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
źródło
5
Ale, ale ALE ...?!
Arnauld
2
@Arnauld ALE wszystko jest kłamstwem! Myślisz, że wszystko jest binarne? Cóż ... ta Wzniesiona jest Prawda! Nie, nie wszystko jest binarne. Witamy w szarej strefie!
Erik the Outgolfer
7

R , 52 26 bajtów

which(intToBits(scan())>0)

Wypróbuj online!

Konwertuje dane wejściowe na bity i zwraca oparte na 1 indeksy ich położenia TRUE. To sprawia, że ​​jest to odpowiedź na galaretkę Dennisa .

Zwraca integer(0)pustą listę liczb całkowitych do wprowadzenia 0.

Giuseppe
źródło
Chociaż ta odpowiedź nie zawiera IF, AND ani ALE.
ngm
2

K4 , 7 bajtów

Rozwiązanie:

1+&|2\:

Przykład:

Pierwsze 10 ...

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

Wyjaśnienie:

1+&|2\: / the solution
    2\: / convert to base-2
   |    / reverse
  &     / indices where true
1+      / add 1
streetster
źródło
2

Japt, 7 bajtów

ì2 Ôi ð

Spróbuj

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

¤¬²Ôð¥1

Spróbuj

¤           :Convert to base-2 string
 ¬          :Split
  ²         :Push 2
   Ô        :Reverse
    ð       :0-based indices of elements
     ¥1     :  Equal to 1
Kudłaty
źródło
1

Łuska , 5 bajtów

`fN↔ḋ

Pobiera dane wejściowe jako argument wiersza poleceń nie na stdin ( mam nadzieję, że jest w porządku ), spróbuj online!

Wyjaśnienie

`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]
ბიმო
źródło
1

Haskell , 55 54 bajtów

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

Wysyła zestaw w odwrotnej kolejności, spróbuj online!

Wersja ogólna, 56 bajtów

{i}i=18

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

Wypróbuj online!

Wyjaśnienie

Termin mapM (pure [0,1]) [1..n]generuje listę ( n=4) [[0,0,0,0],[0,0,0,1],[0,0,1,0],..,[1,1,1,1]]- tj. reprezentacje binarne [0..2^n-1]. Indeksowanie w nim za pomocą ndaje binarną reprezentację n.

Teraz możemy to zipzrobić za pomocą liczb odwróconych [1..n]i zachować tylko te elementy, w których cyfra binarna jest niezerowa:

 [ x | (x,digit) <- zip [n,n-1,..1] binaryRepN, digit > 0 ]
ბიმო
źródło
1

Węgiel drzewny , 11 bajtów

↓⭆⮌↨Ｎ²×ιＩ⊕κ

Wypróbuj online! Link jest do pełnej wersji kodu. Jeśli wydrukowanie odpowiedzi w poziomie bez spacji jest dopuszczalne, pierwszy znak można usunąć. Wyjaśnienie:

    Ｎ       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
źródło
1

JavaScript (ES6), 37 bajtów

+4 bajty, jeśli separator jest obowiązkowy
+3 bajty, jeśli ten separator jest przecinkiem i dozwolony jest przecinek wiodący

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

Wypróbuj online!

Arnauld
źródło
1

Common Lisp, 57 bajtów

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

Wypróbuj online!

Renzo
źródło
1

J , 13 10 bajtów

-3 bytes thanks to Bubbler

1+I.@|.@#:

Wypróbuj online!

Galen Iwanow
źródło
1
10 bajtów .
Bubbler,
@Bubbler Thanks! Myślałem, że spróbowałem - najwyraźniej nie :)
Galen Iwanow
0

Python 3.6, 58 bajtów

f=lambda n:[8-v for v,i in enumerate(f'{n:08b}')if int(i)]
PieCot
źródło
0

APL + WIN, 13 bajtów

Monity o N:

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

Wypróbuj online! Dzięki uprzejmości Dyalog Classic

Wyjaśnienie:

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

Zwraca podzbiór w odwrotnej kolejności

Graham
źródło
0

Oracle SQL, 77 bajtów

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

Testuj w 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
źródło
0

MathGolf , 8 bajtów

â^mÉ┤\*─

Wypróbuj online!

Wyjaśnienie

â         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

Alternatywny format wyjściowy

Z bardziej elastycznym formatem wyjściowym (który moim zdaniem wygląda całkiem dobrze) mogę wymyślić 6-bajtowy:

â^É┤\*

Zamiast mapowania używam niejawnego for-each i pomijam spłaszczanie. Dane wyjściowe wyglądają tak:

[1][2][][4][5][6][7][]
maxb
źródło
0

F # (mono) , 45 bajtów

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

Wypróbuj online!

Zaimplementowałem również funkcję generyczną / rekurencyjną, ale jest ona dość brzydka, a liczba bajtów jest znacznie większa ...

F # (mono) , 107 bajtów

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

Wypróbuj online!

dana
źródło
0

05AB1E , 6 bajtów

bRSƶ0K

Wypróbuj online lub sprawdź wszystkie możliwe przypadki testowe .

Wyjaśnienie:

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
źródło
0

Java 8, 58 bajtów

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

Wypróbuj online.

Wyjaśnienie:

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
źródło