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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
Date: 2009-01-27 04:37 |
FWIW, I added combinations_with_replacement() in r69001 and r69004 .
|
msg80645 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
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) * |
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) * |
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) * |
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.
|
|
Date |
User |
Action |
Args |
2022-04-11 14:56:44 | admin | set | github: 49298 |
2009-01-27 18:08:14 | rhettinger | set | messages:
+ msg80664 |
2009-01-27 11:31:44 | mark.dickinson | set | messages:
+ msg80648 |
2009-01-27 11:19:28 | rhettinger | set | messages:
+ msg80646 |
2009-01-27 11:14:15 | mark.dickinson | set | messages:
+ msg80645 |
2009-01-27 04:37:30 | rhettinger | set | messages:
+ msg80617 |
2009-01-25 19:47:54 | rhettinger | set | status: open -> closed resolution: rejected messages:
+ msg80536 |
2009-01-25 19:40:04 | mark.dickinson | set | messages:
+ msg80533 |
2009-01-25 19:35:18 | rhettinger | set | messages:
+ msg80532 |
2009-01-25 13:08:37 | mark.dickinson | set | messages:
+ msg80506 |
2009-01-25 10:57:39 | konryd | set | messages:
+ msg80501 |
2009-01-25 09:43:11 | mark.dickinson | set | nosy:
+ mark.dickinson messages:
+ msg80500 |
2009-01-25 07:30:56 | rhettinger | set | messages:
+ msg80499 |
2009-01-25 07:10:20 | ezio.melotti | set | nosy:
+ ezio.melotti messages:
+ msg80498 |
2009-01-25 03:22:55 | rhettinger | set | assignee: rhettinger messages:
+ msg80495 components:
+ Extension Modules, - Library (Lib) versions:
+ Python 3.1, Python 2.7 |
2009-01-25 02:05:03 | konryd | create | |