Add itertools recipe for directly finding the n-th combination (#5161)

1 files changed, 23 insertions, 0 deletions

diff --git a/Doc/library/itertools.rst b/Doc/library/itertools.rst
index 5af5422..0b3829f 100644
--- a/Doc/library/itertools.rst
+++ b/Doc/library/itertools.rst
@@ -859,6 +859,29 @@ which incur interpreter overhead.
        indices = sorted(random.randrange(n) for i in range(r))
        return tuple(pool[i] for i in indices)
 
+   def nth_combination(iterable, r, index):
+       'Equivalent to list(combinations(iterable, r))[index]'
+       pool = tuple(iterable)
+       n = len(pool)
+       if r < 0 or r > n:
+           raise ValueError
+       c = 1
+       k = min(r, n-r)
+       for i in range(1, k+1):
+           c = c * (n - k + i) // i
+       if index < 0:
+           index += c
+       if index < 0 or index >= c:
+           raise IndexError
+       result = []
+       while r:
+           c, n, r = c*r//n, n-1, r-1
+           while index >= c:
+               index -= c
+               c, n = c*(n-r)//n, n-1
+           result.append(pool[-1-n])
+       return tuple(result)
+
 Note, many of the above recipes can be optimized by replacing global lookups
 with local variables defined as default values.  For example, the
 *dotproduct* recipe can be written as::