summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Doc/library/math.rst13
-rw-r--r--Lib/test/test_math.py66
-rw-r--r--Misc/NEWS.d/next/Library/2019-06-01-22-54-03.bpo-37128.oGXBWN.rst1
-rw-r--r--Modules/clinic/mathmodule.c.h37
-rw-r--r--Modules/mathmodule.c130
5 files changed, 244 insertions, 3 deletions
diff --git a/Doc/library/math.rst b/Doc/library/math.rst
index 8c68370503..c5a77f1fab 100644
--- a/Doc/library/math.rst
+++ b/Doc/library/math.rst
@@ -207,6 +207,19 @@ Number-theoretic and representation functions
of *x* and are floats.
+.. function:: perm(n, k)
+
+ Return the number of ways to choose *k* items from *n* items
+ without repetition and with order.
+
+ It is mathematically equal to the expression ``n! / (n - k)!``.
+
+ Raises :exc:`TypeError` if the arguments not integers.
+ Raises :exc:`ValueError` if the arguments are negative or if *k* > *n*.
+
+ .. versionadded:: 3.8
+
+
.. function:: prod(iterable, *, start=1)
Calculate the product of all the elements in the input *iterable*.
diff --git a/Lib/test/test_math.py b/Lib/test/test_math.py
index e27092eefd..96e0cf2fe6 100644
--- a/Lib/test/test_math.py
+++ b/Lib/test/test_math.py
@@ -240,6 +240,9 @@ def result_check(expected, got, ulp_tol=5, abs_tol=0.0):
else:
return None
+class IntSubclass(int):
+ pass
+
# Class providing an __index__ method.
class MyIndexable(object):
def __init__(self, value):
@@ -1862,6 +1865,64 @@ class IsCloseTests(unittest.TestCase):
self.assertAllClose(fraction_examples, rel_tol=1e-8)
self.assertAllNotClose(fraction_examples, rel_tol=1e-9)
+ def testPerm(self):
+ perm = math.perm
+ factorial = math.factorial
+ # Test if factorial defintion is satisfied
+ for n in range(100):
+ for k in range(n + 1):
+ self.assertEqual(perm(n, k),
+ factorial(n) // factorial(n - k))
+
+ # Test for Pascal's identity
+ for n in range(1, 100):
+ for k in range(1, n):
+ self.assertEqual(perm(n, k), perm(n - 1, k - 1) * k + perm(n - 1, k))
+
+ # Test corner cases
+ for n in range(1, 100):
+ self.assertEqual(perm(n, 0), 1)
+ self.assertEqual(perm(n, 1), n)
+ self.assertEqual(perm(n, n), factorial(n))
+
+ # Raises TypeError if any argument is non-integer or argument count is
+ # not 2
+ self.assertRaises(TypeError, perm, 10, 1.0)
+ self.assertRaises(TypeError, perm, 10, decimal.Decimal(1.0))
+ self.assertRaises(TypeError, perm, 10, "1")
+ self.assertRaises(TypeError, perm, 10.0, 1)
+ self.assertRaises(TypeError, perm, decimal.Decimal(10.0), 1)
+ self.assertRaises(TypeError, perm, "10", 1)
+
+ self.assertRaises(TypeError, perm, 10)
+ self.assertRaises(TypeError, perm, 10, 1, 3)
+ self.assertRaises(TypeError, perm)
+
+ # Raises Value error if not k or n are negative numbers
+ self.assertRaises(ValueError, perm, -1, 1)
+ self.assertRaises(ValueError, perm, -2**1000, 1)
+ self.assertRaises(ValueError, perm, 1, -1)
+ self.assertRaises(ValueError, perm, 1, -2**1000)
+
+ # Raises value error if k is greater than n
+ self.assertRaises(ValueError, perm, 1, 2)
+ self.assertRaises(ValueError, perm, 1, 2**1000)
+
+ n = 2**1000
+ self.assertEqual(perm(n, 0), 1)
+ self.assertEqual(perm(n, 1), n)
+ self.assertEqual(perm(n, 2), n * (n-1))
+ self.assertRaises((OverflowError, MemoryError), perm, n, n)
+
+ for n, k in (True, True), (True, False), (False, False):
+ self.assertEqual(perm(n, k), 1)
+ self.assertIs(type(perm(n, k)), int)
+ self.assertEqual(perm(IntSubclass(5), IntSubclass(2)), 20)
+ self.assertEqual(perm(MyIndexable(5), MyIndexable(2)), 20)
+ for k in range(3):
+ self.assertIs(type(perm(IntSubclass(5), IntSubclass(k))), int)
+ self.assertIs(type(perm(MyIndexable(5), MyIndexable(k))), int)
+
def testComb(self):
comb = math.comb
factorial = math.factorial
@@ -1925,8 +1986,11 @@ class IsCloseTests(unittest.TestCase):
for n, k in (True, True), (True, False), (False, False):
self.assertEqual(comb(n, k), 1)
self.assertIs(type(comb(n, k)), int)
+ self.assertEqual(comb(IntSubclass(5), IntSubclass(2)), 10)
self.assertEqual(comb(MyIndexable(5), MyIndexable(2)), 10)
- self.assertIs(type(comb(MyIndexable(5), MyIndexable(2))), int)
+ for k in range(3):
+ self.assertIs(type(comb(IntSubclass(5), IntSubclass(k))), int)
+ self.assertIs(type(comb(MyIndexable(5), MyIndexable(k))), int)
def test_main():
diff --git a/Misc/NEWS.d/next/Library/2019-06-01-22-54-03.bpo-37128.oGXBWN.rst b/Misc/NEWS.d/next/Library/2019-06-01-22-54-03.bpo-37128.oGXBWN.rst
new file mode 100644
index 0000000000..f1b8258902
--- /dev/null
+++ b/Misc/NEWS.d/next/Library/2019-06-01-22-54-03.bpo-37128.oGXBWN.rst
@@ -0,0 +1 @@
+Added :func:`math.perm`.
diff --git a/Modules/clinic/mathmodule.c.h b/Modules/clinic/mathmodule.c.h
index 92ec4bec9b..0efe5cc409 100644
--- a/Modules/clinic/mathmodule.c.h
+++ b/Modules/clinic/mathmodule.c.h
@@ -638,6 +638,41 @@ exit:
return return_value;
}
+PyDoc_STRVAR(math_perm__doc__,
+"perm($module, n, k, /)\n"
+"--\n"
+"\n"
+"Number of ways to choose k items from n items without repetition and with order.\n"
+"\n"
+"It is mathematically equal to the expression n! / (n - k)!.\n"
+"\n"
+"Raises TypeError if the arguments are not integers.\n"
+"Raises ValueError if the arguments are negative or if k > n.");
+
+#define MATH_PERM_METHODDEF \
+ {"perm", (PyCFunction)(void(*)(void))math_perm, METH_FASTCALL, math_perm__doc__},
+
+static PyObject *
+math_perm_impl(PyObject *module, PyObject *n, PyObject *k);
+
+static PyObject *
+math_perm(PyObject *module, PyObject *const *args, Py_ssize_t nargs)
+{
+ PyObject *return_value = NULL;
+ PyObject *n;
+ PyObject *k;
+
+ if (!_PyArg_CheckPositional("perm", nargs, 2, 2)) {
+ goto exit;
+ }
+ n = args[0];
+ k = args[1];
+ return_value = math_perm_impl(module, n, k);
+
+exit:
+ return return_value;
+}
+
PyDoc_STRVAR(math_comb__doc__,
"comb($module, n, k, /)\n"
"--\n"
@@ -674,4 +709,4 @@ math_comb(PyObject *module, PyObject *const *args, Py_ssize_t nargs)
exit:
return return_value;
}
-/*[clinic end generated code: output=6709521e5e1d90ec input=a9049054013a1b77]*/
+/*[clinic end generated code: output=a82b0e705b6d0ec0 input=a9049054013a1b77]*/
diff --git a/Modules/mathmodule.c b/Modules/mathmodule.c
index bea4607b9b..6e1099321c 100644
--- a/Modules/mathmodule.c
+++ b/Modules/mathmodule.c
@@ -2999,6 +2999,120 @@ math_prod_impl(PyObject *module, PyObject *iterable, PyObject *start)
/*[clinic input]
+math.perm
+
+ n: object
+ k: object
+ /
+
+Number of ways to choose k items from n items without repetition and with order.
+
+It is mathematically equal to the expression n! / (n - k)!.
+
+Raises TypeError if the arguments are not integers.
+Raises ValueError if the arguments are negative or if k > n.
+[clinic start generated code]*/
+
+static PyObject *
+math_perm_impl(PyObject *module, PyObject *n, PyObject *k)
+/*[clinic end generated code: output=e021a25469653e23 input=f71ee4f6ff26be24]*/
+{
+ PyObject *result = NULL, *factor = NULL;
+ int overflow, cmp;
+ long long i, factors;
+
+ n = PyNumber_Index(n);
+ if (n == NULL) {
+ return NULL;
+ }
+ if (!PyLong_CheckExact(n)) {
+ Py_SETREF(n, _PyLong_Copy((PyLongObject *)n));
+ if (n == NULL) {
+ return NULL;
+ }
+ }
+ k = PyNumber_Index(k);
+ if (k == NULL) {
+ Py_DECREF(n);
+ return NULL;
+ }
+ if (!PyLong_CheckExact(k)) {
+ Py_SETREF(k, _PyLong_Copy((PyLongObject *)k));
+ if (k == NULL) {
+ Py_DECREF(n);
+ return NULL;
+ }
+ }
+
+ if (Py_SIZE(n) < 0) {
+ PyErr_SetString(PyExc_ValueError,
+ "n must be a non-negative integer");
+ goto error;
+ }
+ cmp = PyObject_RichCompareBool(n, k, Py_LT);
+ if (cmp != 0) {
+ if (cmp > 0) {
+ PyErr_SetString(PyExc_ValueError,
+ "k must be an integer less than or equal to n");
+ }
+ goto error;
+ }
+
+ factors = PyLong_AsLongLongAndOverflow(k, &overflow);
+ if (overflow > 0) {
+ PyErr_Format(PyExc_OverflowError,
+ "k must not exceed %lld",
+ LLONG_MAX);
+ goto error;
+ }
+ else if (overflow < 0 || factors < 0) {
+ if (!PyErr_Occurred()) {
+ PyErr_SetString(PyExc_ValueError,
+ "k must be a non-negative integer");
+ }
+ goto error;
+ }
+
+ if (factors == 0) {
+ result = PyLong_FromLong(1);
+ goto done;
+ }
+
+ result = n;
+ Py_INCREF(result);
+ if (factors == 1) {
+ goto done;
+ }
+
+ factor = n;
+ Py_INCREF(factor);
+ for (i = 1; i < factors; ++i) {
+ Py_SETREF(factor, PyNumber_Subtract(factor, _PyLong_One));
+ if (factor == NULL) {
+ goto error;
+ }
+ Py_SETREF(result, PyNumber_Multiply(result, factor));
+ if (result == NULL) {
+ goto error;
+ }
+ }
+ Py_DECREF(factor);
+
+done:
+ Py_DECREF(n);
+ Py_DECREF(k);
+ return result;
+
+error:
+ Py_XDECREF(factor);
+ Py_XDECREF(result);
+ Py_DECREF(n);
+ Py_DECREF(k);
+ return NULL;
+}
+
+
+/*[clinic input]
math.comb
n: object
@@ -3028,11 +3142,24 @@ math_comb_impl(PyObject *module, PyObject *n, PyObject *k)
if (n == NULL) {
return NULL;
}
+ if (!PyLong_CheckExact(n)) {
+ Py_SETREF(n, _PyLong_Copy((PyLongObject *)n));
+ if (n == NULL) {
+ return NULL;
+ }
+ }
k = PyNumber_Index(k);
if (k == NULL) {
Py_DECREF(n);
return NULL;
}
+ if (!PyLong_CheckExact(k)) {
+ Py_SETREF(k, _PyLong_Copy((PyLongObject *)k));
+ if (k == NULL) {
+ Py_DECREF(n);
+ return NULL;
+ }
+ }
if (Py_SIZE(n) < 0) {
PyErr_SetString(PyExc_ValueError,
@@ -3050,7 +3177,7 @@ math_comb_impl(PyObject *module, PyObject *n, PyObject *k)
"k must be an integer less than or equal to n");
goto error;
}
- cmp = PyObject_RichCompareBool(k, temp, Py_GT);
+ cmp = PyObject_RichCompareBool(temp, k, Py_LT);
if (cmp > 0) {
Py_SETREF(k, temp);
}
@@ -3174,6 +3301,7 @@ static PyMethodDef math_methods[] = {
{"tanh", math_tanh, METH_O, math_tanh_doc},
MATH_TRUNC_METHODDEF
MATH_PROD_METHODDEF
+ MATH_PERM_METHODDEF
MATH_COMB_METHODDEF
{NULL, NULL} /* sentinel */
};
View Lorry Controller Status