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
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
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?
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?
On 23 Oct 2015, at 09:41, stepharo <stepharo@free.fr> 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.
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
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 <stepharo@free.fr> To: "Pharo Development List" <pharo-dev@lists.pharo.org> 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
2015-10-23 18:02 GMT+02:00 monty <monty2@programmer.net>:
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 <stepharo@free.fr> To: "Pharo Development List" <pharo-dev@lists.pharo.org> 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
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
participants (8)
-
Cédrick Béler -
Ferlicot D. Cyril -
monty -
Nicolas Cellier -
Stephan Eggermont -
stepharo -
Sven Van Caekenberghe -
vincent.blondeau＠polytech-lille.net