0 views

Skip to first unread message

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.

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.

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.

May 26, 2001, 11:16:22 PM5/26/01

to

On Sun, 27 May 2001, Harry Ohlsen wrote:

> 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

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:

>

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

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

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.

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.

>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

Search

Clear search

Close search

Google apps

Main menu