The task

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.

Addendums:

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

  • 1
    Is the set specifically 1 to 8, or is it any set? – Jo King Nov 24 at 13:36
  • 1
    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. – BMO Nov 24 at 13:53
  • 5
    You don't need to tell everyone whether their solution is correct, you can restrict yourself to telling when it's not. – BMO Nov 24 at 14:34
  • 1
    Since the set is limited to 1..8, an output such as "123" would be unambiguous. Is it valid? – Arnauld Nov 24 at 14:45
  • 2
    Can we use 0-indexed [0,7] instead of [1,8]? – Erik the Outgolfer Nov 24 at 15:11

29 Answers 29

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.
  • 3
    But, but, BUT...?! – Arnauld Nov 24 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 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 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, 31 29 27 bytes

@(n)9-find(dec2bin(n,8)-48)

Try it online!

  • 1
    @(n)9-find(dec2bin(n,8)-48) – alephalpha Nov 24 at 16:35
  • @alephalpha Thanks! – PieCot Nov 24 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

↓⭆⮌↨N²×ιI⊕κ

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:

    N       Input as a number
   ↨        Converted to base
     ²      Literal 2
  ⮌         Reversed
 ⭆          Map over bits and join
          κ Current index (0-indexed)
         ⊕  Incremented
        I   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!

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

J, 13 10 bytes

-3 bytes thanks to Bubbler

1+I.@|.@#:

Try it online!

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

Try it online or verify all possible test cases.

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`

Japt, 7 bytes

¢Ô¬ðÍmÄ

Test it online


Japt, 7 bytes

¤Ôð1 mÄ

Test it online

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.