Author TFinley
Recipients TFinley
Date 2009-01-03.10:51:11
SpamBayes Score 2.81156e-11
Marked as misclassified No
Message-id <1230979875.82.0.811611724155.issue4816@psf.upfronthosting.co.za>
In-reply-to
Content
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.
History
Date User Action Args
2009-01-03 10:51:15TFinleysetrecipients: + TFinley
2009-01-03 10:51:15TFinleysetmessageid: <1230979875.82.0.811611724155.issue4816@psf.upfronthosting.co.za>
2009-01-03 10:51:14TFinleylinkissue4816 messages
2009-01-03 10:51:12TFinleycreate