[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Raymond Hettinger added the comment: Fixed in r68394 Will forward port in a day or two. -- resolution: accepted -> fixed status: open -> closed ___ Python tracker ___ __

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Changes by Raymond Hettinger : Removed file: http://bugs.python.org/file12644/combperm3.diff ___ Python tracker ___ ___ Python-bugs-list mailin

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Changes by Raymond Hettinger : Added file: http://bugs.python.org/file12647/combperm4.diff ___ Python tracker ___ ___ Python-bugs-list mailing

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Changes by Raymond Hettinger : Removed file: http://bugs.python.org/file12642/combperm2.diff ___ Python tracker ___ ___ Python-bugs-list mailin

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Changes by Raymond Hettinger : Added file: http://bugs.python.org/file12644/combperm3.diff ___ Python tracker ___ ___ Python-bugs-list mailing

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Raymond Hettinger added the comment: Thanks David. Looks like we're all in agreement. Turns out, I did a weeks worth of mulling today ;-) Accepting the proposal with the following rationale: 1. There exist some valid use cases where r>n. 2. Returning an empty list is the expected outcome with t

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

David W. Lambert added the comment: I had thought highly of the "mull it over for a week" plan. After a week we'd decide to follow Stephen Wolfram's lead, which seems to be the current patch. I haven't yet used the python permutations iterator, although I used to have a script that solved w

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Changes by Raymond Hettinger : Removed file: http://bugs.python.org/file12640/combperm.diff ___ Python tracker ___ ___ Python-bugs-list mailing

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Changes by Raymond Hettinger : Added file: http://bugs.python.org/file12642/combperm2.diff ___ Python tracker ___ ___ Python-bugs-list mailing

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Raymond Hettinger added the comment: Attached an updated patch which expands the tests and docs. Handles the r>n case with an empty result. Leaves the r<0 case as a ValueError. Am thinking that if we do this, it should be treated as a bug and posted to 2.6 and 3.0. Added file: http://bugs.pyth

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Raymond Hettinger added the comment: David, I know the OPs position and Mark's opinion. What is your recommendation for the r>n case and the r<0 case? ___ Python tracker ___

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Raymond Hettinger added the comment: Summary of functions/definitions expected to return a number: r>n r<0 Source - -- -- error error MS Excel PERMUT() and COMBIN() error error HP32SII nPr and nCr und

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Raymond Hettinger added the comment: Excel is returning the count, not the set itself. So, it could have chosen to return zero. The HP32SII also has nCr and nPr functions that return INVALID DATA for r>n or r<0. The Combinatorics section of CRC Standard Mathematical Formulae (30th edition) de

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

David W. Lambert added the comment: I try to "not know" excel. Does it have any other means to represent an empty set? ___ Python tracker ___ ___

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Raymond Hettinger added the comment: Data point: Microsoft Excel's PERMUT() and COMBIN() return #NUM! for r>n or r<0. ___ Python tracker ___ _

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Mark Dickinson added the comment: Got Sage working again. It also returns an empty list for r > n. For r negative, Combinations returns an empty list and Permutation gives an error. sage: Combinations(range(4), 6) Combinations of [0, 1, 2, 3] of length 6 sage: Combinations(range(4), 6).list

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Mark Dickinson added the comment: Results from Magma, Sage and Gap: Magma provides functions "Subsets(S, k)" and "Permutations(S, k)". From the documentation: Subsets(S, k) : The set of subsets of the set S of size k. If k is larger than the cardinality of S then the result will be empty.

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

David W. Lambert added the comment: Mathematica indicates for the user to define it later. An error. In[3]:= Permutations[{1,2},{-2}] Permutations::nninfseq: Position 2 of Permutations[{1, 2}, {-2}] must be All, Infinity, a non-negative integer, or a List whose first element (r

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Raymond Hettinger added the comment: David, thanks for the data point. What does it return for In[1]:= Permutations[{a, b, c}, {-1}] ___ Python tracker ___ ___

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

David W. Lambert added the comment: Mathematica returns an empty list. In[1]:= Permutations[{1,2},{1}] Out[1]= {{1}, {2}} In[2]:= Permutations[{1,2},{4}] Out[2]= {} In[3]:= -- nosy: +LambertDW ___ Python tracker

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Mark Dickinson added the comment: > 5. This one bugs me a bit. It is nice to have all the factorial > formulas just work and not have a piecewise definition. IIRC, in the 'Concrete Mathematics' book, Knuth and co use something like (n choose k) = (n-to-the-k-falling)/k! to get around this:

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Raymond Hettinger added the comment: Another thought before I forget: The piecewise definition of the choose function or for binomial coefficients suggests that supporting the r>n case should be accompanied by supporting the r<0 case. ___ Python tracker

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Raymond Hettinger added the comment: 1. This is the most important issue. Is the r>n case typically an error in the user's program or thought process. If so, then the utility of a ValueError can be weighed against the utility of other cases where you want combs/perms to automatically handle t

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Thomas Finley added the comment: Hi Raymond, thanks for your well reasoned and thorough reply. Just a couple small thoughts... I'll borrow your numbers if you don't mind. 1. I'd ask you to discount this argument. There are many situations in the Python library where empty results are possible

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Raymond Hettinger added the comment: Quick notes so I don't forget: The two main pure python equivalents in the docs would need to be updated with the new special cases (currently they raise IndexError for r>n). The other two pure python equivalents would automatically handle the proposed new

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Raymond Hettinger added the comment: Will spend a while mulling this over and taking it under advisement. Initially, I am disinclined for several reasons. 1. For many use cases, r>n is an error condition that should not pass silently. 2. While it's possible to make definitions of comb/perm

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

Mark Dickinson added the comment: I agree that the proposed behaviour seems more correct: the collection of all subsets of size 4 of range(3) is perfectly valid and well-defined; it just happens to be empty. I've also encountered this in practice (in code that was enumerating partitions of

[issue4816] Patch of itertools.{combinations, permutations} for empty combinations

New submission from Thomas Finley : This is a patch for the Python 3.1 build checked out from http://svn.python.org/projects/python/branches/py3k The current behavior of itertools.combinations(iterable,r) and itertools.permutations(iterable,r) is to throw a ValueError if iterable yields fewer th