algorithm - 半随机子集

Question

我正在尝试生成具有一些限制的半随机子集。

以下是带有示例值的变量描述:

• ObjCount - 对象的数量 (12)
• VisibleCount(又名 SetSize)- 每组对象的数量 (6)
• SetCount - 组数 (12)
• ObjAppearances - 对象出现的集合数 = SetCount * VisibleCount/ObjCount

我需要生成遵循这些规则的给定数量的集合 (SetCount):

1. 每个集合都是对象的集合，但任何对象都不能在一个集合中出现超过一次。
2. 此外，每个对象都应该在相同数量的集合中。 如果不是均匀分布，那么一个对象出现的数量集合可以相差1(有些对象是4组，有些是5组)。我会尽量避免这种情况，所以它并不重要。

事实证明，它远没有我最初想象的那么微不足道。谁能帮我一些代码/伪代码？通用版本的解决方案也会非常有帮助。

提前致谢。

编辑: VisibleCount 是设置的大小。对象出现的次数(ObjAppearances)为SetCount * VisibleCount/ObjCount

Edit2:我还应该补充一点，我希望这些集合相当随机。如果集合都具有顺序对象(例如 set1:5,6,7 set2:3,4,5 set3:10,11,0)，则该解决方案没有用。抱歉没说清楚。

Edit3:这是一个行不通的解决方案。 (在 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 矩阵，并用 1 和 0 填充它，使得每列包含 VisibleCount 个，每行包含(几乎)相同数量的。此时顺序无关紧要。
2. 打乱列(和行，如果 ObjCount 不均匀划分 SetCount × VisibleCount)。
3. 对于每一列i，如果第j行的单元格等于1，添加对象j以设置i>.

对于 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}