classification
Title: Extending itertools.combinations
Type: enhancement Stage:
Components: Extension Modules Versions: Python 3.1, Python 2.7
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: ezio.melotti, konryd, mark.dickinson, rhettinger
Priority: normal Keywords:

Created on 2009-01-25 02:05 by konryd, last changed 2009-01-27 18:08 by rhettinger. This issue is now closed.

Messages (15)
msg80492 - (view) Author: Konrad (konryd) Date: 2009-01-25 02:05
The function itertools.combinations might benefit from making
the 'r' (length of the combinations) argument optionally a sequence.

With that change one could call combinations(sequence, [2, 3]) in
order to get all combinations of length 2 and 3.
In particular, one could call combinations(sequence,
range(len(sequence)) in order to get *all* combinations of given
sequence.

The change would be backwards compatible as it would check for
sequential arguments.
msg80495 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-01-25 03:22
Do you have compelling use cases?

Is it worth what it takes to preserve the relation with permuations()
and product() and the lexicographic orderings?

Do we care the length of the output is no longer predictable by a simple
n! / r! / (n-r)!  ?

Do we care that the variable length output prevents uses in for-loops
with tuple unpacking:

   for a, b, c in combinations('ABCDEF', [2,3]):
        . . .
msg80498 - (view) Author: Ezio Melotti (ezio.melotti) * (Python committer) Date: 2009-01-25 07:10
It would also be nice to have a __len__ method on both permutations and
combinations.

len(permutations(sequence)) could return the number of permutations
using the formulas (e.g. n! for permutations) without generating all the
possible permutations (as opposed to something like
len(list(permutations(sequence)))).

Also, is there a way to calculate combinations with repetitions[1]?
Maybe we could add an optional argument repetitions=True/False.

[1]:
http://en.wikipedia.org/wiki/Combinations#Number_of_combinations_with_repetition
msg80499 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-01-25 07:30
Guido disallowed returning a len method on iterators.  He expected
bool(it) to be False.

The recipes section of the itertools docs has code for
combinations_with_replacement().  It was not included originally because
it was unclear whether there was actually a need to generate them. 
Possibly, people are mainly interested in knowing how many there are but
having no need to actually enumerate them.  That being said, if I get
more requests or if some real world use cases arise, I would be happy to
C the recipe and add it in Py2.7.
msg80500 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-01-25 09:43
I've seen requests for combinations with replacement come up on c.l.p. a 
few times in the past, though it's never been clear whether there was a 
real need or whether the interest was driven by homework or curiosity.

-1 for sequences in the second argument of combinations();  it doesn't 
feel like a useful enough generalization to be worth adding code for.
msg80501 - (view) Author: Konrad (konryd) Date: 2009-01-25 10:57
I'm afraid I don't have any real-world use cases. Originally, I assumed 
that dropping the length argument will make the function iterate over 
*all* combinations, which would enable me to write somehow twisted, one-
liner for _inefficiently_ solving knapsack problem.

max((comb for comb in all_combinations(zip(weights, values))
       if sum(map(itemgetter(0), comb)) < LIM), 
     key=lambda comb: sum(map(itemgetter(1), comb)))

But unfortunately, this is far from being 'compelling'.

Regarding other issues you raised: I think it would be pretty clear for 
the user, that the length of every combination might vary - that's what 
he asked for. And the length might be computed by summing the lengths 
counted using given formula, which is (for me at last) still explicit 
enough.
msg80506 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-01-25 13:08
> that dropping the length argument will make the function iterate over 
> *all* combinations,

Now *this* sounds more useful to me:  an itertool that generates *all* subsets of a list.  It's 
quite easy to do with existing itertools, though, either by looping over the second argument to 
combinations, or (for a different ordering) using product:

def subsets(iterable):
    l = list(iterable)
    for selector in itertools.product([False, True], repeat=len(l)):
        yield [element for indicator, element in zip(selector, l) if indicator]
msg80532 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-01-25 19:35
There is already a powerset() recipe in the docs.  It was contributed by
Eric Raymond.
msg80533 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-01-25 19:40
So there is.  Apologies---I'll try to read more carefully next time.
msg80536 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-01-25 19:47
Am rejecting the OP's request for the reasons cited.

Also rejecting the request for a __len__ method on permutations.

Ezio or Mark, please open another feature request for
combinations_with_replacement() and assign to me.  Will likely accept
this one and put it in when I get a chance.

Thank you to all the posters on this one.
msg80617 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-01-27 04:37
FWIW, I added combinations_with_replacement() in r69001 and r69004 .
msg80645 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-01-27 11:14
combinations_with_replacement addition looks good.  Thank you.

I wonder whether the second argument should be constrained to be an
integer? I find the following a little surprising:

>>> list(combinations_with_replacement(range(5), -0.3))
[()]

(same behaviour with combinations and permutations).  Should I open a
separate issue for this, or is it just not worth changing?
msg80646 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-01-27 11:19
Glad you like it.

Will meditate for a bit on the floating point input.  My first thought
is that it isn't worth going through the __index__ dance to preclude
inputs that look odd.
msg80648 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-01-27 11:31
I only just noticed the DeprecationWarning that's already happening for
float inputs in 2.7.  (And float inputs already raise TypeError in 3.1.)
So I agree that it's probably not worth it.
msg80664 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-01-27 18:08
Correction to earlier statement.  It should have read:

Guido disallowed returning a len method on iterators.  He expected
bool(it) to be always be True.
History
Date User Action Args
2009-01-27 18:08:14rhettingersetmessages: + msg80664
2009-01-27 11:31:44mark.dickinsonsetmessages: + msg80648
2009-01-27 11:19:28rhettingersetmessages: + msg80646
2009-01-27 11:14:15mark.dickinsonsetmessages: + msg80645
2009-01-27 04:37:30rhettingersetmessages: + msg80617
2009-01-25 19:47:54rhettingersetstatus: open -> closed
resolution: rejected
messages: + msg80536
2009-01-25 19:40:04mark.dickinsonsetmessages: + msg80533
2009-01-25 19:35:18rhettingersetmessages: + msg80532
2009-01-25 13:08:37mark.dickinsonsetmessages: + msg80506
2009-01-25 10:57:39konrydsetmessages: + msg80501
2009-01-25 09:43:11mark.dickinsonsetnosy: + mark.dickinson
messages: + msg80500
2009-01-25 07:30:56rhettingersetmessages: + msg80499
2009-01-25 07:10:20ezio.melottisetnosy: + ezio.melotti
messages: + msg80498
2009-01-25 03:22:55rhettingersetassignee: rhettinger
messages: + msg80495
components: + Extension Modules, - Library (Lib)
versions: + Python 3.1, Python 2.7
2009-01-25 02:05:03konrydcreate