17
\$\begingroup\$

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 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 , shortest wins.

\$\endgroup\$
5
  • 9
    \$\begingroup\$ Presumably you're only interested in enumerating finite pure sets, there being too many infinite ones to be able to enumerate them anyway. \$\endgroup\$
    – Neil
    Jun 17 at 7:18
  • \$\begingroup\$ Related: Make every fixed list \$\endgroup\$
    – tsh
    Jun 17 at 7:53
  • \$\begingroup\$ @VisualMelon What do you mean by that? I see no answers that do that, and they would be invalid. Also, finite pure sets are definitely countable. \$\endgroup\$
    – emanresu A
    Jun 19 at 9:00
  • \$\begingroup\$ @emanresuA You need to specify in your question that only the recursively finite pure sets should be enumerated. (See en.wikipedia.org/wiki/Hereditarily_finite_set). \$\endgroup\$
    – Tyilo
    Jun 20 at 11:20
  • \$\begingroup\$ @Tyilo I think that's obvious. \$\endgroup\$
    – emanresu A
    Jun 20 at 11:22

13 Answers 13

17
\$\begingroup\$

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.

\$\endgroup\$
2
7
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
0
4
\$\begingroup\$

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 [].

\$\endgroup\$
4
\$\begingroup\$

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
  • recurse on each filtered index.
\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ A really clever way to do recursion! But it's shorter to define a function instead of a closure: struct K(Vec<K>);fn f(x:u64)->K{K((0..x).filter(|v|x>>v&1>0).map(f).collect())} \$\endgroup\$
    – alephalpha
    Jun 17 at 10:19
  • \$\begingroup\$ @alephalpha thanks, I was so convinced lambdas where shorter that I never considered their disadvantages \$\endgroup\$
    – mousetail
    Jun 17 at 10:46
4
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 15 bytes

FN⊞υΦυ&ιX²λ⭆¹⊟υ

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

FN

Repeat n times.

⊞υΦυ&ιX²λ

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Ruby, 39 bytes

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

Try it online!

Based on pxeger's python answer.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can just use 0..n. \$\endgroup\$
    – pxeger
    Jun 19 at 12:25
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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