首页 文章

有效地绘制具有“最大多样性”的组合

提问于
浏览 次
1

On可以使用给定数组中的 n 元素创建所有可能的组合，如：

from itertools import combinations
[*combinations(range(4), 2)]
# [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

我正在尝试找到一种方法来调整它，以便用"maximum diversity"找到 m 这些组合 . 我的意思可能最好用一个例子来解释：

diverse_combinations(range(4), n=2, m=3)
# either of these would be what I'm looking for
# [(0, 1), (2, 3), (0, 2)]  # or
# [(0, 1), (2, 3), (1, 2)]  # or 
# [(0, 2), (1, 3), (0, 1)]  # ...

所以我基本上希望我的子集组合中的各个元素尽可能接近均匀分布（或尽可能接近） . 因此，这不是我想要的：

def diverse_combinations(arr, n, m): 
    for idx, comb in enumerate(combinations(arr, n)): 
        if idx == m: 
            break
        yield comb 

[*diverse_combinations(np.arange(4), n=2, m=3)]  
# [(0, 1), (0, 2), (0, 3)]

最后，我正在看的情况是性能敏感的，因为它归结为类似于：

diverse_combinations(range(100), n=50, m=100)
# a list with 100 tuples of len=50 where each element appears 
# ~equally often

我很高兴有任何提示！

python-3.x statistics combinations

1 回答

  • 1

    好的，所以我提出了这个解决方案，它运作得相当好 . 我把它放在这里，以防其他人有用：

    # python3
import numpy as np
from scipy.special import comb

def diverse_combinations(arr, size, count):
    if count > comb(len(arr), size):
        raise ValueError('Not enough possible combinations')
    possible_draws = np.floor(len(arr) / size).astype(int)
    combs = set()
    while len(combs) < count:
        new_combs = np.random.choice(
            arr, size=(possible_draws, size), replace=False)
        combs.update([tuple(sorted(cc)) for cc in  new_combs])
    return [*combs][:count]

    这给出了所需行为的合理近似值：

    # this case has an exact solution
np.unique(diverse_combinations(range(100), 50, 100), return_counts=True)[1]
# array([50, 50, 50, 50, 50,...

# here 50 elements appear one time more often   
np.unique(diverse_combinations(range(100), 50, 101), return_counts=True)[1]
# array([50, 50, 51, 50, 51,...

# if 'arr' is not divisible by 'size' the result is less exact
np.unique(diverse_combinations(range(100), 40, 100), return_counts=True)[1] 
# array([44, 45, 40, 38, 43,...
    回复于

相关问题