Skip to content

Commit 5ae299a

Browse files
serhiy-storchakaserhiy-storchaka
authored
bpo-37128: Add math.perm(). (GH-13731)
1 parent d71f317 commit 5ae299a

File tree

5 files changed

+244
-3
lines changed

5 files changed

+244
-3
lines changed

‎Doc/library/math.rst‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -207,6 +207,19 @@ Number-theoretic and representation functions
207207
of *x* and are floats.
208208

209209

210+
.. function:: perm(n, k)
211+
212+
Return the number of ways to choose *k* items from *n* items
213+
without repetition and with order.
214+
215+
It is mathematically equal to the expression ``n! / (n - k)!``.
216+
217+
Raises :exc:`TypeError` if the arguments not integers.
218+
Raises :exc:`ValueError` if the arguments are negative or if *k* > *n*.
219+
220+
.. versionadded:: 3.8
221+
222+
210223
.. function:: prod(iterable, *, start=1)
211224

212225
Calculate the product of all the elements in the input *iterable*.

‎Lib/test/test_math.py‎

Lines changed: 65 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -240,6 +240,9 @@ def result_check(expected, got, ulp_tol=5, abs_tol=0.0):
240240
else:
241241
return None
242242

243+
class IntSubclass(int):
244+
pass
245+
243246
# Class providing an __index__ method.
244247
class MyIndexable(object):
245248
def __init__(self, value):
@@ -1862,6 +1865,64 @@ def test_fractions(self):
18621865
self.assertAllClose(fraction_examples, rel_tol=1e-8)
18631866
self.assertAllNotClose(fraction_examples, rel_tol=1e-9)
18641867

1868+
def testPerm(self):
1869+
perm = math.perm
1870+
factorial = math.factorial
1871+
# Test if factorial defintion is satisfied
1872+
for n in range(100):
1873+
for k in range(n + 1):
1874+
self.assertEqual(perm(n, k),
1875+
factorial(n) // factorial(n - k))
1876+
1877+
# Test for Pascal's identity
1878+
for n in range(1, 100):
1879+
for k in range(1, n):
1880+
self.assertEqual(perm(n, k), perm(n - 1, k - 1) * k + perm(n - 1, k))
1881+
1882+
# Test corner cases
1883+
for n in range(1, 100):
1884+
self.assertEqual(perm(n, 0), 1)
1885+
self.assertEqual(perm(n, 1), n)
1886+
self.assertEqual(perm(n, n), factorial(n))
1887+
1888+
# Raises TypeError if any argument is non-integer or argument count is
1889+
# not 2
1890+
self.assertRaises(TypeError, perm, 10, 1.0)
1891+
self.assertRaises(TypeError, perm, 10, decimal.Decimal(1.0))
1892+
self.assertRaises(TypeError, perm, 10, "1")
1893+
self.assertRaises(TypeError, perm, 10.0, 1)
1894+
self.assertRaises(TypeError, perm, decimal.Decimal(10.0), 1)
1895+
self.assertRaises(TypeError, perm, "10", 1)
1896+
1897+
self.assertRaises(TypeError, perm, 10)
1898+
self.assertRaises(TypeError, perm, 10, 1, 3)
1899+
self.assertRaises(TypeError, perm)
1900+
1901+
# Raises Value error if not k or n are negative numbers
1902+
self.assertRaises(ValueError, perm, -1, 1)
1903+
self.assertRaises(ValueError, perm, -2**1000, 1)
1904+
self.assertRaises(ValueError, perm, 1, -1)
1905+
self.assertRaises(ValueError, perm, 1, -2**1000)
1906+
1907+
# Raises value error if k is greater than n
1908+
self.assertRaises(ValueError, perm, 1, 2)
1909+
self.assertRaises(ValueError, perm, 1, 2**1000)
1910+
1911+
n = 2**1000
1912+
self.assertEqual(perm(n, 0), 1)
1913+
self.assertEqual(perm(n, 1), n)
1914+
self.assertEqual(perm(n, 2), n * (n-1))
1915+
self.assertRaises((OverflowError, MemoryError), perm, n, n)
1916+
1917+
for n, k in (True, True), (True, False), (False, False):
1918+
self.assertEqual(perm(n, k), 1)
1919+
self.assertIs(type(perm(n, k)), int)
1920+
self.assertEqual(perm(IntSubclass(5), IntSubclass(2)), 20)
1921+
self.assertEqual(perm(MyIndexable(5), MyIndexable(2)), 20)
1922+
for k in range(3):
1923+
self.assertIs(type(perm(IntSubclass(5), IntSubclass(k))), int)
1924+
self.assertIs(type(perm(MyIndexable(5), MyIndexable(k))), int)
1925+
18651926
def testComb(self):
18661927
comb = math.comb
18671928
factorial = math.factorial
@@ -1925,8 +1986,11 @@ def testComb(self):
19251986
for n, k in (True, True), (True, False), (False, False):
19261987
self.assertEqual(comb(n, k), 1)
19271988
self.assertIs(type(comb(n, k)), int)
1989+
self.assertEqual(comb(IntSubclass(5), IntSubclass(2)), 10)
19281990
self.assertEqual(comb(MyIndexable(5), MyIndexable(2)), 10)
1929-
self.assertIs(type(comb(MyIndexable(5), MyIndexable(2))), int)
1991+
for k in range(3):
1992+
self.assertIs(type(comb(IntSubclass(5), IntSubclass(k))), int)
1993+
self.assertIs(type(comb(MyIndexable(5), MyIndexable(k))), int)
19301994

19311995

19321996
def test_main():

‎Misc/NEWS.d/next/Library/2019-06-01-22-54-03.bpo-37128.oGXBWN.rst‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
Added :func:`math.perm`.

‎Modules/clinic/mathmodule.c.h‎

Lines changed: 36 additions & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎Modules/mathmodule.c‎

Lines changed: 129 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2998,6 +2998,120 @@ math_prod_impl(PyObject *module, PyObject *iterable, PyObject *start)
29982998
}
29992999

30003000

3001+
/*[clinic input]
3002+
math.perm
3003+
3004+
n: object
3005+
k: object
3006+
/
3007+
3008+
Number of ways to choose k items from n items without repetition and with order.
3009+
3010+
It is mathematically equal to the expression n! / (n - k)!.
3011+
3012+
Raises TypeError if the arguments are not integers.
3013+
Raises ValueError if the arguments are negative or if k > n.
3014+
[clinic start generated code]*/
3015+
3016+
static PyObject *
3017+
math_perm_impl(PyObject *module, PyObject *n, PyObject *k)
3018+
/*[clinic end generated code: output=e021a25469653e23 input=f71ee4f6ff26be24]*/
3019+
{
3020+
PyObject *result = NULL, *factor = NULL;
3021+
int overflow, cmp;
3022+
long long i, factors;
3023+
3024+
n = PyNumber_Index(n);
3025+
if (n == NULL) {
3026+
return NULL;
3027+
}
3028+
if (!PyLong_CheckExact(n)) {
3029+
Py_SETREF(n, _PyLong_Copy((PyLongObject *)n));
3030+
if (n == NULL) {
3031+
return NULL;
3032+
}
3033+
}
3034+
k = PyNumber_Index(k);
3035+
if (k == NULL) {
3036+
Py_DECREF(n);
3037+
return NULL;
3038+
}
3039+
if (!PyLong_CheckExact(k)) {
3040+
Py_SETREF(k, _PyLong_Copy((PyLongObject *)k));
3041+
if (k == NULL) {
3042+
Py_DECREF(n);
3043+
return NULL;
3044+
}
3045+
}
3046+
3047+
if (Py_SIZE(n) < 0) {
3048+
PyErr_SetString(PyExc_ValueError,
3049+
"n must be a non-negative integer");
3050+
goto error;
3051+
}
3052+
cmp = PyObject_RichCompareBool(n, k, Py_LT);
3053+
if (cmp != 0) {
3054+
if (cmp > 0) {
3055+
PyErr_SetString(PyExc_ValueError,
3056+
"k must be an integer less than or equal to n");
3057+
}
3058+
goto error;
3059+
}
3060+
3061+
factors = PyLong_AsLongLongAndOverflow(k, &overflow);
3062+
if (overflow > 0) {
3063+
PyErr_Format(PyExc_OverflowError,
3064+
"k must not exceed %lld",
3065+
LLONG_MAX);
3066+
goto error;
3067+
}
3068+
else if (overflow < 0 || factors < 0) {
3069+
if (!PyErr_Occurred()) {
3070+
PyErr_SetString(PyExc_ValueError,
3071+
"k must be a non-negative integer");
3072+
}
3073+
goto error;
3074+
}
3075+
3076+
if (factors == 0) {
3077+
result = PyLong_FromLong(1);
3078+
goto done;
3079+
}
3080+
3081+
result = n;
3082+
Py_INCREF(result);
3083+
if (factors == 1) {
3084+
goto done;
3085+
}
3086+
3087+
factor = n;
3088+
Py_INCREF(factor);
3089+
for (i = 1; i < factors; ++i) {
3090+
Py_SETREF(factor, PyNumber_Subtract(factor, _PyLong_One));
3091+
if (factor == NULL) {
3092+
goto error;
3093+
}
3094+
Py_SETREF(result, PyNumber_Multiply(result, factor));
3095+
if (result == NULL) {
3096+
goto error;
3097+
}
3098+
}
3099+
Py_DECREF(factor);
3100+
3101+
done:
3102+
Py_DECREF(n);
3103+
Py_DECREF(k);
3104+
return result;
3105+
3106+
error:
3107+
Py_XDECREF(factor);
3108+
Py_XDECREF(result);
3109+
Py_DECREF(n);
3110+
Py_DECREF(k);
3111+
return NULL;
3112+
}
3113+
3114+
30013115
/*[clinic input]
30023116
math.comb
30033117
@@ -3028,11 +3142,24 @@ math_comb_impl(PyObject *module, PyObject *n, PyObject *k)
30283142
if (n == NULL) {
30293143
return NULL;
30303144
}
3145+
if (!PyLong_CheckExact(n)) {
3146+
Py_SETREF(n, _PyLong_Copy((PyLongObject *)n));
3147+
if (n == NULL) {
3148+
return NULL;
3149+
}
3150+
}
30313151
k = PyNumber_Index(k);
30323152
if (k == NULL) {
30333153
Py_DECREF(n);
30343154
return NULL;
30353155
}
3156+
if (!PyLong_CheckExact(k)) {
3157+
Py_SETREF(k, _PyLong_Copy((PyLongObject *)k));
3158+
if (k == NULL) {
3159+
Py_DECREF(n);
3160+
return NULL;
3161+
}
3162+
}
30363163

30373164
if (Py_SIZE(n) < 0) {
30383165
PyErr_SetString(PyExc_ValueError,
@@ -3050,7 +3177,7 @@ math_comb_impl(PyObject *module, PyObject *n, PyObject *k)
30503177
"k must be an integer less than or equal to n");
30513178
goto error;
30523179
}
3053-
cmp = PyObject_RichCompareBool(k, temp, Py_GT);
3180+
cmp = PyObject_RichCompareBool(temp, k, Py_LT);
30543181
if (cmp > 0) {
30553182
Py_SETREF(k, temp);
30563183
}
@@ -3174,6 +3301,7 @@ static PyMethodDef math_methods[] = {
31743301
{"tanh", math_tanh, METH_O, math_tanh_doc},
31753302
MATH_TRUNC_METHODDEF
31763303
MATH_PROD_METHODDEF
3304+
MATH_PERM_METHODDEF
31773305
MATH_COMB_METHODDEF
31783306
{NULL, NULL} /* sentinel */
31793307
};

0 commit comments

Comments
 (0)