Эффективно рисуйте комбинации с «максимальным разнообразием» - PullRequest
Новая
       11

Эффективно рисуйте комбинации с «максимальным разнообразием»

0 голосов
/ 09 декабря 2018

On может создать все возможные комбинации с n элементами из данного массива, например: 

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

Я пытаюсь найти способ адаптировать это, чтобы найти 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

Ярад за любые подсказки!

1 Ответ

0 голосов
/ 11 декабря 2018

Хорошо, поэтому я придумала это решение, которое работает достаточно хорошо.Я помещу это здесь в случае, если это полезно для кого-то еще: 

# 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,...
...