Re: [Pharo-dev] powerSet
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 arghh) 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
Re: [Pharo-dev] powerSet
2015-10-23 18:02 GMT+02:00 monty : > 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 > > To: "Pharo Development List" > > Subject: [Pharo-dev] powerSet > > > > Hi > > > > I was programming an exercise with one of my son (well in Python > > arghh) > > 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 > > > > > >
Re: [Pharo-dev] powerSet
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 > To: "Pharo Development List" > Subject: [Pharo-dev] powerSet > > Hi > > I was programming an exercise with one of my son (well in Python > arghh) > 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 > >
Re: [Pharo-dev] 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
Re: [Pharo-dev] powerSet
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
Re: [Pharo-dev] powerSet
> On 23 Oct 2015, at 09:41, stepharo 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.
Re: [Pharo-dev] powerSet
Hi, Want would be the uses of this method? Apparently this is something really common on sets, you get all the subparts combinations. Stef
Re: [Pharo-dev] 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 arghh) 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?
Re: [Pharo-dev] 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 arghh) 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?
Re: [Pharo-dev] powerSet
Le 22/10/2015 22:58, stepharo a écrit : > Hi > > I was programming an exercise with one of my son (well in Python > arghh) > 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 Description: OpenPGP digital signature
[Pharo-dev] powerSet
Hi I was programming an exercise with one of my son (well in Python arghh) 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
