子集的半隨機集

Question

我試圖生成具有一些限制的半隨機子集。

下面是與示例值的變量的描述：

• ObjCount - 對象的數量（12）
• VisibleCount（AKA的setSize） - 每組對象的數量（6）
• SetCount - 組（12）
• ObjAppearances數量 - 在其中出現的對象組的數量= SetCount * VisibleCount/ObjCount

我需要製作一個給定的多套（SetCount），其遵循以下規則：

1. 每一組是對象的集合，但沒有對象可以是在一組不止一次。
2. 此外，每個對象應該在相同數量的集合中。 如果它不均勻分佈，那麼一個對象出現的數字集可以被關閉1（一些對象在4個集合中，另外一些在5中）。我會盡量避免這種情況，所以這不是關鍵。

事實證明，這並不像我最初想象的那麼微不足道。任何人都可以幫我一些代碼/ psuedocode？一個通用版本的解決方案也是非常有用的。

在此先感謝。

編輯： VisibleCount是設定的大小。對象出現的次數（ObjAppearances）爲SetCount * VisibleCount/ObjCount

編輯2：我還應該補充說我希望這些集合相當隨機。如果這些集合都具有順序對象（例如set1：5,6,7 set2：3,4,5 set3：10,11,0），則該解決方案無用。對不起，沒有說清楚。

編輯3：這是一個不起作用的解決方案。 （在C＃）

static void Main(string[] args) 
{ 
    var ObjectCount = 12; 
    var SetSize = 6; 
    var SetCount = 12; 

    var Sets = Enumerable.Range(0, SetCount).Select(i => new List<int>()).ToArray(); // a SetCount-sized array of lists 
    var ObjectAppearances = SetSize * SetCount/ObjectCount; 
    var rand = new Random(); 

    // fill the sets 
    for (int obj = 0; obj < ObjectCount; obj++) 
    { 
     for (int a = 0; a < ObjectAppearances; a++) 
     { 
      // get the collection of sets that are not full 
      var nonFullSets = Sets.Where(s => s.Count < SetSize); 
      // get the collection of non-full sets without obj 
      var setsWithoutObj = nonFullSets.Where(s => !s.Contains(obj)); 
      /////////////////////// 
      // Here is the problem. All of the non-full sets may already 
      // have a copy of obj 
      /////////////////////// 
      // choose a set at random 
      var currentSetIndex = rand.Next(setsWithoutObj.Count()); 
      var currentSet = setsWithoutObj.ElementAt(currentSetIndex); 
      // add the object 
      currentSet.Add(obj); 
     } 
    } 

    // randomize the order within each set and output each 
    for (int i = 0; i < SetCount; i++) 
    { 
     var randomlyOrderedSet = Sets[i].OrderBy(obj => rand.Next()); 
     Sets[i] = new List<int>(randomlyOrderedSet); 

     // output 
     foreach (var obj in Sets[i]) 
      Console.Write(string.Format("{0}, ", obj)); 
     Console.WriteLine(); 
    } 
    Console.ReadLine(); 
} 

這裏的解決方案 - MizardX的答案的實現

static void Main(string[] args) 
{ 
    var ObjectCount = 12; 
    var SetSize = 6; 
    var SetCount = 10; 
    var rand = new Random(); 

    // make a matrix [SetCount][ObjectCount] 
    var Matrix = new int[SetCount][]; 
    for (int s = 0; s < SetCount; s++) 
     Matrix[s] = Enumerable.Repeat(0, ObjectCount).ToArray(); 

    // put approximately the same number of objects in each set by 
    // adding sequential objects to sequential sets (not random) 
    for (int s = 0; s < SetCount; s++) 
    { 
     var firstObject = (int)Math.Ceiling((double)s * ObjectCount/SetCount); 
     for (int i = 0; i < SetSize; i++) 
     { 
      var o = (firstObject + i) % ObjectCount; 
      Matrix[s][o] = 1; 
     } 
    } 

    // output the result 
    for (int s = 0; s < SetCount; s++) 
    { 
     for (int o = 0; o < ObjectCount; o++) 
     { 
      Console.Write(string.Format("{0}, ", Matrix[s][o])); 
     } 
     Console.WriteLine(); 
    } 
    Console.WriteLine(); 

    // shuffle sets 
    Matrix = Matrix.OrderBy(s => rand.Next()).ToArray(); 
    // make a new matrix for shuffle objects 
    var objOrder = Enumerable.Range(0, ObjectCount).OrderBy(o => rand.Next()).ToArray(); 
    var MatrixSuffled = new int[SetCount][]; 
    for (int s = 0; s < SetCount; s++) 
     MatrixSuffled[s] = Enumerable.Repeat(0, ObjectCount).ToArray(); 
    for (int o = 0; o < ObjectCount; o++) 
    { 
     var oldObj = o; 
     var newObj = objOrder[o]; 
     for (int s = 0; s < SetCount; s++) 
     { 
      MatrixSuffled[s][newObj] = Matrix[s][oldObj]; 
     } 
    } 

    // check and output the result 
    var objectCounters = Enumerable.Repeat(0, ObjectCount).ToArray(); 
    for (int s = 0; s < SetCount; s++) 
    { 
     var objectsInThisSet = 0; 
     for (int o = 0; o < ObjectCount; o++) 
     { 
      objectsInThisSet += MatrixSuffled[s][o]; 
      objectCounters[o] += MatrixSuffled[s][o]; 
      Console.Write(string.Format("{0}, ", MatrixSuffled[s][o])); 
     } 
     Console.Write(string.Format(" {0}", objectsInThisSet)); 
     Console.WriteLine(); 
    } 
    // output object count 
    Console.WriteLine(); 
    for (int o = 0; o < ObjectCount; o++) 
     Console.Write(string.Format("{0} ", objectCounters[o])); 
    Console.ReadLine(); 
} 

Answer 1

1. 創建ObjCount × SetCount矩陣，使得每個列包含VisibleCount那些與一和零填充它，和每行包含一些的（幾乎）相等數量。訂單在這一點上是無關緊要的。
2. shuffle的列（以及行，如果ObjCount不分SetCount × VisibleCount均勻）。
3. 對於每一列我，如果在排Ĵ小區等於1，添加對象Ĵ設置我。

12點的對象，6套和3可見，最初的矩陣可能是這樣的：

1 0 0 0 0 0 
1 0 0 0 0 0 
1 1 0 0 0 0 
0 1 0 0 0 0 
0 1 1 0 0 0 
0 0 1 0 0 0 
0 0 1 1 0 0 
0 0 0 1 0 0 
0 0 0 1 1 0 
0 0 0 0 1 1 
0 0 0 0 1 1 
0 0 0 0 0 1 

而洗牌後：

1 0 1 0 0 0 
0 0 0 0 1 0 
1 1 0 0 0 0 
0 0 0 1 1 0 
0 1 0 0 0 0 
0 0 0 1 0 0 
0 0 1 0 0 0 
1 0 1 0 0 0 
0 0 0 1 0 0 
0 0 0 0 1 1 
0 1 0 0 0 1 
0 0 0 0 0 1 

在組得到的：

{1,3,8} 
{3,5,11} 
{1,7,8} 
{4,6,9} 
{2,4,10} 
{10,11,12} 

Answer 2

resultSets = new Set[SetCount]; // create an array of sets to hold the results 

totalObjectsPlaced = 0; 
currentObjectIndex = 0; 

while (totalObjectsPlaced < (ObjCount * VisibleCount)) { 
    do { 
    randomSet = rand(SetCount); 
    } while (!resultSets[randomSet].contains(object[currentObjectIndex])); 
    resultSets[randomSet].add(object[currentObjectIndex]); 
    currentObjectIndex = (currentObjectIndex + 1) % ObjCount; 
    totalObjectsPlaced++; 
} 

Answer 3

讓o是對象的數量，v是知名度計數，s是多少套。

1. 對於每個對象[重複o倍]
   1.1。重複v次。
   1.1.1隨機挑選一個集合並插入該對象 - 直到步驟1.1結束爲止，不要重用該集合。

編輯：解決方案失敗，因爲saroz表示。解決辦法可能是以最少的次數選取集合。如果存在多個最少計數的集合，則隨機選擇其中一個。