All non-empty finite sets of positive integers

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

• I realize now that simply counting upwards from 1 and listing the set bits in each number gives exactly this. I had an altogether more complex and pointless solution in mind. Perhaps I should post another problem for all non-empty finite "lists" of positive integers (ie ordered and with repeats) or perhaps sets with multiplicities (unordered, but with repeats) – dspyz Jun 17 '12 at 8:06
• Problem fixed with extra credit; For lists, you can simply add a 0 onto all the sets in the original problem and then take the differences between successive terms. For multiplicities, just filter the lists for ones which are non-descending – dspyz Jun 17 '12 at 10:01
• Please do not change the challange after it was posted. Instead you should post it here and discuss it before it becomes an open puzzle. – Howard Jun 17 '12 at 10:19
• Thank you. If you don't mind, I will delete this question, post it there and get help with it and then repost it when I'm ready. – dspyz Jun 18 '12 at 4:06
• I'd leave it as it is. It is a valid challenge and maybe others are already working on a solution. You may of course create a new question with different scope and then discuss it in sandbox. – Howard Jun 18 '12 at 4:12

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
• Sorry I keep changing the rules on you. I'm experimenting with how to make the problem more interesting. Good solution though. – dspyz Jun 17 '12 at 9:53

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

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,3],[2,3],[1,2,3],,[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4],]

Python

Note: I wrote this version before the challenge became . 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.

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
}
}
• Perhaps I didn't clarify, when I said integers I wasn't talking about the type "int", I was talking about actual mathematical integers (the kind that can grow infinitely large). If your program uses MAX as you did, then you missed the point of the problem – dspyz Jun 18 '12 at 6:26
• @dspyz: I missed that point initially, but luckily, my first solution could easily be widened to work for Sets of random size. – user unknown Jun 18 '12 at 14:39

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

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.