Asp Forum - Translate from Python to Ruby

Sam Kong

12/23/2005 10:48:00 PM

Hi!

I am trying to get a powerset (all subsets) of a set.
I couldn't find a code in Ruby, but I found a code in Python.
I'm trying to convert it to Ruby but it's not done easily.

def powset(seq):
if seq:
head, tail = seq[:1], seq[1:]
for smaller in powset(tail):
yield smaller
yield head + smaller
else:
yield []

1. Can somebody translate the Python code into Ruby?
(I have difficulty in understanding the yield part)

2. Actually I want to add a method to Set class.
How can I change the function into a method which won't take any
parameter.
(Can a method be recursive if it doesn't take a parameter?
Maybe not.
Do I need a helper private method?)
example:
s = Set[1,2,3]
ps = s.powerset #returns a set of powerset of s

Thanks.

Sam

6 Answers

Marcin Mielzynski

12/24/2005 12:21:00 AM

Sam Kong wrote:
> Hi!
>
> I am trying to get a powerset (all subsets) of a set.
> I couldn't find a code in Ruby, but I found a code in Python.
> I'm trying to convert it to Ruby but it's not done easily.
>
> def powset(seq):
> if seq:
> head, tail = seq[:1], seq[1:]
> for smaller in powset(tail):
> yield smaller
> yield head + smaller
> else:
> yield []
>
> 1. Can somebody translate the Python code into Ruby?
> (I have difficulty in understanding the yield part)
>

def powset seq
unless seq.empty?
head,tail = seq[0,1] , seq[1..-1]
powset(tail){|smaller|
yield smaller
yield head + smaller
}
else
yield []
end
end

powset([1,2,5]){|e| p e}

not sure if it works for other examples

lopex

Stefan Walk

12/24/2005 12:29:00 AM

Non-recursive version:
I'm sure you can translate this for sets...

class Array
def powset
ret = []
0.upto(2**size - 1) do |n|
ret << []
0.upto(size - 1) do |i|
ret.last << self[i] if (n & (1 << i)) != 0
end
end
ret
end
end

p [].powset
p [1].powset
p [1,2].powset
p [1,2,3].powset
[[]]
[[], [1]]
[[], [1], [2], [1, 2]]
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Simon Kröger

12/24/2005 12:56:00 AM

Sorry, i couldn't resist:

class Array
def powset
(0...(2**size)).map do |n|
(0...size).reject{|i|n[i].zero?}.map{|i|at(i)}
end
end
end

cheers

Simon

Stefan Walk wrote:

> Non-recursive version:
> I'm sure you can translate this for sets...
>
> class Array
> def powset
> ret = []
> 0.upto(2**size - 1) do |n|
> ret << []
> 0.upto(size - 1) do |i|
> ret.last << self[i] if (n & (1 << i)) != 0
> end
> end
> ret
> end
> end
>
> p [].powset
> p [1].powset
> p [1,2].powset
> p [1,2,3].powset
> [[]]
> [[], [1]]
> [[], [1], [2], [1, 2]]
> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
>
>

Florian Groß

12/24/2005 1:05:00 AM

Ken

12/24/2005 6:25:00 PM

require 'set'

class Set
def powerset
result = Set.new
for element_map in 0...(1 << self.length) do
subset = Set.new
each_with_index do |element, index|
subset.add(element) if element_map[index] == 1
end
result.add(subset)
end
return result
end
end

s = Set[1,2,3]
ps = s.powerset #returns a set of powerset of s
p ps

--
Posted via http://www.ruby-....

Michael 'entropie' Trommer

12/27/2005 5:42:00 PM

* Simon Kr?ger (SimonKroeger@gmx.de) wrote:
> Sorry, i couldn't resist:
>
> class Array
> def powset
> (0...(2**size)).map do |n|
> (0...size).reject{|i|n[i].zero?}.map{|i|at(i)}
> end
> end
> end

lovely peace of code!
(it makes my brain burning but its nice!)
>
> cheers
>
> Simon
>
> Stefan Walk wrote:
>
> >Non-recursive version:
> >I'm sure you can translate this for sets...
> >
> >class Array
> > def powset
> > ret = []
> > 0.upto(2**size - 1) do |n|
> > ret << []
> > 0.upto(size - 1) do |i|
> > ret.last << self[i] if (n & (1 << i)) != 0
> > end
> > end
> > ret
> > end
> >end
> >
> >p [].powset
> >p [1].powset
> >p [1,2].powset
> >p [1,2,3].powset
> >[[]]
> >[[], [1]]
> >[[], [1], [2], [1, 2]]
> >[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
> >
> >
>
>
So long
--
Michael 'entropie' Trommer; http:/...

ruby -e "0.upto((a='njduspAhnbjm/dpn').size-1){|x| a[x]-=1}; p 'mailto:'+a"

comp.lang.ruby

Translate from Python to Ruby