Subsets of a set

0 views
Skip to first unread message

Harry Ohlsen

unread,
May 26, 2001, 9:36:35 PM5/26/01
to
I know that the Array class has a number of methods that make it usable
for storing sets.

What I need is a method that will allow me to generate all of the
subsets of a given set
that are a certain size.

For example, if my set was { 1, 2, 3, 4 } then all the subsets of size 3
would be ...

{1, 2, 3}, {1, 2, 4}, {2, 3, 4}

It will need to be a recursive routine. I tried to write one, but only
got as far as having it
generate all sets of size 1 or the whole set.

Has anyone done this before? If not, I'll just keep plugging away, but
I figure it never
hurts to ask!

TIA

Harry O.


Harry Ohlsen

unread,
May 26, 2001, 9:51:09 PM5/26/01
to
Harry Ohlsen wrote:

> I know that the Array class has a number of methods that make it usable
> for storing sets.
>
> What I need is a method that will allow me to generate all of the
> subsets of a given set
> that are a certain size.

By the way, I'd be happy to accept a routine which returns the set of ALL
subsets
(ie, the power set), because I could easily code something to extract
elements of
a given size from that.

At least, that would be fine for sets of a reasonable size, since
I actually want to
generate them all, just grouped into sets of the various possible sizes.

For any mathematicians out there, what I'm working on is something to
generate
all of the discrete topologies for a given set. Someone here recently did
it in C++, but
their code runs for a very long time and I'd like to see if I can write
something neater
in Ruby.

Also, I want to extend it to the generation of Hasse diagrams for the
topologies.


Mathieu Bouchard

unread,
May 26, 2001, 11:16:22 PM5/26/01
to
On Sun, 27 May 2001, Harry Ohlsen wrote:
> Harry Ohlsen wrote:

> By the way, I'd be happy to accept a routine which returns the set of
> ALL subsets (ie, the power set), because I could easily code something
> to extract elements of a given size from that.

Mine is not recursive, but it works anyway.

class Array; def power_each
(0...2**length).each {|i|
yield *indices(*(0...length).find_all {|j| i&(1<<j)>0 })
}
end end

[0.618,true,42,"towel",:foo].power_each {|*x| p x}

matju


David S.

unread,
May 27, 2001, 1:10:43 AM5/27/01
to
On Sun, May 27, 2001 at 11:10:05AM +0900, Harry Ohlsen wrote:
> Harry Ohlsen wrote:
>
> At least, that would be fine for sets of a reasonable size, since
> I actually want to
> generate them all, just grouped into sets of the various possible sizes.
>
> For any mathematicians out there, what I'm working on is something to
> generate
> all of the discrete topologies for a given set. Someone here recently did
> it in C++, but
> their code runs for a very long time and I'd like to see if I can write
> something neater
> in Ruby.

An alogorithm exponential in it's input size "runs for a very long time"?
Isn't that surprising ...

David S.


Harry Ohlsen

unread,
May 27, 2001, 10:09:52 PM5/27/01
to
"David S." wrote:

> An alogorithm exponential in it's input size "runs for a very long time"?
> Isn't that surprising ...
>
> David S.

Fair comment, but 4 minutes for n=8 is a bit over the top. Let's face it, 2^8
isn't a particularly big number.


Niklas Frykholm

unread,
May 28, 2001, 4:38:13 AM5/28/01
to
>What I need is a method that will allow me to generate all of the
>subsets of a given set
>that are a certain size.

class Array
def all_subsets(size)
if size==0
return [[]]
else
prev = all_subsets(size-1)
res = []
prev.each do |s|
self.each do |elem|
if not s.member?(elem)
res << s + [elem]
end
end
end
return res
end
end
end

// Niklas

Reply all
Reply to author
Forward
0 new messages