Я пытаюсь сгенерировать полуслучайные подмножества с некоторыми ограничениями.
Вот описания переменных с примерами значений:
- ObjCount - количество объектов (12)
- VisibleCount (AKA SetSize) - количество объектов в наборе (6)
- SetCount - количество наборов (12)
- ObjAppearances - количество наборов, в которомпоявляется объект =
SetCount * VisibleCount / ObjCount
Мне нужно создать определенное количество наборов (SetCount), которые следуют следующим правилам:
- Каждый набор представляет собой набор объектов,но ни один объект не может быть в одном наборе более одного раза.
- Кроме того, каждый объект должен иметь одинаковое количество наборов. Если это не делится равномерно, то наборы номеров, в которых появляется объект, могут быть отключены на 1 (некоторые объекты в 4 наборах, а другие в 5).Я постараюсь избежать этой ситуации, так что это не критично.
Оказалось, что это гораздо менее тривиально, чем я первоначально думал.Может ли кто-нибудь помочь мне с некоторым кодом / psuedocode?Было бы очень полезно найти решение обобщенной версии.
Заранее спасибо.
Редактировать: 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();
}