子集的半随机集

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表示。解决办法可能是以最少的次数选取集合。如果存在多个最少计数的集合，则随机选择其中一个。