[if this isn't the correct spot, let me know and I'll gladly take it elsewhere] I have found myself needing powerset functionality several times recently to the point where I wondered if there's interest in making it part of the standard library. I have a working implementation and tests. Would take but 3 minutes to add it in and issue a pull request, but I'd like to know if there's interest from esteemed group members. Thanks for the quick turnaround. -- H -- OpenPGP: https://sks-keyservers.net/pks/lookup?op=get&search=0xFEBAD7FFD041BBA1 If you wish to request my time, please do so using bit.ly/hd1AppointmentRequest. Si vous voudrais faire connnaisance, allez a bit.ly/hd1AppointmentRequest. Sent from my mobile device Envoye de mon portable
Hi Hassan, I think this is unlikely to get added to the standard library as it is listed as a recipe in the itertools module ( https://docs.python.org/3/library/itertools.html#itertools-recipes). You may want to check out the more-itertools package ( https://more-itertools.readthedocs.io/en/latest/) which includes all the recipes listed, as well as some other functions. On Mon, Oct 15, 2018 at 8:16 PM Hasan Diwan <hasan.diwan@gmail.com> wrote:
-- Sebastian Kreft
Hi Hasan, and welcome, On Mon, Oct 15, 2018 at 11:15:47AM -0700, Hasan Diwan wrote:
This is certainly the right place to discuss this, but you shouldn't assume that everyone reading will know what powerset functionality you are referring to. Is it the same as the recipe in the itertools documentation? https://docs.python.org/3/library/itertools.html#itertools-recipes Can you make a case for why it is important and useful enough to be put into the std lib? Every new function increases the burden on both the Python developers maintaining the stdlib, and new users learning to use the language. So you need to make a case for why the benefit outweighs the costs. -- Steve
Yes pretty much.
The best case I've come up with is one of obviousness. When looking for the powerset implementation in the cpython source, grepping for itertools.chain is not an obvious, at least to me, vector for a solution. -- H -- OpenPGP: https://sks-keyservers.net/pks/lookup?op=get&search=0xFEBAD7FFD041BBA1 If you wish to request my time, please do so using bit.ly/hd1AppointmentRequest. Si vous voudrais faire connnaisance, allez a bit.ly/hd1AppointmentRequest. Sent from my mobile device Envoye de mon portable
Is there a name for an iteration of the powerset which is more useful for binary search? I.e. instead of starting with null set, start with the "middle" ( r/2 ). Maybe a bit OT, but is there a name for such a combinatorial search? On Monday, October 15, 2018, Hasan Diwan <hasan.diwan@gmail.com> wrote:
Wes Turner wrote:
You'll have to provide more detail about what you want to search and how you intend to search it. There isn't a single "middle" to the set of powersets, since in general there are many subsets with about half the elements of the original set. Also there is no obvious ordering to use for bisection. -- Greg
On Tuesday, October 16, 2018, Greg Ewing <greg.ewing@canterbury.ac.nz> wrote:
When searching for combinations of factors which most correlate to the dependent variable, it doesn't always make sense to start with single factors; especially when other factors 'cancel out'. For example, in clinical medicine, differential diagnosis is a matter of determining what the most likely diagnosis/es is/are; given lots of noise and one or more differentiating factors. Testing individual factors first may not be the most efficient because combinations/permutations are more likely to be highly correlated with specific diagnoses. Random search of the powerset and mutation (or a neuralnet) may be faster anyways. Just wondering whether there's a name for differently ordered powerset (and Cartesian product) traversals? Obviously, this is combinatorics and set theory (category theory (HOTT)); here in the itertools library for iterables.
Wes Turner wrote:
Obviously, this is combinatorics and set theory (category theory (HOTT)); here in the itertools library for iterables.
Powerset is a small problem, and HoTT is a big solution. I know this because I've got the standard book sitting, largely unread, on my bookshelf for over a year. https://en.wikipedia.org/wiki/Homotopy_type_theory https://homotopytypetheory.org/book/ HoTT is based on the Coq Proof Assistant: https://coq.inria.fr/. One of the applications of CoQ is certification of properties of programming languages. And now we're a long way from the original post and topic. -- Jonathan
Not that I know of, especially since this has the unfortunate drawback that you're going through the largest part of the search space first. Usually, I find that I want to do the opposite from this; go from both ends simultaneously. Hasan, if you recall that the powerset is just `yield from S choose k for k from 0 to |S|+1`, you see that that is exactly the implementation in the examples page. Best regards, Pål GD
On Mon, 15 Oct 2018 at 23:25, Pål Grønås Drange <paal.drange@gmail.com> wrote:
I know that, but when one searches for a powerset function, the logical place to look isn't itertools, it's the set class. -- H -- OpenPGP: https://sks-keyservers.net/pks/lookup?op=get&search=0xFEBAD7FFD041BBA1 If you wish to request my time, please do so using bit.ly/hd1AppointmentRequest. Si vous voudrais faire connnaisance, allez a bit.ly/hd1AppointmentRequest. Sent from my mobile device Envoye de mon portable
[...] when one searches for a powerset function, the logical place to look isn't itertools, it's the set class. -- H
That's a rather object-oriented view, I think. So you look for the permutation function in the list class? I prefer these functions gathered in one place, and I find that itertools does the job. I do however agree that there could be a powerset function there for convenience, but only +0. - Pål GD
Pal, On Tue, 16 Oct 2018 at 01:36, Pål Grønås Drange <paal.drange@gmail.com> wrote:
I do however agree that there could be a powerset function there for convenience, but only +0.
That is the best argument I could come up with to justify a set#powerset method. -- H -- OpenPGP: https://sks-keyservers.net/pks/lookup?op=get&search=0xFEBAD7FFD041BBA1 If you wish to request my time, please do so using bit.ly/hd1AppointmentRequest. Si vous voudrais faire connnaisance, allez a bit.ly/hd1AppointmentRequest. Sent from my mobile device Envoye de mon portable
Can we get an utilisation context ? I don't think it belongs in the stdlib alone on the basis that its output is not linear in the size of its input (but exponential), so it explode even for a mid-sized list, which by nature limits greatly its usage. The question would be wether or not it is used enough to push it to itertools, which is pretty hard to decide with no examples. 2018-10-16 10:41 GMT+02:00 Hasan Diwan <hasan.diwan@gmail.com>:
-- -- *Nicolas Rolin* | Data Scientist + 33 631992617 - nicolas.rolin@tiime.fr <prenom.nom@tiime.fr> *15 rue Auber, **75009 Paris* *www.tiime.fr <http://www.tiime.fr>*
"more-itertools" seems to be a modestly popular library (top 100-500?) that includes the stdlib itertools recipes and more. https://more-itertools.readthedocs.io/en/stable/api.html#more_itertools.powe... On Tue, Oct 16, 2018 at 3:42 AM Hasan Diwan <hasan.diwan@gmail.com> wrote:
Hi Hassan, I think this is unlikely to get added to the standard library as it is listed as a recipe in the itertools module ( https://docs.python.org/3/library/itertools.html#itertools-recipes). You may want to check out the more-itertools package ( https://more-itertools.readthedocs.io/en/latest/) which includes all the recipes listed, as well as some other functions. On Mon, Oct 15, 2018 at 8:16 PM Hasan Diwan <hasan.diwan@gmail.com> wrote:
-- Sebastian Kreft
Hi Hasan, and welcome, On Mon, Oct 15, 2018 at 11:15:47AM -0700, Hasan Diwan wrote:
This is certainly the right place to discuss this, but you shouldn't assume that everyone reading will know what powerset functionality you are referring to. Is it the same as the recipe in the itertools documentation? https://docs.python.org/3/library/itertools.html#itertools-recipes Can you make a case for why it is important and useful enough to be put into the std lib? Every new function increases the burden on both the Python developers maintaining the stdlib, and new users learning to use the language. So you need to make a case for why the benefit outweighs the costs. -- Steve
Yes pretty much.
The best case I've come up with is one of obviousness. When looking for the powerset implementation in the cpython source, grepping for itertools.chain is not an obvious, at least to me, vector for a solution. -- H -- OpenPGP: https://sks-keyservers.net/pks/lookup?op=get&search=0xFEBAD7FFD041BBA1 If you wish to request my time, please do so using bit.ly/hd1AppointmentRequest. Si vous voudrais faire connnaisance, allez a bit.ly/hd1AppointmentRequest. Sent from my mobile device Envoye de mon portable
Is there a name for an iteration of the powerset which is more useful for binary search? I.e. instead of starting with null set, start with the "middle" ( r/2 ). Maybe a bit OT, but is there a name for such a combinatorial search? On Monday, October 15, 2018, Hasan Diwan <hasan.diwan@gmail.com> wrote:
Wes Turner wrote:
You'll have to provide more detail about what you want to search and how you intend to search it. There isn't a single "middle" to the set of powersets, since in general there are many subsets with about half the elements of the original set. Also there is no obvious ordering to use for bisection. -- Greg
On Tuesday, October 16, 2018, Greg Ewing <greg.ewing@canterbury.ac.nz> wrote:
When searching for combinations of factors which most correlate to the dependent variable, it doesn't always make sense to start with single factors; especially when other factors 'cancel out'. For example, in clinical medicine, differential diagnosis is a matter of determining what the most likely diagnosis/es is/are; given lots of noise and one or more differentiating factors. Testing individual factors first may not be the most efficient because combinations/permutations are more likely to be highly correlated with specific diagnoses. Random search of the powerset and mutation (or a neuralnet) may be faster anyways. Just wondering whether there's a name for differently ordered powerset (and Cartesian product) traversals? Obviously, this is combinatorics and set theory (category theory (HOTT)); here in the itertools library for iterables.
Wes Turner wrote:
Obviously, this is combinatorics and set theory (category theory (HOTT)); here in the itertools library for iterables.
Powerset is a small problem, and HoTT is a big solution. I know this because I've got the standard book sitting, largely unread, on my bookshelf for over a year. https://en.wikipedia.org/wiki/Homotopy_type_theory https://homotopytypetheory.org/book/ HoTT is based on the Coq Proof Assistant: https://coq.inria.fr/. One of the applications of CoQ is certification of properties of programming languages. And now we're a long way from the original post and topic. -- Jonathan
Not that I know of, especially since this has the unfortunate drawback that you're going through the largest part of the search space first. Usually, I find that I want to do the opposite from this; go from both ends simultaneously. Hasan, if you recall that the powerset is just `yield from S choose k for k from 0 to |S|+1`, you see that that is exactly the implementation in the examples page. Best regards, Pål GD
On Mon, 15 Oct 2018 at 23:25, Pål Grønås Drange <paal.drange@gmail.com> wrote:
I know that, but when one searches for a powerset function, the logical place to look isn't itertools, it's the set class. -- H -- OpenPGP: https://sks-keyservers.net/pks/lookup?op=get&search=0xFEBAD7FFD041BBA1 If you wish to request my time, please do so using bit.ly/hd1AppointmentRequest. Si vous voudrais faire connnaisance, allez a bit.ly/hd1AppointmentRequest. Sent from my mobile device Envoye de mon portable
[...] when one searches for a powerset function, the logical place to look isn't itertools, it's the set class. -- H
That's a rather object-oriented view, I think. So you look for the permutation function in the list class? I prefer these functions gathered in one place, and I find that itertools does the job. I do however agree that there could be a powerset function there for convenience, but only +0. - Pål GD
Pal, On Tue, 16 Oct 2018 at 01:36, Pål Grønås Drange <paal.drange@gmail.com> wrote:
I do however agree that there could be a powerset function there for convenience, but only +0.
That is the best argument I could come up with to justify a set#powerset method. -- H -- OpenPGP: https://sks-keyservers.net/pks/lookup?op=get&search=0xFEBAD7FFD041BBA1 If you wish to request my time, please do so using bit.ly/hd1AppointmentRequest. Si vous voudrais faire connnaisance, allez a bit.ly/hd1AppointmentRequest. Sent from my mobile device Envoye de mon portable
Can we get an utilisation context ? I don't think it belongs in the stdlib alone on the basis that its output is not linear in the size of its input (but exponential), so it explode even for a mid-sized list, which by nature limits greatly its usage. The question would be wether or not it is used enough to push it to itertools, which is pretty hard to decide with no examples. 2018-10-16 10:41 GMT+02:00 Hasan Diwan <hasan.diwan@gmail.com>:
-- -- *Nicolas Rolin* | Data Scientist + 33 631992617 - nicolas.rolin@tiime.fr <prenom.nom@tiime.fr> *15 rue Auber, **75009 Paris* *www.tiime.fr <http://www.tiime.fr>*
"more-itertools" seems to be a modestly popular library (top 100-500?) that includes the stdlib itertools recipes and more. https://more-itertools.readthedocs.io/en/stable/api.html#more_itertools.powe... On Tue, Oct 16, 2018 at 3:42 AM Hasan Diwan <hasan.diwan@gmail.com> wrote:
participants (9)
-
Greg Ewing -
Hasan Diwan -
Jonathan Fine -
Nick Timkovich -
Nicolas Rolin -
Pål Grønås Drange -
Sebastian Kreft -
Steven D'Aprano -
Wes Turner