N-te Teilmenge einer Menge

13

Die Aufgabe

Angesichts der Menge

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

und eine ganze Zahl

0≤N<2|S|

Finden Sie die n-te Teilmenge.

Input-Output

N wird als vorzeichenlose ganze Zahl in stdin angegeben. Sie müssen die n - te Teilmenge in einem geeigneten Format für Ihre Sprache gedruckt werden (dies kann [1,2,3], {1,2,3}, [1, 2, 3], 1 2 3, 1,2,3usw. , solange es ein Mensch lesbar Text - Format).

Ein bisschen über Teilmengen

Es gibt eine Beziehung zwischen Teilmengen und Zahlen in der Basis zwei. Jede Ziffer

di
angibt , ob das i - te Element der Menge innerhalb der Teilmenge ist. Beispielsweise wäre 00000000 die leere Menge und 10000001 die Teilmenge, die enthält [1,8](das letzte und erste Element). Sie erhalten die Teilmenge Nth durch die Zahl in der Basis 2 Umwandlung und dann enthält die Teilmenge alle Elemente , bei denen
di>0
 . Die 3. Teilmenge (3 = 00000011) enthält also [1,2]. Die Ziffer ganz rechts ist die Ziffer # 0. Es ist in Ordnung zu drucken [2,1]. Das Set muss nicht sortiert werden.

Nachträge:

Ja, das Set ist fest auf 1..8. Das Set ist nicht Bestandteil der Eingabe. Die Eingabe ist nur N .

Ja, Sie können alternative Eingabeformulare verwenden.

Alle erwarteten Ausgaben für alle N : https://tio.run/##SyotykktLixN/f/fyNS02qIoP8soJd1CwSAg2kY32LPWPaoqs7jg/38A

code-golf mroman
quelle
1
Ist der Satz speziell 1auf 8, oder ist es ein Satz?
Jo King
2
Ich bin überrascht, dass noch niemand gefragt hat: Würden Sie so freundlich sein, Funktionen als Einreichungen zuzulassen, die die Eingabe als Argument verwenden und Sprachen nicht dazu zwingen, stdin zu verwenden (was einige nicht können)? Die Frage handelt von Teilmengen und nicht von Eingaben.
24.
5
Sie müssen nicht jedem mitteilen, ob die Lösung korrekt ist, sondern können sich darauf beschränken, zu sagen, wann dies nicht der Fall ist.
24.
1
Da der Satz auf 1..8 begrenzt ist , kann ein Ausgang wie z"123" eindeutig. Ist es gültig
Arnauld
2
Können wir 0-indizierte [0,7] anstelle von [1,8] verwenden?
Erik der Outgolfer

Antworten:

17

Gelee , 3 Bytes

BUT

Probieren Sie es online!

Wie es funktioniert

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
quelle
5
Aber, aber, aber...?!
Arnauld
2
@ Arnauld ABER alles ist eine Lüge! Sie denken, dass alles binär ist, nicht wahr? Nun ... dass Upended die Wahrheit ist! Also, nein, nicht alles ist binär. Willkommen in der Grauzone!
Erik der Outgolfer
7

R , 52 26 Bytes

which(intToBits(scan())>0)

Probieren Sie es online!

Konvertiert die Eingabe in ihre Bits und gibt die auf 1 basierenden Indizes zurück, in denen sie sich befinden TRUE. Das macht dies zu einem Hafen von Dennis 'Jelly-Antwort .

Gibt integer(0)die leere Liste der Ganzzahlen zur Eingabe von zurück 0.

Giuseppe
quelle
Obwohl diese Antwort keine IFs, ANDs oder BUTs enthält.
ngm
2

K4 , 7 Bytes

Lösung:

1+&|2\:

Beispiel:

Erste 10 ...

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

Erläuterung:

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

Japt, 7 Bytes

ì2 Ôi ð

Versuch es

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

¤¬²Ôð¥1

Versuch es

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

Schale , 5 Bytes

`fN↔ḋ

Nimmt Eingaben als Kommandozeilenargument nicht auf stdin ( ich hoffe das ist ok ), versuche es online!

Erläuterung

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

Haskell , 55 54 Bytes

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

Gibt das Set in umgekehrter Reihenfolge aus, probiere es online aus!

Allgemeine Version, 56 Bytes

Dies funktioniert für Gruppen, die größer als sind {ich}ich=18:

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

Probieren Sie es online!

Erläuterung

Der Begriff mapM (pure [0,1]) [1..n]erzeugt die Liste ( n=4) [[0,0,0,0],[0,0,0,1],[0,0,1,0],..,[1,1,1,1]]- dh. die binären Darstellungen von [0..2^n-1]. Indizieren in es mit ngibt uns die binäre Darstellung vonn .

Jetzt können wir es einfach zipmit den umgekehrten Zahlen machen [1..n]und nur die Elemente behalten, bei denen die Binärziffer ungleich Null ist:

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

Holzkohle , 11 Bytes

↓⭆⮌↨Ｎ²×ιＩ⊕κ

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Wenn es akzeptabel ist, die Antwort horizontal ohne Leerzeichen auszudrucken, kann das erste Zeichen entfernt werden. Erläuterung:

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

JavaScript (ES6), 37 Byte

+4 Bytes, wenn ein Trennzeichen erforderlich ist
+3 Bytes, wenn dieses Trennzeichen ein Komma ist und ein führendes Komma zulässig ist

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

Probieren Sie es online!

Arnauld
quelle
1

Common Lisp, 57 Bytes

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

Probieren Sie es online!

Renzo
quelle
1

J , 13-10 Bytes

-3 bytes thanks to Bubbler

1+I.@|.@#:

Probieren Sie es online!

Galen Ivanov
quelle
1
10 Bytes .
Bubbler
@Bubbler Danke! Ich dachte, ich habe es versucht - anscheinend nicht :)
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
quelle
0

APL + WIN, 13 Bytes

Eingabeaufforderungen für N:

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

Probieren Sie es online! Mit freundlicher Genehmigung von Dyalog Classic

Erläuterung:

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

Gibt die Teilmenge in umgekehrter Reihenfolge zurück

Graham
quelle
0

Oracle SQL, 77 Byte

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

Testen Sie in 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')
Trockener Humor
quelle
0

MathGolf , 8 Bytes

â^mÉ┤\*─

Probieren Sie es online!

Erläuterung

â         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

Alternatives Ausgabeformat

Mit einem flexibleren Ausgabeformat (das meiner Meinung nach recht gut aussieht) kann ich ein 6-Byte-Format erstellen:

â^É┤\*

Anstatt zuzuordnen, verwende ich das implizite For-Each und überspringe die Abflachung. Die Ausgabe sieht folgendermaßen aus:

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

F # (Mono) , 45 Bytes

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

Probieren Sie es online!

Ich habe auch eine generische / rekursive Funktion implementiert, aber sie ist ziemlich hässlich und die Anzahl der Bytes ist sehr hoch größer ...

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

Probieren Sie es online!

Dana
quelle
0

05AB1E , 6 Bytes

bRSƶ0K

Probieren Sie es online aus oder überprüfen Sie alle möglichen Testfälle .

Erläuterung:

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

Java 8, 58 Bytes

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

Probieren Sie es online aus.

Erläuterung:

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
quelle