All non-empty finite sets of positive integers

Question

The challenge is to create an iterator(/generator) which iterates (in any order so as to reach all of them... ie no set should occur at infinity) over all possible non-empty finite sets(/tuples/lists) of positive integers (hence demonstrating their countability).

Since the problem of verifying the correctness of a solution is undecidable in some cases, an accompanying explanation of how your program works and what order the sets are returned in would be helpful

Each finite set should occur exactly once. So if left running long enough, the iterator should eventually hit each of {1}, {3,5}, {17,29,306} etc. exactly once

Answer 1

GolfScript, 21 characters

;]]0{)\{.2$+.p}%\1}do

A GolfScript version which prints all generated sets. It basically does the same as my Python version although not by recursion but instead collecting all possible sets in an array.

;        // clear the stack
]]       // put [[]] on the stack - the array of generated sets 
            (initially an array with only the empty set)
0        // counter starts with zero
{        // start of infinite loop
  )      // increase counter
  \{     // map for each item of the array
    .    // duplicate item (i.e. this is a set)
    2$+  // append counter
    .p   // print the newly generated set
  }%\    // end of map => now the array contains all sets with max. up to counter
1} do    // end of infinite loop

Answer 2

Why mess with iterators and suchlike if we can just return an infinite (lazy) list?

Haskell, 40

s(α:η)=[α]:(s η>>=(\κ->[κ,α:κ]))
c=s[1..]

Works thusly:

s(α:η)                    --the nonempty subsets of the list beginning with α, followed by η
   =[α]                   --  are: the singleton set [α]
      :(s η               --       and all nonempty subsets of η,
          >>=(\κ->[ κ     --         once on their own
                  , α:κ ] --         and once with α prepended to each of them.
                         ))
c=s[1..]       --c is the list of all nonempty subsets of the naturals.

Demonstration:

Prelude> take 16 c
[[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4],[5]]

Answer 3

Python

Note: I wrote this version before the challenge became code-golf. I'll leave it here until I have a new one.

def allsets():

  def setswithmax(n):
    yield [n]

    for m in range(1,n):
      for s in setswithmax(m):
        yield s+[n]

  n = 1
  while n:
    for s in setswithmax(n):
      yield s
    n = n+1

It enumerates the sets with increasing maximum element, i.e. first of all it will generate all sets where max element is 1, then 2, ...

It does so by calling the generator setswithmax for increasing argument, which recursively builds these sets, i.e. a set with maximum n is obtained by iterating all sets with arbitrary max <n and then appending n to these sets.

You can see it in action on ideone.

Answer 4

Scala 265:

object C extends Iterator[Set[Int]]{
var c=1
var M=1
var s=(1 to M)
var i:Iterator[Seq[Int]]=_
def n{i=s.combinations(c)}
def hasNext=true
n
def next:Set[Int]={
if(!i.hasNext)
if(c<M){
c+=1
n}else{c=1
M+=1
s=(1 to M)
n}
val r=i.next
if(r.max<M)next else r.toSet
}
}

Iterator is a well defined type in Scala, which means you have to declare what it returns (Set[Int]) in our case) and implement a method next and hasNext. For infinite Sets, hasNext trivially just returns true.

Here is code for testing:

object Cg6394IteratorTest extends App {
  val ci = C
  println (ci.take (1000).mkString ("\n"))
}

output:

Set(1)
Set(2)
Set(1, 2)
Set(3)
Set(1, 3)
Set(2, 3)
Set(1, 2, 3)
Set(4)
Set(1, 4)
Set(2, 4)
Set(3, 4)
Set(1, 2, 4)
Set(1, 3, 4)
Set(2, 3, 4)
Set(1, 2, 3, 4)

ungolfed:

object Cg6394Iterator extends Iterator [Set[Int]] {

  var curLength = 1
  var MAX = 1
  var source = (1 to MAX)
  var iter: Iterator [Seq[Int]] = _

  def init { iter = source.combinations (curLength)}
  def hasNext: Boolean = true

  init

  def next : Set[Int] = {
    if (! iter.hasNext)
      if (curLength < MAX) {
        curLength += 1
        init
       } else {
         curLength = 1
         MAX = MAX + 1
         source = (1 to MAX)
         init 
       }
     val coll = iter.next ()
     if (coll.max < MAX) next else coll.toSet
  }
}

Answer 5

Stax, 7 bytes

âe¢-ï♂~

The link below adds a footer to output the generated sets

Run and debug online!

Explanation

Uses ASCII representation to explain:

zWiRSca-
z           Empty set
 W          Loop forever
  iR        Range [1..current loop index]
    S       Powerset (*)
     ca-    Remove the powerset of [1..(current loop index-1)] from (*)

The footer is mJ, which outputs every generated set on a line, with the element separated by spaces.

Answer 6

Python, 88

Simple implementation, like mentioned, counter and checking for bits in binary representation.

def P():
 i=1
 while 1:yield [n+1 for n,x in enumerate(bin(i)[2:][::-1])if x=='1'];i+=1