random_combination_with_replacement recipe has misleading docstring

[pochmann]

Documentation

The random module has four recipes that are supposed to "efficiently make random selections from the combinatoric iterators in the itertools module". And their docstrings all say "Random selection from [iterator]". Both suggest they're equivalent to random.choice(list(iterator)), just efficiently.

For example, itertools.combinations_with_replacement([0, 1], r=4) produces these five combinations:

(0, 0, 0, 0)
(0, 0, 0, 1)
(0, 0, 1, 1)
(0, 1, 1, 1)
(1, 1, 1, 1)

So random.choice(list(iterator)) would return one of those five with 20% probability each.

But the random_combination_with_replacement recipe instead produces these probabilities:

(0, 0, 0, 0)  6.25%
(0, 0, 0, 1) 25.00%
(0, 0, 1, 1) 37.50%
(0, 1, 1, 1) 25.00%
(1, 1, 1, 1)  6.25%

Here's an implementation that is equivalent to random.choice(list(iterator)):

def random_combination_with_replacement(iterable, r):
    "Random selection from itertools.combinations_with_replacement(iterable, r)"
    pool = tuple(iterable)
    n = len(pool)
    indices = sorted(random.sample(range(n+r-1), k=r))
    return tuple(pool[i-j] for j, i in enumerate(indices))

---

One can view the combinations as the result of actually simulating r random draws with replacement, where the multiset {0,0,1,1} indeed occurs more often, namely as 0011, 0101, 0110, etc. But that is not the only valid view and isn't the view suggested by the documentation (as my first paragraph argued). Though if that view and the bias is the intention, then I suggest its documentation should mention the bias.

Test code

Attempt This Online!

import random
import itertools
from collections import Counter

iterable = [0, 1]
r = 4


#-- itertools ----------------------

print('itertools')
for comb in itertools.combinations_with_replacement(iterable, r):
    print(comb)


#-- from iterator ------------------

def random_combination_with_replacement_from_iterator(iterable, r):
    "Random selection from itertools.combinations_with_replacement(iterable, r)"
    iterator = itertools.combinations_with_replacement(iterable, r)
    return random.choice(list(iterator))


#-- current random recipe ----------

def random_combination_with_replacement(iterable, r):
    "Random selection from itertools.combinations_with_replacement(iterable, r)"
    pool = tuple(iterable)
    n = len(pool)
    indices = sorted(random.choices(range(n), k=r))
    return tuple(pool[i] for i in indices)


#-- proposed random recipe ---------

def random_combination_with_replacement_proposal(iterable, r):
    "Random selection from itertools.combinations_with_replacement(iterable, r)"
    pool = tuple(iterable)
    n = len(pool)
    indices = sorted(random.sample(range(n+r-1), k=r))
    return tuple(pool[i-j] for j, i in enumerate(indices))


#-- Comparison

for func in random_combination_with_replacement_from_iterator, random_combination_with_replacement, random_combination_with_replacement_proposal:
    print()
    print(func.__name__)
    N = 100000
    ctr = Counter(func(iterable, r) for _ in range(N))
    for comb, freq in sorted(ctr.items()):
        print(comb, f'{freq/N:6.2%}')

Test results

itertools
(0, 0, 0, 0)
(0, 0, 0, 1)
(0, 0, 1, 1)
(0, 1, 1, 1)
(1, 1, 1, 1)

random_combination_with_replacement_from_iterator
(0, 0, 0, 0) 19.89%
(0, 0, 0, 1) 20.08%
(0, 0, 1, 1) 20.01%
(0, 1, 1, 1) 19.88%
(1, 1, 1, 1) 20.14%

random_combination_with_replacement
(0, 0, 0, 0)  6.14%
(0, 0, 0, 1) 24.98%
(0, 0, 1, 1) 37.71%
(0, 1, 1, 1) 25.04%
(1, 1, 1, 1)  6.13%

random_combination_with_replacement_proposal
(0, 0, 0, 0) 20.17%
(0, 0, 0, 1) 19.82%
(0, 0, 1, 1) 20.18%
(0, 1, 1, 1) 19.88%
(1, 1, 1, 1) 19.95%

Linked PRs

• GH-102653: Make recipe docstring show the correct distribution #102742
• [3.11] GH-102653: Make recipe docstring show the correct distribution (GH-102742) #102754

[terryjreedy]

@rhettinger

[stevendaprano]

Both suggest they're equivalent to random.choice(list(iterator)), just efficiently.

I cannot see anything in the documentation that says or implies that. The text immediately under the heading "Recipes" says:

"These recipes show how to efficiently make random selections from the combinatoric iterators in the itertools module"

But it doesn't say anything about being equivalent to random.choice(list(iterator)). Where did you see that?

[rhettinger]

@pochmann Please assign these to me as you produce one issue after another on the various recipes. In every case, the author of the code should be looped in on the conversation.

[pochmann]

@stevendaprano I didn't see that code, I'm saying that's what "random selection from [an iterator]" sounds like. How else do you interpret that?

@rhettinger Ok, next time.

[rhettinger]

I agree with @pochmann that there is an issue here. The docs do imply (falsely) that the output of the itertool is what is being sampled.

The actual intent of the recipe was to model selection with replacement and then subsequently disregarding order. That happens to not be the same as making equiprobable selections from a deduped result space.

I'll spend some more time thinking about this. For the moment, I'm inclined to just update the docstring to make clear what random process is being modeled.

[rhettinger]

Here's a possible new docstring:

def random_combination_with_replacement(iterable, r):  # baseline
    """Choose r elements with replacement.  Order the result to match the iterable.

    When the input iterable is already sorted, this is equivalent to:

        sorted(random.choice(list(itertools.product(iterable, repeat=r))))

    And because the result is sorted, it would be contained in:
    
        set(itertools.combinations_with_replacement(iterable, r))
    
    """
    pool = tuple(iterable)
    n = len(pool)
    indices = sorted(random.choices(range(n), k=r))
    return tuple(pool[i] for i in indices)

This is likely overkill and perhaps only the first line is needed. This recipe has been around for a while there haven't previously been any misunderstandings. This is likely because it matches what people usually want and because the four line recipe is clear about what it does.

[pochmann]

Sounds alright. I'd probably remove the middle paragraph, I don't think it really helps and might even be distracting. Then the third paragraph could shrink to just extend the first:

def random_combination_with_replacement(iterable, r):  # baseline
    """Choose r elements with replacement.  Order the result to match the iterable,
    so it would be contained in:
    
        set(itertools.combinations_with_replacement(iterable, r))
    
    """

Or maybe even without the set:

def random_combination_with_replacement(iterable, r):  # baseline
    """Choose r elements with replacement.  Order the result to match the iterable,
    so it would occur in:
    
        itertools.combinations_with_replacement(iterable, r)
    
    """

This recipe has been around for a while there haven't previously been any misunderstandings. This is likely because it matches what people usually want and because the four line recipe is clear about what it does.

Might also be because it's rarely used. A GitHub search found 434 occurrences, most of which just defining the function, I had to go to page 5 of the results to find someone using it, and that was for test data in a benchmark about container types and their membership test speeds, where I doubt they cared about the distribution.