Re: [Python-ideas] Powerset

[Nick Timkovich]

"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.powerset

On Tue, Oct 16, 2018 at 3:42 AM Hasan Diwan  wrote:

> Pal,
> On Tue, 16 Oct 2018 at 01:36, Pål Grønås Drange 
> 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=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
> ___
> Python-ideas mailing list
> Python-ideas@python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Powerset

[Wes Turner]

On Tuesday, October 16, 2018, Greg Ewing 
wrote:

> Wes Turner wrote:
>
>> 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 ).
>>
>
> 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.


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.


> --
> Greg
> ___
> Python-ideas mailing list
> Python-ideas@python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Powerset

[Nicolas Rolin]

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 :

> Pal,
> On Tue, 16 Oct 2018 at 01:36, Pål Grønås Drange 
> 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=
> 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
> ___
> Python-ideas mailing list
> Python-ideas@python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>



-- 

--
*Nicolas Rolin* | Data Scientist
+ 33 631992617 - nicolas.ro...@tiime.fr 


*15 rue Auber, **75009 Paris*
*www.tiime.fr *
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Powerset

[Hasan Diwan]

Pal,
On Tue, 16 Oct 2018 at 01:36, Pål Grønås Drange  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=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
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Powerset

[Pål Grønås Drange]

> [...] 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
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Powerset

[Hasan Diwan]

On Mon, 15 Oct 2018 at 23:25, Pål Grønås Drange  wrote:
> 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.

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=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
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Powerset

[Pål Grønås Drange]

> 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?

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
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Powerset

[Greg Ewing]

Wes Turner wrote:
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 ).


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
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Powerset

[Wes Turner]

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  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?
>
> Yes pretty much.
> >
> > 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.
>
> 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=
> 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
> ___
> Python-ideas mailing list
> Python-ideas@python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Powerset

[Hasan Diwan]

> 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?

Yes pretty much.
>
> 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.

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=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
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Powerset

[Steven D'Aprano]

Hi Hasan, and welcome,


On Mon, Oct 15, 2018 at 11:15:47AM -0700, Hasan Diwan wrote:
> [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. 

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
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Powerset

[Sebastian Kreft]

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  wrote:

> [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=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
> ___
> Python-ideas mailing list
> Python-ideas@python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>


-- 
Sebastian Kreft
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/