Enumerate all pure sets

Question

In set theory, a set is an unordered group of unique elements. A pure set is either the empty set \$\{\}\$ or a set containing only pure sets, like \$\{\{\},\{\{\}\}\}\$.

Your challenge is to write a program that enumerates all pure sets, in some order of your choice. Standard sequence rules apply - you may:

• Output all pure sets
• Take an integer \$n\$ and output the nth set by your definition
• Take an integer \$n\$ and output the first n sets.

(\$n\$ may be 0 or 1-indexed)

Pure sets may be represented in any reasonable format.

This is code-golf, shortest wins.

Answer 1

Python, 43 bytes

f=lambda x:[f(i)for i in range(x)if x>>i&1]

Attempt This Online!

Outputs the \$ n \$th set, starting at \$ 0 \$.

One way of creating a sequence of all pure sets is to encode them as binary numbers, with bits set according to which indices of pure sets they do and do not contain.

For example, the empty set contains no sets, so it has no 1 bits, and its index is \$ 0 \$.

For the set {{}}, it contains only one item, the empty set, which has index 0, so we set a 1 bit in the 0th position: \$ 1 \$.

For the set {{}, {{}}}, it contains two items: the empty set with index 0, and the previous {{}} which has index 1. Therefore, we set the 0th and 1st bits: \$ 11_2 = 3_{10} \$

My program does the reverse of this process.

This is essentially the same as my answer to Output every sublist ... eventually but operating recursively on itself.

Answer 2

K (ngn/k), 9 bytes

Port of pxeger's answer.

{o'&|2\x}

Try it online!

|2\x The argument converted to binary, reversed.
& Where, indices of 1s.
o' For each of those indices, call the function recursively.

Answer 3

Python 2, 45 bytes

-1 thanks to pxeger

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

Try it online!

A worse version of pxeger's answer. The input's binary digits encode which sets are included.

Answer 4

05AB1E, 8 bytes

ÝæΔDè}Iè

Outputs the 0-based \$n^{th}\$ value.

Try it online or verify the first few test cases.

Outputting the first \$n\$ values would be 8 bytes as well by replacing the è with £:
Try it online or verify the first few test cases.

Explanation:

Ý         # Push a list in the range [0, (implicit) input]
 æ        # Get the powerset of this list
  Δ  }    # Loop until the result no longer changes:
   D      #  Duplicate the list
    è     #  And index each inner-most integers into itself
      I   # After the loop: push the input-integer again
       è  # And index it into the list
       £  # Or alternatively leave that meany leading items from the list
          # (after which the result is output implicitly)

Try ∞<æ online to see (the infinite version of) the list it uses to reduce all inner integers down to [].

Answer 5

BQN, 20 bytes

{𝕊¨(2|·⌊𝕩÷2⊸⋆)¨⊸/↕𝕩}

Try it here!

Based on pxeger's answer.

Explanation

• ↕𝕩 range from 0 to input x
• (...)¨⊸/ filter range over predicate...
• 2|·⌊𝕩÷2⊸⋆ equivalent to floor(x / 2^i) mod 2
• S¨ recurse on each filtered index.

Answer 6

Rust, 113 79 bytes

-34 bytes thanks to @alephalpha

struct K(Vec<K>);fn f(x:u64)->K{K((0..x).filter(|v|x>>v&1>0).map(f).collect())}

Could save 2 bytes by using u8 instead but then it generates only 5 numbers before overlow. You could also use 128 bit integers to get more numbers. Algorithm copied from @pxeger.

Try it yourself: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=1dbb90a9b8347a6cd554723dedbb93e1

Answer 7

x86-64 machine code, 28 bytes

B0 7B AA EB 0B 0F B3 C6 56 96 E8 F1 FF FF FF 5E 0F BC C6 75 F0 B0 7D AA C6 07 00 C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RDI an address at which to place the result, as a null-terminated byte string, and takes the input number in ESI.

This uses the same method as most other answers, with a set's number having 1s in binary positions corresponding to its elements' numbers.

In assembly:

f:  mov al, '{'
    stosb
    jmp b
a:  btr esi, eax
    push rsi
    xchg eax, esi
    call f
    pop rsi
b:  bsf eax, esi
    jnz a
    mov al, '}'
    stosb
    mov BYTE PTR [rdi], 0
    ret

Answer 8

Jelly, 6 bytes

BṚT’߀

A recursive mondaic Link that accepts n (0-indexed) and yields the n-th pure set using the empty list as the empty set.

Try it online!

How?

BṚT’߀ - Link: non-negative integer, n
B      - convert to binary
 Ṛ     - reverse
  T    - truthy indices (1-indexed)
   ’   - decrement (vectorises)
     € - for each:
    ß  -   call this Link

Answer 9

Haskell, 49 bytes

Outputs as a lazily evaluated infinite list. Each entry is encoded as a nested list.

import Data.List
data P=P[P]
p=P<$>subsequences p

Answer 10

Vyxal, 6 bytes

λbṘTvx

Try it Online!

Port of Jelly.

λbṘTvx
λ      # Open a lambda for recursion, f(x)
 b     # Get the binary representation of x (as a list)
  Ṙ    # Reverse
   T   # Get truthy indices of that (zero-indexed)
    vx # For each, recurse

Answer 11

Charcoal, 15 bytes

ＦＮ⊞υΦυ＆ιＸ²λ⭆¹⊟υ

Try it online! Link is to verbose version of code. Outputs the 1-indexed nth set using []s. Explanation:

ＦＮ

Repeat n times.

⊞υΦυ＆ιＸ²λ

Extract the existing lists given by the binary decomposition of the current index and push the resulting list to the predefine empty list.

⭆¹⊟υ

Pretty-print the last list.

Answer 12

Retina, 53 bytes

{`\d+
{$&*_}
+`(_+)\1
$1@
_(?=((@)|(_))*)
$#2$.3*,
@

Try it online! Link includes test cases. Output's the 0-indexed nth set. Explanation:

{`

Repeat until all subsets have been constructed.

\d+
{$&*_}

Convert all integers to unary, and wrap them in {}s. Note that if the integer was 0, there were no _s, so processing stops for this integer here.

+`(_+)\1
$1@

Partially convert them to binary, but using the "digits" @_ and @. Normally for binary conversion you would then remove the @s before _s, but we only need the count of "digits", which here is simply the count of @s.

_(?=((@)|(_))*)

For each 1 in the binary representation, calculate its bit position and whether it's the last 1 bit...

$#2$.3*,

... and replace it with the position and append a , if this is not the last 1 bit.

@

Delete the remaining @s.

Answer 13

Ruby, 39 bytes

f=->n{(0...n).select{|x|n[x]>0}.map &f}

Try it online!

Based on pxeger's python answer.

Answer 14

Julia 1.0, 28 bytes

!k=[!i for i=0:k if k&2^i>0]

Try it online!

Port of pxeger's answer

Answer 15

JavaScript (Node.js), 49 bytes

f=(x,i=0)=>x?[...x&1?[f(i)]:[],...f(x>>1,i+1)]:[]

Try it online!