Случайно выбрать подмножество всех комбинаций в Python - PullRequest
Новая
       42

Случайно выбрать подмножество всех комбинаций в Python

0 голосов
/ 19 мая 2018

Я могу составить список всех комбинаций двоичных значений длины n itertools.list(product([0, 1], repeat=n)), если n мало.

1000
0100
0110
1001
 .
 .
 .

Как я могу случайным образом выбрать подмножество из списка выше без предварительного построения массивного списка комбинаций, когда n большое?

Допустим, я хочу случайным образом выбрать 1 миллион комбинаций без заменыкогда n = 30 (всего 2 ^ 30 комбинаций)

Я посмотрел расширенную функцию из itertools http://docs.python.org/2/library/itertools.html#recipes

def random_product(*args, **kwds):
    "Random selection from itertools.product(*args, **kwds)"
    pools = map(tuple, args) * kwds.get('repeat', 1)
    return tuple(random.choice(pool) for pool in pools)

, но она возвращается только один раз за раз.Должен ли я выполнить цикл этой функции, пока не получу 1 миллион уникальных комбинаций?или есть лучший способ.Спасибо!

1 Ответ

0 голосов
/ 19 мая 2018

Вы можете думать о проблеме по-другому.По сути, вы просто хотите, чтобы 1 миллион случайных значений между 0 и 2^30. 

import random

num_selections = 1000000
range = 2 ** 30

def make_set(n, max):
  result = set()
  while(len(result) < n):
    rand = bin(random.randrange(max)) # converting to binary
    result.add(rand)
  return result

s = make_set(num_selections, range)

На моем компьютере это занимает около 2 секунд.Этот метод не будет эффективным, если n приблизительно равен max.Но 1000000 / (2^30) ~= 0.000931, поэтому он отлично работает.

Редактировать:

@ user2285236 Решение более лаконично: 

import random
random_group = random.sample(range(2**30), 10**6)
random_group = [bin(x) for x in random_group] # convert all to binary
...