| msg81026 - (view) |
Author: Raymond Hettinger (rhettinger) *  |
Date: 2009-02-03 04:57 |
| 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 r>0 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. |
|
|
| msg81030 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
Date: 2009-02-03 08:22 |
| This all sounds good to me. |
|
|
| msg81038 - (view) |
Author: Raymond Hettinger (rhettinger) * |
Date: 2009-02-03 09:49 |
| 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 *"). |
|
|
| msg81042 - (view) |
Author: Raymond Hettinger (rhettinger) * |
Date: 2009-02-03 10:56 |
| Will put together a patch. |
|
|
| msg81046 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
Date: 2009-02-03 11:50 |
| 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. |
|
|
| msg81062 - (view) |
Author: Ezio Melotti (ezio.melotti) * |
Date: 2009-02-03 14:49 |
| 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]). |
|
|
| msg81097 - (view) |
Author: Raymond Hettinger (rhettinger) * |
Date: 2009-02-03 20:42 |
| -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() |
|
|
| msg81101 - (view) |
Author: Fredrik Johansson (fredrikj) |
Date: 2009-02-03 21:28 |
| 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. |
|
|
| msg81107 - (view) |
Author: Raymond Hettinger (rhettinger) * |
Date: 2009-02-03 22:16 |
| 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". |
|
|
| msg81128 - (view) |
Author: Ezio Melotti (ezio.melotti) * |
Date: 2009-02-04 05:32 |
| 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. |
|
|
| msg81134 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
Date: 2009-02-04 09:36 |
| > 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 |
|
|
| msg81294 - (view) |
Author: Terry J. Reedy (terry.reedy) * |
Date: 2009-02-06 19:39 |
| 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. |
|
|
| msg81313 - (view) |
Author: Ezio Melotti (ezio.melotti) * |
Date: 2009-02-06 22:44 |
| > 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). |
|
|
| msg85095 - (view) |
Author: Raymond Hettinger (rhettinger) * |
Date: 2009-04-01 21:10 |
| 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. |
|
|
| msg85100 - (view) |
Author: Raymond Hettinger (rhettinger) * |
Date: 2009-04-01 21:38 |
| 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. |
|
|