#python #python-3.x #list #performance #random
#питон #python-3.x #Список #Производительность #Случайный
Вопрос:
Допустим, у меня есть список из 20 уникальных номеров, и я хочу случайным образом выбрать N = 3 номера из списка. Для каждого числа существует ограничение, заключающееся в том, что оно не может быть в окончательном образце с некоторыми другими числами, приведенными в словаре exclusions .
lst = list(range(20)) N = 3 exclusions = {0: [5], 1: [3, 13], 2: [10], 3: [1, 4, 18], 4: [3, 15, 17, 19], 5: [0], 6: [12], 7: [13, 15], 8: [10], 9: [16], 10: [2, 8, 12], 11: [15], 12: [6, 10], 13: [1, 7], 14: [], 15: [4, 7, 11], 16: [9], 17: [4], 18: [3], 19: [4]} Прямо сейчас я использую метод проб и ошибок:
import random sample = {random.choice(lst)} n_sample = 1 while n_sample lt; N: s = random.choice([x for x in lst if x not in sample]) if not set(exclusions[s]).isdisjoint(sample): sample.add(s) n_sample = 1 print(sample) # {10, 2, 12} Однако это очень неэффективно и не может охватить случай, когда вообще нет решения, особенно когда N оно большое. Может ли кто-нибудь предложить эффективный способ сделать это на Python?
Комментарии:
1. Насколько большим может быть N/список? (кроме того, разве это не эквивалентно максимальному независимому набору, который является NP-полным?)
2. Кроме того, вы сказали «случайным образом», но вас не волнует распределение? Текущее решение не похоже на то, что оно приведет к очень «равномерному» распределению.
3. Составьте набор из всех чисел, затем выберите первое число. Затем просмотрите словарь ограничений и удалите ограничения из своего набора. Повторите с остальными элементами для остальных N-1 чисел
Ответ №1:
Если исключения предварительно вычислены, вы также можете предварительно вычислить разрешенные наборы, которые удовлетворяют ограничениям исключения. Вы можете сделать это в соответствии @Sembei Norimaki's с предложением:
Составьте набор из всех чисел, затем выберите первое число. Затем просмотрите словарь ограничений и удалите ограничения из своего набора. Повторите с остальными элементами для остальных N-1 чисел
Затем во время выполнения вы можете случайным образом выбрать допустимый набор и выбрать N чисел из этого набора.
Примечание: Результирующее распределение выборочных значений здесь не будет равномерным. Это связано с тем, что элементы с большим количеством исключений, следовательно, будут исключены из большего числа разрешенных наборов. При отборе проб, учитывая большое количество выборок, ваше распределение будет сходиться к распределению того, из которого вы отбираете выборку.
Ответ №2:
Как уже предлагалось, наборы являются хорошим компаньоном для такого рода проблем:
Если вам нужен случайный выбор, то
[x for x in lst if x not in sample] может быть улучшен с помощью наборов
candidates = set(sample) - set(last) в любом случае вы должны избегать использования random в цикле while:
подсказка
Мне не ясно, как справиться с делом «без решения»:
lst = set(range(20)) N = 3 exclusions = {0: [5], 1: [3, 13], 2: [10], 3: [1, 4, 18], 4: [3, 15, 17, 19], 5: [0], 6: [12], 7: [13, 15], 8: [10], 9: [16], 10: [2, 8, 12], 11: [15], 12: [6, 10], 13: [1, 7], 14: [], 15: [4, 7, 11], 16: [9], 17: [4], 18: [3], 19: [4]} exclusions = {k:set(v) for k,v in exclusions.items()} sample = {random.choice(list(lst))} n_sample = 1 while n_sample lt; N: found = False for s in lst-sample: if not exclusions[s].isdisjoint(sample): sample.add(s) n_sample = 1 found = True break if not found: print('No solution') break print(sample)