# Nth subset of a set

Given the set

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

and an integer

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

find the Nth subset.

## Input/Output

N is given as an unsigned integer on stdin. You must print the Nth subset in a format suitable for your language (this may include [1,2,3],{1,2,3},[1, 2, 3],1 2 3,1,2,3 etc. for as long as it is a human readable text format).

## A little bit about subsets

There is a relationship between subsets and numbers in base two. Each digit $$d_{i}$$ specifies whether the ith element of the set is within the subset. For example 00000000 would be the empty set and 10000001 is the subset containing [1,8] (the last and first element). You get the Nth subset by converting the number into base 2 and then the subset includes all elements where $$d_{i} > 0$$. The 3rd subset (3 = 00000011) thus contains [1,2]. The rightmost digit is digit #0. It's ok to print [2,1]. The set does not have to be sorted.

Yes, the set is fixed to 1..8. The set is not part of the input. Input is just N.

Yes, you may use alternate input forms.

All expected outputs for all N: https://tio.run/##SyotykktLixN/f/fyNS02qIoP8soJd1CwSAg2kY32LPWPaoqs7jg/38A

• Is the set specifically 1 to 8, or is it any set? – Jo King Nov 24 '18 at 13:36
• I'm surprised nobody asked before: Would you be so kind to allow functions as submissions which take the input as argument and not force languages to use stdin (which some are not able to)? The question is about subsets and not fiddling with inputs. – ბიმო Nov 24 '18 at 13:53
• You don't need to tell everyone whether their solution is correct, you can restrict yourself to telling when it's not. – ბიმო Nov 24 '18 at 14:34
• Since the set is limited to 1..8, an output such as "123" would be unambiguous. Is it valid? – Arnauld Nov 24 '18 at 14:45
• Can we use 0-indexed [0,7] instead of [1,8]? – Erik the Outgolfer Nov 24 '18 at 15:11

# Jelly, 3 bytes

BUT


Try it online!

### How it works

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.

• But, but, BUT...?! – Arnauld Nov 24 '18 at 21:00
• @Arnauld BUT everything is a lie! You think everything is Binary, eh? Well... that Upended is the Truth! So, nope, not everything is Binary. Welcome to the gray area! – Erik the Outgolfer Nov 25 '18 at 11:34

# R, 52 26 bytes

which(intToBits(scan())>0)


Try it online!

Converts the input to its bits and returns the 1-based indices of where they are TRUE. That makes this a port of Dennis' Jelly answer.

Returns integer(0), the empty list of integers, for input of 0.

• Although this answer contains no IFs, ANDs, or BUTs. – ngm Nov 26 '18 at 1:11

# Python 2, 40 bytes

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


Try it online!

# Perl 6, 33 bytes

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


Try it online!

# Python 2, 42 bytes

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


Try it online!

# K4, 7 bytes

Solution:

1+&|2\:


Example:

First 10...

q)k)(1+&|2\:)@'!10
long$() ,1 ,2 1 2 ,3 1 3 2 3 1 2 3 ,4 1 4  Explanation: 1+&|2\: / the solution 2\: / convert to base-2 | / reverse & / indices where true 1+ / add 1  ## MATLAB/Octave, 3129 27 bytes @(n)9-find(dec2bin(n,8)-48)  Try it online! • @(n)9-find(dec2bin(n,8)-48) – alephalpha Nov 24 '18 at 16:35 • @alephalpha Thanks! – PieCot Nov 24 '18 at 16:37 # Japt, 7 bytes ì2 Ôi ð  Try it ì2 :Convert to base-2 digit array Ô :Reverse i :Prepend null element ð :0-based indices of truthy elements  ¤¬²Ôð¥1  Try it ¤ :Convert to base-2 string ¬ :Split ² :Push 2 Ô :Reverse ð :0-based indices of elements ¥1 : Equal to 1  # Husk, 5 bytes fN↔ḋ  Takes input as command-line argument not on stdin (I hope this is ok), try it online! ## Explanation 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 bytes s n=[x|(x,d)<-zip[8,7..]$mapM(pure[0,1])[1..8]!!n,d>0]


Outputs the set in reversed order, try it online!

### General version, 56 bytes

This will work for sets larger than $$\\{i\}_{i=1}^8\$$:

s n=[x|(x,d)<-zip[n,n-1..]$mapM(pure[0,1])[1..n]!!n,d>0]  Try it online! ## Explanation The term mapM (pure [0,1]) [1..n] generates the list (n=4) [[0,0,0,0],[0,0,0,1],[0,0,1,0],..,[1,1,1,1]] - ie. the binary representations of [0..2^n-1]. Indexing into it with n gives us the binary representation of n. Now we can just zip it with the reversed numbers [1..n] and only keep the elements where the binary-digit is non-zero:  [ x | (x,digit) <- zip [n,n-1,..1] binaryRepN, digit > 0 ]  # Charcoal, 11 bytes ↓⭆⮌↨Ｎ²×ιＩ⊕κ  Try it online! Link is to verbose version of code. If printing the answer horizontally without spaces is acceptable then the first character can be removed. Explanation:  Ｎ 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 bytes +4 bytes if a separator is mandatory +3 bytes if this separator is a comma and a leading comma is allowed f=(n,i=1)=>n?(n&1?i:'')+f(n/2,i+1):''  Try it online! # Perl 6, 21 bytes {1 X+grep$_+>*%2,^8}


Try it online!

Alternative:

{grep $_*2+>*%2,1..8}  # Common Lisp, 57 bytes (lambda(x)(dotimes(i 7)(format(logbitp i x)"~a "(1+ i))))  Try it online! # Haskell, 33 bytes s n=[x+1|x<-[0..7],odd$div n$2^x]  Try it online! 37 bytes concat.(mapM(\i->[[],[i]])[8,7..1]!!)  Try it online! Test cases from nimi. # C# (Visual C# Interactive Compiler), 49 bytes x=>Enumerable.Range(1,8).Where(y=>(1&x>>(y-1))>0)  Try it online! This solution uses pretty straightforward bit manipulation. While I don't think that 0-based indexing is allowed, I came up with a slightly shorter version that uses it... # C# (Visual C# Interactive Compiler), 45 bytes x=>Enumerable.Range(0,8).Where(y=>(1&x>>y)>0)  Try it online! # J, 13 10 bytes -3 bytes thanks to Bubbler 1+I.@|.@#:  Try it online! • – Bubbler Nov 26 '18 at 0:57 • @Bubbler Thanks! I thought I tried this - apparently not :) – Galen Ivanov Nov 26 '18 at 4:41 # Japt, 7 bytes ¢Ô¬ðÍmÄ  Test it online # Japt, 7 bytes ¤Ôð1 mÄ  Test it online ## Python 3.6, 58 bytes f=lambda n:[8-v for v,i in enumerate(f'{n:08b}')if int(i)]  # Wolfram Language (Mathematica), 32 bytes Pick[r=Range@8,BitGet[#,r-1],1]&  Try it online! # Pari/GP, 31 bytes n->[x|x<-[1..8],bittest(n,x-1)]  Try it online! # APL+WIN, 13 bytes Prompts for N: ((8⍴2)⊤⎕)/⌽⍳8  Try it online! Courtesy of Dyalog Classic Explanation: ((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  Returns subset in reverse order ## Burlesque - 8 bytes 8roR@j!!  Try it online. # Oracle SQL, 77 bytes select*from(select rownum r,value(p)from t,table(powermultiset(x))p)where:n=r  Test 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')


# MathGolf, 8 bytes

â^mÉ┤\*─


Try it online!

## Explanation

â         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


## Alternate output format

With a more flexible output format (that I personally think looks quite good) I can come up with a 6-byter:

â^É┤\*


Instead of mapping, I use the implicit for-each, and I skip the flattening. Output looks like this:

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


# Ruby, 31 bytes

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


Try it online!

# F# (Mono), 45 bytes

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


Try it online!

I also implemented a generic/recursive function, but its pretty ugly and the byte count is a lot larger...

# 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


Try it online!

# 05AB1E, 6 bytes

bRSƶ0K


Explanation:

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 bytes

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


Try it online.

Explanation:

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