[issue5139] Add combinatoric counting functions to the math module.
Changes by Raymond Hettinger rhettin...@users.sourceforge.net: Added file: http://bugs.python.org/file13559/math_combinatorics.c ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue5139] Add combinatoric counting functions to the math module.
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: Probably, these should be saved for an integer functions module. In the meantime, leaving this open with low priority. There's not much of a current need since the functions are so simple to write in pure python. The itertools docs provide the formulas for people who have forgotten them. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue5139] Add combinatoric counting functions to the math module.
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: Upon further thought, I'm going to withdraw this feature request. If an integer functions module surfaces at some point, it will be an obvious addition. -- resolution: - rejected status: open - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue5139] Add combinatoric counting functions to the math module.
Changes by Raymond Hettinger rhettin...@users.sourceforge.net: -- priority: normal - low ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue5139] Add combinatoric counting functions to the math module.
Terry J. Reedy tjre...@udel.edu added the comment: If you semi-optimize the implementation by pre-cancelling out the larger of the denominators, then these functions would be justified as more efficient than the naive use of the factorial function indicated by the formulas. Possible shorter names: ncombos nperms ncombos_with_reps I would prefer that these and other integer-only functions be in a separate imath module. I have the impression that this was not done with the first because we can't have a module with just one function, but these would make at least 4 or 5, which is enough for a module. -- nosy: +tjreedy ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue5139] Add combinatoric counting functions to the math module.
Ezio Melotti ezio.melo...@gmail.com added the comment: Ezio, itertools currently has combinations with and without *replacement*, not repetition. I think you're talking about something slightly different (repetitions in the *iterable*, rather than allowing repeated *drawings* of the same element). The two terms should be interchangeable (I just used repetitions because is the one I learnt at school). itertools already has 'permutations_with_replacement': it's called 'product'. combinations(it, r): select r elements from it, no replacement, no order permutations(it, r): select r elements, no replacement, order is relevant combinations_with_replacement(it, r): replacement, no order product(it, repeat=r): replacement, order Isn't this name (product) not coherent with the others? Also is not immediately clear to me what a function named 'product' is supposed to do (but probably it is too late to change it now). ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue5139] Add combinatoric counting functions to the math module.
Mark Dickinson dicki...@gmail.com added the comment: I suggested to include math.npermutations_with_repetitions for completeness, Ezio, itertools currently has combinations with and without *replacement*, not repetition. I think you're talking about something slightly different (repetitions in the *iterable*, rather than allowing repeated *drawings* of the same element). itertools already has 'permutations_with_replacement': it's called 'product'. combinations(it, r): select r elements from it, no replacement, no order permutations(it, r): select r elements, no replacement, order is relevant combinations_with_replacement(it, r): replacement, no order product(it, repeat=r): replacement, order ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue5139] Add combinatoric counting functions to the math module.
Mark Dickinson dicki...@gmail.com added the comment: This all sounds good to me. -- nosy: +marketdickinson ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue5139] Add combinatoric counting functions to the math module.
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: I had a thought to name them perms(n,r), combs(n,r) and combs_with_replacement(n,r). The abbreviated names read nicely and avoid a namespace collision with the itertools module (making the world safe for from math import *). ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue5139] Add combinatoric counting functions to the math module.
Mark Dickinson dicki...@gmail.com added the comment: I agree that the names shouldn't clash with those in math, especially since it seems quite plausible that a user might want to use both itertools.combinations and math.combs (for example) in the same script. No strong feelings about the actual names, but it would be nice if they somehow conveyed the idea of counting rather than enumerating. That is, if it weren't for the clearly ridiculous length, it would be nice to have: itertools.combinations itertools.permutations and math.number_of_combinations math.number_of_permutations etc. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue5139] Add combinatoric counting functions to the math module.
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: Will put together a patch. -- assignee: - rhettinger ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue5139] Add combinatoric counting functions to the math module.
Ezio Melotti ezio.melo...@gmail.com added the comment: Should we add permutations with repetitions? Example (from Schaum's outline of theory and problems of probability and statistics): The number of different permutations of the 11 letters of the word MISSISSIPPI, which consists of 1 M, 4 I's, 4 S's and 2 P's, is 11! / (1!*4!*4!*2!) = 34650 math.perms_with_repetitions(11, [1,4,4,2]) and maybe parallel function in itertools: itertools.permutations_with_repetitions(iterable[, r]) This should be equal to itertools.permutations(set(iterable)[, r]). ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue5139] Add combinatoric counting functions to the math module.
Changes by Ezio Melotti ezio.melo...@gmail.com: -- nosy: +ezio.melotti ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue5139] Add combinatoric counting functions to the math module.
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: -1 on perms_with_repetitions. That's headed in the direction of bloat -- taking every formula in a textbook and putting it in the module. Also, it is somewhat use case challenged. I've *never* needed this in my 30 years of programming. I like Mark's idea for names that indicate that they return a number or count instead an iterator. Perhaps something like: ncombinations() npermutations() ncombinations_with_replacement() ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue5139] Add combinatoric counting functions to the math module.
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: Besides paralleling itertools names, the names should also parallel each other -- when I find permutations, I also expect to find combinations. No matter what names are selected, we'll include alternate index targets for the various names binonimial coefficient, choose function, multichoose, combinations with repetition. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue5139] Add combinatoric counting functions to the math module.
Fredrik Johansson fredrik.johans...@gmail.com added the comment: I understand the connection with itertools, but why not just call a binomial coefficient a binomial coefficient? Probably 90% of all math libraries call this function 'binomial' or 'bincoef' and I suspect that's the name most people would search for. -- nosy: +fredrikj ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue5139] Add combinatoric counting functions to the math module.
Ezio Melotti ezio.melo...@gmail.com added the comment: itertools.permutations_with_repetitions(iterable[, r]) is not necessary, writing in the doc that set(itertools.permutations(iterable[, r])) has the same result is probably enough (I put the set() in the wrong place in the previous message - this version is also less efficient because it has to generate duplicate elements that will be removed by set()). I suggested to include math.npermutations_with_repetitions for completeness, even if it's not widely used IMHO is not coherent to have formulas to calculate combinations with and without repetitions and a just a formula for permutations without repetitions. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue5139] Add combinatoric counting functions to the math module.
New submission from Raymond Hettinger rhettin...@users.sourceforge.net: To parallel the functions in itertools, add: math.combinations(n,r) -- n! / r! / (n-r)! when 0 = r = n or zero when r n. math.permutations(n,r) -- n! / (n-r)! when 0 = r = n or zero when r n. math.combinations_with_replacement(n,r) -- (n+r-1)! / r! / (n-1)! when n 0. And when n==0, return 0 if r0 else 1. These will enable an itertools user to compute the length of those iterators. It will also serve for general probability computations. Likewise, it produce binomial coefficients and multiset partitions. Since, the math module is where we put the factorial() function, it is the logical place for the combinatoric counting functions. -- components: Extension Modules messages: 81026 nosy: rhettinger priority: normal severity: normal status: open title: Add combinatoric counting functions to the math module. type: feature request versions: Python 2.7, Python 3.1 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue5139 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com