將N個元素分成k個大小的子集

Question

如果我有N個不同的數字，他們將被分成k個大小的子集，這樣每個子集至少有一個共同的元素。請幫助我的算法。輸出應該是這樣的 如果我有從1到5和k = 3元素一些東西則輸出應該是：

- S0 = {0, 1, 2} 
- S1 = {1, 3, 5} 
- S2 = {2, 4, 5} 
- S3 = {0, 3, 4} 
- S4 = {1, 4, 6} 
- S5 = {0, 5, 6} 
- S6 = {2, 3, 6} 

Answer 1

1）注意，如果k = 1和|S| > 1然後這是不可能的（即k = 1和S = {1,2}）

2）否則，取第一個數字，將其作爲每個子集中的第一個數字始終添加，然後用剩餘的數字填充子集。如果沒有足夠的數字填寫最後一個子集，只需使用隨機數填寫即可。

按照您的例子k = 3和S = {0,1,2,3,4,5,6}我們可以這樣做：

• S0 = {0,1,2}（第一號+未來2）
• S1 = {0,3,4}（第一號+未來2後1,2）
• S2 = {0,5,6}（在這種情況下，我們很幸運，因爲我們能夠填寫S2，否則應該只爲0 .. 5我們可以添加一個隨機數作爲最後一個）

Answer 2

你的例子有7個點（0，...，6）和7個「行」（例如，「行」{0,1,2}）。請注意，任何兩條線「交叉」在一個點上，任何兩點確定一條線。 （從0，...，6中挑選兩個數字，您會看到只有一組數字和這兩個數字。）

因此，您提出的設計有比您所描述的更多的限制。如果你只是想子集的每對有至少一個共同的元素，你可以把0到每個set和get Ç _2個子集{0,1,2}，{0,1 ，3}，{0,1,4}等等，這並不難。

點和線的幾何語言不是巧合。如果你想要一個每一對子集都有一個共同元素的設計，你可能需要一個投影平面。你給的例子叫做法諾飛機。對於N和k的所有組合，射影平面是不可能的。您必須具有N = m^2 + m + 1和k = m + 1，其中m被稱爲飛機的訂單。使用模運算（例如，m = 2給出Fano平面），通過用於m素數的「向量空間構造」可以容易地構建投影面。他們稍微難以使用向量空間構造和有限域來構造素數的冪，m = p^k。細節可以在許多不同的參考文獻中找到。

對於其他訂單，很少有人知道，除了通過蠻力計算可知，有訂單6沒有射影飛機和10

這是你想要的嗎？如果沒有，還有其他的「組合塊設計」可能具有你想要的屬性，但你必須精確地滿足你的需求。