Smalltalk › Pharo › Pharo Smalltalk Developers

powerSet

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

11 messages Options

stepharo

powerSet

Hi

I was programming an exercise with one of my son (well in Python....
arghhhhhh)
and I end it up doing it in Pharo (I'm save now).

The idea was to write one function that computes the powerset

powerset(4)
= a Set(a Set(1) a Set(1 2) a Set(3) a Set(2) a Set(1 3) a Set(2 3)
a Set(1 2 3) a Set(4) a Set(1 4) a Set(2 4) a Set(1 2 4) a Set(3 4) a
Set(1 3 4) a Set(2 3 4) a Set(1 2 3 4))

I did it without thinking too much in fact

| s n ps |
ps := Set new.

1 to: ((2 raisedTo: 4) -1)
do: [ :i |
s := Set new.
n := 0.
1 to: 4 do: [ :b |
n := n + 1.
((i bitAt: b) = 1 )
ifTrue: [ s add: n].
ps add: s ]].
ps

but I wonder if we want to add it to our lib.

Stef

CyrilFerlicot

Re: powerSet

Le 22/10/2015 22:58, stepharo a écrit :

> Hi
>
> I was programming an exercise with one of my son (well in Python....
> arghhhhhh)
> and I end it up doing it in Pharo (I'm save now).
>
> The idea was to write one function that computes the powerset
>
> powerset(4)
> = a Set(a Set(1) a Set(1 2) a Set(3) a Set(2) a Set(1 3) a Set(2 3)
> a Set(1 2 3) a Set(4) a Set(1 4) a Set(2 4) a Set(1 2 4) a Set(3 4) a
> Set(1 3 4) a Set(2 3 4) a Set(1 2 3 4))
>
> I did it without thinking too much in fact
>
> | s n ps |
> ps := Set new.
>
> 1 to: ((2 raisedTo: 4) -1)
> do: [ :i |
> s := Set new.
> n := 0.
> 1 to: 4 do: [ :b |
> n := n + 1.
> ((i bitAt: b) = 1 )
> ifTrue: [ s add: n].
> ps add: s ]].
> ps
>
> but I wonder if we want to add it to our lib.
>
> Stef
>

Hi,

Want would be the uses of this method?

--
Cyril Ferlicot

http://www.synectique.eu

165 Avenue Bretagne
Lille 59000 France

signature.asc (836 bytes) Download Attachment

Vincent Blondeau

Re: powerSet

Hi,

I propose a simpler implementation:
4 in: [ :e | (1 to: e) combinations ]

Vincent

Le 2015-10-22 23:25, Ferlicot D. Cyril a écrit :

> Le 22/10/2015 22:58, stepharo a écrit :
>> Hi
>>
>> I was programming an exercise with one of my son (well in Python....
>> arghhhhhh)
>> and I end it up doing it in Pharo (I'm save now).
>>
>> The idea was to write one function that computes the powerset
>>
>> powerset(4)
>> = a Set(a Set(1) a Set(1 2) a Set(3) a Set(2) a Set(1 3) a Set(2
>> 3)
>> a Set(1 2 3) a Set(4) a Set(1 4) a Set(2 4) a Set(1 2 4) a Set(3 4)
>> a
>> Set(1 3 4) a Set(2 3 4) a Set(1 2 3 4))
>>
>> I did it without thinking too much in fact
>>
>> | s n ps |
>> ps := Set new.
>>
>> 1 to: ((2 raisedTo: 4) -1)
>> do: [ :i |
>> s := Set new.
>> n := 0.
>> 1 to: 4 do: [ :b |
>> n := n + 1.
>> ((i bitAt: b) = 1 )
>> ifTrue: [ s add: n].
>> ps add: s ]].
>> ps
>>
>> but I wonder if we want to add it to our lib.
>>
>> Stef
>>
>
> Hi,
>
> Want would be the uses of this method?

stepharo

Re: powerSet

> Hi,
>
> I propose a simpler implementation:
> 4 in: [ :e | (1 to: e) combinations ]
;)
I'm do not think that my son is allowed to use combination in python too.

did you check the implementation of combinations :)?

Stef

>
> Vincent
>
> Le 2015-10-22 23:25, Ferlicot D. Cyril a écrit :
>> Le 22/10/2015 22:58, stepharo a écrit :
>>> Hi
>>>
>>> I was programming an exercise with one of my son (well in Python....
>>> arghhhhhh)
>>> and I end it up doing it in Pharo (I'm save now).
>>>
>>> The idea was to write one function that computes the powerset
>>>
>>> powerset(4)
>>> = a Set(a Set(1) a Set(1 2) a Set(3) a Set(2) a Set(1 3) a Set(2 3)
>>> a Set(1 2 3) a Set(4) a Set(1 4) a Set(2 4) a Set(1 2 4) a Set(3 4) a
>>> Set(1 3 4) a Set(2 3 4) a Set(1 2 3 4))
>>>
>>> I did it without thinking too much in fact
>>>
>>> | s n ps |
>>> ps := Set new.
>>>
>>> 1 to: ((2 raisedTo: 4) -1)
>>> do: [ :i |
>>> s := Set new.
>>> n := 0.
>>> 1 to: 4 do: [ :b |
>>> n := n + 1.
>>> ((i bitAt: b) = 1 )
>>> ifTrue: [ s add: n].
>>> ps add: s ]].
>>> ps
>>>
>>> but I wonder if we want to add it to our lib.
>>>
>>> Stef
>>>
>>
>> Hi,
>>
>> Want would be the uses of this method?
>
>
>

stepharo

Re: powerSet

In reply to this post by CyrilFerlicot

> Hi,
>
> Want would be the uses of this method?

Apparently this is something really common on sets, you get all the
subparts combinations.

Stef

Sven Van Caekenberghe-2

Re: powerSet

> On 23 Oct 2015, at 09:41, stepharo <[hidden email]> wrote:
>
>> Hi,
>>
>> Want would be the uses of this method?
>
> Apparently this is something really common on sets, you get all the subparts combinations.
>
> Stef

https://en.wikipedia.org/wiki/Power_set

The empty set should apparently be part of it too, which is explicitly not done with #combinations (a new method in Pharo 5 BTW).

There is also an elegant recursive algorithm described in the Wikipedia page.

Stephan Eggermont-3

Re: powerSet

In reply to this post by CyrilFerlicot

On 22-10-15 23:25, Ferlicot D. Cyril wrote:
> Want would be the uses of this method?

Show how to run out of memory real quickly?
Demonstrate why you want generators?

Stephan

cedreek

Re: powerSet

Hi all,

just bouncing on this subject as we had this interesting discussions some time ago:

http://forum.world.st/Another-extension-proposal-gt-subsets-td107678.html

Cheers,

Cédrick

monty-3

Re: powerSet

In reply to this post by stepharo

The wiki entry says powersets have 2^n elements where n is the number of elements in the original set. 2^n grows exponentially fast:

2^5 = 35
2^10 = 1024
2^50 = 1125899906842624
2^100 = 1267650600228229401496703205376

So if it's added, bounding it to only support small collections is not a bad idea. 2^30 = 1,073,741,824, so 30 element collections are too big (with 1GB address space). But <= 25 elements would be OK: 2^25 = 33,554,432

I actually needed something like this a few months ago, so there are usecases.

> Sent: Thursday, October 22, 2015 at 4:58 PM
> From: stepharo <[hidden email]>
> To: "Pharo Development List" <[hidden email]>
> Subject: [Pharo-dev] powerSet
>
> Hi
>
> I was programming an exercise with one of my son (well in Python....
> arghhhhhh)
> and I end it up doing it in Pharo (I'm save now).
>
> The idea was to write one function that computes the powerset
>
> powerset(4)
> = a Set(a Set(1) a Set(1 2) a Set(3) a Set(2) a Set(1 3) a Set(2 3)
> a Set(1 2 3) a Set(4) a Set(1 4) a Set(2 4) a Set(1 2 4) a Set(3 4) a
> Set(1 3 4) a Set(2 3 4) a Set(1 2 3 4))
>
> I did it without thinking too much in fact
>
> | s n ps |
> ps := Set new.
>
> 1 to: ((2 raisedTo: 4) -1)
> do: [ :i |
> s := Set new.
> n := 0.
> 1 to: 4 do: [ :b |
> n := n + 1.
> ((i bitAt: b) = 1 )
> ifTrue: [ s add: n].
> ps add: s ]].
> ps
>
> but I wonder if we want to add it to our lib.
>
> Stef
>
>

Nicolas Cellier

Re: powerSet

2015-10-23 18:02 GMT+02:00 monty <[hidden email]>:

The wiki entry says powersets have 2^n elements where n is the number of elements in the original set. 2^n grows exponentially fast:

2^5 = 35
2^10 = 1024
2^50 = 1125899906842624
2^100 = 1267650600228229401496703205376

So if it's added, bounding it to only support small collections is not a bad idea. 2^30 = 1,073,741,824, so 30 element collections are too big (with 1GB address space). But <= 25 elements would be OK: 2^25 = 33,554,432

I actually needed something like this a few months ago, so there are usecases.

But as said by Stephan Eggermont, do you really need to store all the subsets together in memory, or would you just need to iterate them sequentially?

If you create the subsets, then it should better be kind of lazy.

> Sent: Thursday, October 22, 2015 at 4:58 PM
> From: stepharo <[hidden email]>
> To: "Pharo Development List" <[hidden email]>
> Subject: [Pharo-dev] powerSet

>
> Hi
>
> I was programming an exercise with one of my son (well in Python....
> arghhhhhh)
> and I end it up doing it in Pharo (I'm save now).
>
> The idea was to write one function that computes the powerset
>
> powerset(4)
> = a Set(a Set(1) a Set(1 2) a Set(3) a Set(2) a Set(1 3) a Set(2 3)
> a Set(1 2 3) a Set(4) a Set(1 4) a Set(2 4) a Set(1 2 4) a Set(3 4) a
> Set(1 3 4) a Set(2 3 4) a Set(1 2 3 4))
>
> I did it without thinking too much in fact
>
> | s n ps |
> ps := Set new.
>
> 1 to: ((2 raisedTo: 4) -1)
> do: [ :i |
> s := Set new.
> n := 0.
> 1 to: 4 do: [ :b |
> n := n + 1.
> ((i bitAt: b) = 1 )
> ifTrue: [ s add: n].
> ps add: s ]].
> ps
>
> but I wonder if we want to add it to our lib.
>
> Stef
>
>

stepharo

Re: powerSet

In reply to this post by stepharo

We tried to port this code to python and I learned that we cannot have a
set containing a set :(
and other uglies like len(str) but not str.len()

Stef

Le 22/10/15 22:58, stepharo a écrit :

> Hi
>
> I was programming an exercise with one of my son (well in Python....
> arghhhhhh)
> and I end it up doing it in Pharo (I'm save now).
>
> The idea was to write one function that computes the powerset
>
> powerset(4)
> = a Set(a Set(1) a Set(1 2) a Set(3) a Set(2) a Set(1 3) a Set(2
> 3) a Set(1 2 3) a Set(4) a Set(1 4) a Set(2 4) a Set(1 2 4) a Set(3 4)
> a Set(1 3 4) a Set(2 3 4) a Set(1 2 3 4))
>
> I did it without thinking too much in fact
>
> | s n ps |
> ps := Set new.
>
> 1 to: ((2 raisedTo: 4) -1)
> do: [ :i |
> s := Set new.
> n := 0.
> 1 to: 4 do: [ :b |
> n := n + 1.
> ((i bitAt: b) = 1 )
> ifTrue: [ s add: n].
> ps add: s ]].
> ps
>
> but I wonder if we want to add it to our lib.
>
> Stef
>
>