能否编写根据索引生成指定n Multichoose r组合的非遍历函数？

Absolutely! You don’t need to generate every combination before the i-th one to get the target—there’s a direct, efficient way to compute it by leveraging combinatorial math. Let’s walk through how this works, with code to back it up.

Background: n Multichoose r Basics #

First, a quick recap: n multichoose r (combinations with repetition) counts the number of ways to choose r elements from n distinct elements where order doesn’t matter and elements can be reused. The total number of such combinations is given by the binomial coefficient C(n + r - 1, r)—that’s the upper bound for your index i (which should range from 0 to this total minus 1).

The combinations are typically ordered in non-decreasing order (like your example: [0,0], [0,1], [0,2], [1,1], etc.), which is key to our approach.

The Core Idea #

Instead of generating all prior combinations, we’ll build the target combination one element at a time. For each position in the result:

1. We test possible values starting from the smallest valid number (which is the value of the previous element, since the sequence is non-decreasing).
2. For each candidate value, we calculate how many combinations would start with that value (and valid values for the remaining positions).
3. If our index i falls within that count, we lock in this value and move to the next position. If not, we subtract that count from i and try the next candidate value.

Step-by-Step Implementation #

First, we need a helper function to compute binomial coefficients (combinations) efficiently. Then we’ll build the main function to map n, r, and i to the target combination.

Helper Function: Binomial Coefficient Calculation #

def comb(a, b):
    """Calculate the binomial coefficient C(a, b)"""
    if b < 0 or b > a:
        return 0
    if b == 0 or b == a:
        return 1
    # Use symmetry to minimize calculations (C(a,b) = C(a,a-b))
    b = min(b, a - b)
    result = 1
    for i in range(1, b + 1):
        result = result * (a - b + i) // i
    return result

Main Function: Get the i-th Combination #

def get_multichoose_combination(n, r, i):
    total_combinations = comb(n + r - 1, r)
    if i < 0 or i >= total_combinations:
        raise ValueError(f"Index i must be between 0 and {total_combinations - 1}")
    
    combination = []
    current_min = 0  # The smallest value we can use for the next element
    
    for position in range(r):
        remaining_positions = r - position - 1
        candidate = current_min
        
        while True:
            # Calculate how many combinations start with this candidate
            # Remaining elements are chosen from [candidate, n-1], which is (n - candidate) options
            # So the count is C( (n - candidate - 1) + remaining_positions, remaining_positions )
            count = comb( (n - candidate - 1) + remaining_positions, remaining_positions )
            
            if i < count:
                # This candidate is part of our target combination
                combination.append(candidate)
                current_min = candidate  # Next element can't be smaller than this
                break
            else:
                # Move to the next candidate, adjust i accordingly
                i -= count
                candidate += 1
    
    return combination

Test It With Your Example #

Let’s verify with your 3 multichoose 2 case:

n, r = 3, 2
for i in range(6):
    print(f"i={i}: {get_multichoose_combination(n, r, i)}")

Output: #

i=0: [0, 0]
i=1: [0, 1]
i=2: [0, 2]
i=3: [1, 1]
i=4: [1, 2]
i=5: [2, 2]

Perfect—matches exactly what you described!

Why This Works #

This approach is analogous to "digit extraction" in number systems, but instead of base-10 digits, we’re using combinatorial counts to narrow down each element. It runs in O(r * n) time in the worst case, but in practice, the inner loop breaks early for most indices, making it much faster than generating all prior combinations.

内容的提问来源于stack exchange，提问作者yea