Nième sous-ensemble d'un ensemble

13

La tâche

Compte tenu de l'ensemble

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

et un entier

0≤N<2|S|

trouver le Nième sous-ensemble.

Entrée sortie

N est donné sous la forme d'un entier non signé sur stdin. Vous devez imprimer le sous - ensemble Nième un format adapté à votre langue (cela peut inclure [1,2,3], {1,2,3}, [1, 2, 3], 1 2 3, 1,2,3etc. , pour aussi longtemps qu'il est lisible texte le format).

Un peu sur les sous-ensembles

Il existe une relation entre les sous-ensembles et les nombres dans la base deux. Chaque chiffre spécifie si le i ème élément de l'ensemble se trouve dans le sous-ensemble. Par exemple, 00000000 serait l'ensemble vide et 10000001 est le sous-ensemble contenant (le dernier et le premier élément). Vous obtenez le Nième sous-ensemble en convertissant le nombre en base 2, puis le sous-ensemble comprend tous les éléments où . Le 3ème sous-ensemble (3 = 00000011) contient donc . Le chiffre le plus à droite est le chiffre # 0. C'est ok pour imprimer . L'ensemble n'a pas besoin d'être trié.

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

Addendums:

Oui, l'ensemble est fixé sur 1..8. L'ensemble ne fait pas partie de l'entrée. L' entrée est juste N .

Oui, vous pouvez utiliser d'autres formulaires de saisie.

Toutes les sorties attendues pour tous les N : https://tio.run/##SyotykktLixN/f/fyNS02qIoP8soJd1CwSAg2kY32LPWPaoqs7jg/38A

code-golf mroman
la source
1
L'ensemble est-il spécifiquement 1destiné à 8, ou s'agit-il d'un ensemble?
Jo King
2
Je suis surpris que personne n'ait demandé auparavant: seriez-vous si gentil de permettre des fonctions comme des soumissions qui prennent l'entrée comme argument et ne forcent pas les langages à utiliser stdin (ce que certains ne peuvent pas)? La question porte sur les sous-ensembles et non sur les intrants.
ბიმო
5
Vous n'avez pas besoin de dire à tout le monde si leur solution est correcte, vous pouvez vous limiter à dire quand elle ne l'est pas.
ბიმო
1
Puisque l'ensemble est limité à 1..8 , une sortie telle que "123"serait sans ambiguïté. Est-ce valable?
Arnauld
2
Peut-on utiliser [0,7] indexé 0 au lieu de [1,8]?
Erik the Outgolfer

Réponses:

17

Gelée , 3 octets

BUT

Essayez-le en ligne!

Comment ça fonctionne

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
la source
5
Mais, MAIS ...?!
Arnauld,
2
@Arnauld MAIS tout est un mensonge! Tu penses que tout est binaire, hein? Eh bien ... cette modification est la vérité! Donc, non, tout n'est pas binaire. Bienvenue dans la zone grise!
Erik the Outgolfer
7

R , 52 26 octets

which(intToBits(scan())>0)

Essayez-le en ligne!

Convertit l'entrée en ses bits et renvoie les indices basés sur 1 de l'endroit où ils se trouvent TRUE. Cela en fait un port de la réponse de Dennis 'Jelly .

Renvoie integer(0)la liste vide d'entiers pour l'entrée de 0.

Giuseppe
la source
Bien que cette réponse ne contienne aucun IF, AND ou BUT.
ngm
2

K4 , 7 octets

Solution:

1+&|2\:

Exemple:

10 premiers ...

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

Explication:

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

Japt, 7 octets

ì2 Ôi ð

Essayez-le

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

¤¬²Ôð¥1

Essayez-le

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

Husk , 5 octets

`fN↔ḋ

Prend l'entrée comme argument de ligne de commande pas sur stdin ( j'espère que c'est ok ), essayez-le en ligne!

Explication

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

Haskell , 55 54 octets

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

Sort l'ensemble dans l'ordre inverse, essayez-le en ligne!

Version générale, 56 octets

{i}i=18

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

Essayez-le en ligne!

Explication

Le terme mapM (pure [0,1]) [1..n]génère la liste ( n=4) [[0,0,0,0],[0,0,0,1],[0,0,1,0],..,[1,1,1,1]]- ie. les représentations binaires de [0..2^n-1]. L'indexation en elle avec nnous donne la représentation binaire de n.

Maintenant, nous pouvons juste le zipfaire avec les nombres inversés [1..n]et ne garder que les éléments où le chiffre binaire est différent de zéro:

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

Fusain , 11 octets

↓⭆⮌↨Ｎ²×ιＩ⊕κ

Essayez-le en ligne! Le lien est vers la version détaillée du code. Si l'impression de la réponse horizontalement sans espaces est acceptable, le premier caractère peut être supprimé. Explication:

    Ｎ       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
la source
1

JavaScript (ES6), 37 octets

+4 octets si un séparateur est obligatoire
+3 octets si ce séparateur est une virgule et une virgule de début est autorisée

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

Essayez-le en ligne!

Arnauld
la source
1

Lisp commun, 57 octets

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

Essayez-le en ligne!

Renzo
la source
1

J , 13 10 octets

-3 bytes thanks to Bubbler

1+I.@|.@#:

Essayez-le en ligne!

Galen Ivanov
la source
1
10 octets .
Bubbler
@Bubbler Merci! Je pensais avoir essayé cela - apparemment pas :)
Galen Ivanov
0

Python 3.6, 58 octets

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

APL + WIN, 13 octets

Invite pour N:

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

Essayez-le en ligne! Gracieuseté de Dyalog Classic

Explication:

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

Renvoie le sous-ensemble dans l'ordre inverse

Graham
la source
0

Oracle SQL, 77 octets

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

Test dans 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
la source
0

MathGolf , 8 octets

â^mÉ┤\*─

Essayez-le en ligne!

Explication

â         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

Format de sortie alternatif

Avec un format de sortie plus flexible (que je pense personnellement très bon), je peux proposer un 6 octets:

â^É┤\*

Au lieu de mapper, j'utilise l'implicite pour chacun, et je saute l'aplatissement. La sortie ressemble à ceci:

[1][2][][4][5][6][7][]
maxb
la source
0

F # (Mono) , 45 octets

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

Essayez-le en ligne!

J'ai également implémenté une fonction générique / récursive, mais son assez moche et le nombre d'octets est beaucoup plus grand ...

F # (Mono) , 107 octets

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

Essayez-le en ligne!

dana
la source
0

05AB1E , 6 octets

bRSƶ0K

Essayez-le en ligne ou vérifiez tous les cas de test possibles .

Explication:

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
la source
0

Java 8, 58 octets

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

Essayez-le en ligne.

Explication:

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