如何从给定数组生成元素可重复、和在指定范围的等概率随机数组？

你的核心问题是要在不枚举所有可能的前提下，等概率抽样所有元素可重复、和在指定[L, R]范围内的数组组合。当前的累加方法不仅容易超出上限，而且完全无法保证等概率——它只覆盖了“从0开始累加直到超过下限”的部分组合，且不同组合被选中的概率差异极大。

推荐使用Metropolis-Hastings马尔可夫链蒙特卡洛算法，它可以通过迭代调整的方式，收敛到所有有效组合的均匀分布，不需要枚举任何组合。

具体实现步骤 #

1. 生成初始有效组合 #

先随机生成一个符合和范围的初始数组，作为迭代的起点：

import random

def generate_initial_combination(arr, L, R):
    current_sum = 0
    combo = []
    while True:
        x = random.choice(arr)
        if current_sum + x <= R:
            combo.append(x)
            current_sum += x
            if current_sum >= L:
                return combo
        else:
            if current_sum >= L:
                return combo
            continue

2. 用MCMC迭代调整，保证等概率 #

通过随机修改当前组合（添加、移除、替换元素），并根据规则决定是否接受修改，经过足够多迭代后，当前组合就是等概率的有效组合：

def sample_valid_combination(arr, L, R, iterations=1000):
    combo = generate_initial_combination(arr, L, R)
    current_sum = sum(combo)
    
    for _ in range(iterations):
        # 随机选择操作类型：添加、移除、替换，各1/3概率
        op = random.choice(['add', 'remove', 'replace'])
        
        if op == 'add':
            x = random.choice(arr)
            if current_sum + x <= R:
                combo.append(x)
                current_sum += x
        elif op == 'remove':
            if len(combo) == 0:
                continue
            idx = random.randint(0, len(combo)-1)
            x = combo.pop(idx)
            if current_sum - x >= L:
                current_sum -= x
            else:
                combo.insert(idx, x)
        elif op == 'replace':
            if len(combo) == 0:
                continue
            idx = random.randint(0, len(combo)-1)
            old_x = combo.pop(idx)
            new_x = random.choice(arr)
            new_sum = current_sum - old_x + new_x
            if L <= new_sum <= R:
                combo.append(new_x)
                current_sum = new_sum
            else:
                combo.insert(idx, old_x)
    
    return combo

3. 调用示例 #

arr = [10,25,40,55,80,110]
L = 100
R = 150
result = sample_valid_combination(arr, L, R)
print(f"有效组合：{result}，和为{sum(result)}")

关键原理说明 #

Metropolis-Hastings算法通过满足细致平衡条件，保证经过足够多迭代后，采样的组合分布会收敛到所有有效组合的均匀分布：

• 每一步的修改操作都是可逆的
• 只有符合条件的修改才会被接受
• 迭代次数足够时，初始组合的影响会被完全消除，最终得到的组合是等概率的

注意事项 #

• 迭代次数可以根据数组规模调整，一般1000次足够覆盖大部分场景，数组元素越多可能需要适当增加次数
• 操作类型的概率可以灵活调整，比如如果希望组合长度变化更频繁，可以提高添加/移除的概率
• 如果数组中有极小元素，初始组合生成可能需要多尝试几次，但整体效率远高于枚举

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