Repository: more-itertools/more-itertools (python)

Issue:
[Feature Request] inverse_nth_*
### Description

The inverse of `nth_combination`, `nth_permutation`, etc ... functions.

For example, it would have a signature `inverse_nth_combination(iterable, r, comb)`
and would return `list(combinations(iterable, r)).index(sorted(comb))`
without enumerating all combinations.




Pull request description:
Indexing of combinations with replacement
### Issue reference
Related to #684 and #685, and closes #685.

### Changes
This pull request implements the function `combination_with_replacement_index` as an analog to `combination_index`, but for `itertools.combinations_with_replacement` instead of `itertools.combinations`. The pull request includes a test-class similar to the test-class for `combination_index`.

The algorithm used (and the non-standard naming of the `occupation`-list in the function) is from equation 20 in [https://link.aps.org/doi/10.1103/PhysRevA.81.022124](https://link.aps.org/doi/10.1103/PhysRevA.81.022124). I am not sure if this is the most efficient algorithm, but it works.

I have tried to adhere to the style used in this project, but let me know if I missed my mark.


Patch:
diff --git a/more_itertools/more.py b/more_itertools/more.py
index 379f5f6..1e421f2 100755
--- a/more_itertools/more.py
+++ b/more_itertools/more.py
@@ -53,6 +53,7 @@ __all__ = [
     'circular_shifts',
     'collapse',
     'combination_index',
+    'combination_with_replacement_index',
     'consecutive_groups',
     'constrained_batches',
     'consumer',
@@ -3956,6 +3957,61 @@ def combination_index(element, iterable):
     return factorial(n + 1) // (factorial(k + 1) * factorial(n - k)) - index
 
 
+def combination_with_replacement_index(element, iterable):
+    """Equivalent to
+    ``list(combinations_with_replacement(iterable, r)).index(element)``
+
+    The subsequences with repetition of *iterable* that are of length *r* can
+    be ordered lexicographically. :func:`combination_with_replacement_index`
+    computes the index of the first *element*, without computing the previous
+    combinations with replacement.
+
+        >>> combination_with_replacement_index('adf', 'abcdefg')
+        20
+
+    ``ValueError`` will be raised if the given *element* isn't one of the
+    combinations with replacement of *iterable*.
+    """
+    element = tuple(element)
+    l = len(element)
+    element = enumerate(element)
+
+    k, y = next(element, (None, None))
+    if k is None:
+        return 0
+
+    indexes = []
+    pool = tuple(iterable)
+    for n, x in enumerate(pool):
+        while x == y:
+            indexes.append(n)
+            tmp, y = next(element, (None, None))
+            if tmp is None:
+                break
+            else:
+                k = tmp
+        if y is None:
+            break
+    else:
+        raise ValueError(
+            'element is not a combination with replacment of iterable'
+        )
+
+    n = len(pool)
+    occupations = [0] * n
+    for p in indexes:
+        occupations[p] += 1
+
+    index = 0
+    for k in range(1, n):
+        j = l + n - 1 - k - sum(occupations[:k])
+        i = n - k
+        if i <= j:
+            index += factorial(j) // (factorial(i) * factorial(j - i))
+
+    return index
+
+
 def permutation_index(element, iterable):
     """Equivalent to ``list(permutations(iterable, r)).index(element)```
 
diff --git a/more_itertools/more.pyi b/more_itertools/more.pyi
index 79de37e..e10a9b0 100644
--- a/more_itertools/more.pyi
+++ b/more_itertools/more.pyi
@@ -586,6 +586,9 @@ def product_index(element: Iterable[_T], *args: Iterable[_T]) -> int: ...
 def combination_index(
     element: Iterable[_T], iterable: Iterable[_T]
 ) -> int: ...
+def combination_with_replacement_index(
+    element: Iterable[_T], iterable: Iterable[_T]
+) -> int: ...
 def permutation_index(
     element: Iterable[_T], iterable: Iterable[_T]
 ) -> int: ...


Test patch:
diff --git a/tests/test_more.py b/tests/test_more.py
index 2eea0c6..aa5c3bf 100644
--- a/tests/test_more.py
+++ b/tests/test_more.py
@@ -12,6 +12,7 @@ from itertools import (
     accumulate,
     chain,
     combinations,
+    combinations_with_replacement,
     count,
     cycle,
     groupby,
@@ -4584,6 +4585,65 @@ class CombinationIndexTests(TestCase):
             mi.combination_index(tuple('axe'), 'abcde')
 
 
+class CombinationWithReplacementIndexTests(TestCase):
+    def test_r_less_than_n(self):
+        iterable = 'abcdefg'
+        r = 4
+        first_index = {}
+        for index, element in enumerate(
+            combinations_with_replacement(iterable, r)
+        ):
+            actual = mi.combination_with_replacement_index(element, iterable)
+            expected = first_index.setdefault(element, index)
+            self.assertEqual(actual, expected)
+
+    def test_r_equal_to_n(self):
+        iterable = 'abcd'
+        r = len(iterable)
+        first_index = {}
+        for index, element in enumerate(
+            combinations_with_replacement(iterable, r=r)
+        ):
+            actual = mi.combination_with_replacement_index(element, iterable)
+            expected = first_index.setdefault(element, index)
+            self.assertEqual(actual, expected)
+
+    def test_multiplicity(self):
+        iterable = 'abacba'
+        r = 3
+        first_index = {}
+        for index, element in enumerate(
+            combinations_with_replacement(iterable, r)
+        ):
+            actual = mi.combination_with_replacement_index(element, iterable)
+            expected = first_index.setdefault(element, index)
+            self.assertEqual(actual, expected)
+
+    def test_null(self):
+        actual = mi.combination_with_replacement_index(tuple(), [])
+        expected = 0
+        self.assertEqual(actual, expected)
+
+    def test_long(self):
+        actual = mi.combination_with_replacement_index(
+            (22, 65, 68, 81), range(90)
+        )
+        expected = 2000000
+        self.assertEqual(actual, expected)
+
+    def test_invalid_order(self):
+        with self.assertRaises(ValueError):
+            mi.combination_with_replacement_index(tuple('acb'), 'abcde')
+
+    def test_invalid_large(self):
+        with self.assertRaises(ValueError):
+            mi.combination_with_replacement_index(tuple('abcdefg'), 'abcdef')
+
+    def test_invalid_match(self):
+        with self.assertRaises(ValueError):
+            mi.combination_with_replacement_index(tuple('axe'), 'abcde')
+
+
 class PermutationIndexTests(TestCase):
     def test_r_less_than_n(self):
         iterable = 'abcdefg'