[New-bugs-announce] [issue4816] Patch of itertools.{combinations, permutations} for empty combinations

[Thomas Finley]

New submission from Thomas Finley <tfinley at gmail.com>:

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 than r items.  This changes these functions so the
generator instead yields 0 items.

As for my argument for acceptance, while the original behavior is not a
bug insofar as its implementation was deliberate, I'd argue this is
undesirable on grounds of mathematical consistency and functionality.

In mathematics the "choose" function is defined as "(n choose r)=0" for
r>n, so itertools.combinations' behavior is inconsistent with its
obvious combinatorial analogy.  (Similar for permutations and the
combinatorial "P" function.)

For functionality I'll cite my own case as anecdote.  In writing
regression tests I wanted to ensure that a group of items obeyed a
certain "mutually consistent" property between all triples.  (Something
akin to the triangle inequality.)  So:

all(triangle_respected(*triple) for triple in
itertools.combinations(group, 3))

If len(group)<=2, that's fine, since with no triangles there is no
inconsistency, and all(())==True.  However, the code failed with a
ValueError when groups were that small.  Working around this was fairly
awkward, since I wanted to continue to fail noisily if my
triangle_respected function threw a ValueError, and I wasn't sure at all
that it wouldn't if my items were 

The patch modifies Modules/itertoolsmodule.c slightly, changing
combinationsobject_new and permutationsobject_new.  (Deleting the error
throwing code, and have one line changes in both structures to handle
the n>r case.  One could handle this special case more efficiently than
I do by not bothering to allocate certain structures in this case, but I
didn't want to tempt fate.)  The patch also changes the appropriate
tests in Lib/test/test_itertools.py .

Obviously, this would break code that depends upon Python throwing
ValueError in the event of the combination or permutation sequence being
empty.  However, I hope given that combinations and permutations are a
relative novelty that their behavior in this corner case is not yet
etched in stone.

Sorry if this belongs in a PEP -- it seems quite minor, but I don't
quite have a feel what the threshold is.

----------
components: Library (Lib), Tests
files: itertools-empty-combinations.diff
keywords: patch
messages: 78943
nosy: TFinley
severity: normal
status: open
title: Patch of itertools.{combinations,permutations} for empty combinations
type: behavior
versions: Python 3.1
Added file: http://bugs.python.org/file12563/itertools-empty-combinations.diff

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue4816>
_______________________________________