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

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

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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.