設置封面：生成測試實例

Question

我期待着用遺傳算法解決Set Cover Problem。我一直在尋找一些好的測試例子，但沒有取得任何大的成功。

我正在尋找的是一些實例，形式如下：集U = {1,2，...，n}和它的子集S = {{1,2}，{4 }，{3,4,5}}，其中S的聯合爲U.

當然，這是一個小例子，因爲我希望找到一些更大的實例。

那麼，有沒有人有任何關於這種類型的實例的好來源，或者可能是一種生成它們的方法嗎？

後來編輯：所以我看到這個問題已被擱置。我的不好，我會增加一點點細節。

首先，我已經搜索了一些測試實例的集合覆蓋問題。我期望找到的是一些像我上面描述的那些實例。運氣不好，我找到了類似於this的東西。我必須說，鏈接中沒有那麼多的細節可以借我這些實例。

所以我開始考慮一種生成它們的方法。一個pseudocodish解決方案：

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) 

雖然我不知道，如果工會（子集）= 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}]