Установить обложку: создание тестовых экземпляров

Question

Я с нетерпением жду, чтобы решить проблему Set Cover, используя генетический алгоритм. Я везде искал хорошие тестовые примеры, но без особого успеха.

То, что я ищу, - это несколько экземпляров в форме: набор U = {1,2,...,n} и набор его подмножеств S={{1,2}, {4}, {3,4,5}}, где объединением S является U.

Конечно, это небольшой пример, так как я хотел бы найти несколько более крупных примеров.

Итак, есть ли у кого-нибудь представление о хорошем источнике подобных случаев или о способе их генерации?

Позднее редактирование: так что я вижу, что вопрос был отложен. Мой плохой, я добавлю немного больше деталей.

Во-первых, я погуглил некоторые тестовые экземпляры для решения проблемы покрытия. То, что я ожидал найти, было несколько примеров, подобных тем, что я описал выше. Не повезло, я нашел что-то похожее на это. Должен сказать, что в ссылке было не так много деталей, которые дают мне представление об этих случаях.

Поэтому я начал думать о методе их генерации. Псевдокодовое решение:

given set G=[1,2....,n]
no_of_subsets  = random integer
subsets = []
for i in k: 
    subset = random.sample(G, random(0, len(G))
    subsets.add(subset)

Хотя я не был уверен, если union(subsets) = G, так что мои сомнения были именно там, поэтому я нуждался в некоторых уже созданных тестовых экземплярах.

Answer 1

Вы можете создать набор, получая случайную выборку из списка возможных чисел. И они генерируют список (с заранее определенным размером) своих подмножеств также путем получения случайных выборок со случайным размером, и для последнего подмножества вы просто дополняете то, чего не хватало, поэтому сумма подмножеств будет всем набором.

Пример:

import random

n = 100
m = 10 #size of set
l = 5 #size of list of subsets
possible_numbers = range(n)

U = set(random.sample(possible_numbers, m))

subsets = []
control = set()
for i in range(l - 1):
    sub_size = random.randrange(m)
    sub = set(random.sample(U, sub_size))
    subsets += [sub]
    control |= sub

rest = U - control     
if rest:
    subsets += [rest]

print(U)
--> {97, 99, 69, 9, 15, 52, 53, 55, 28, 30}

print(subsets)
--> [{28, 52, 69, 55}, {69}, {99, 28, 52, 55}, {69, 9, 15, 52, 53, 55}, {97, 30}]