如何在 C# 中创建匹配特定条件的组合组？

Question

我有一份人员名单List<Person>，我需要他们根据几个条件产生组合组。通过一个例子可能最容易解释这一点。假设我有人N = 19。

List<Person> people = new List<Person>(){A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S};

我作为输入给出PreferredGroupSize。在这种情况下，PreferredGroupSize = 5;。

我需要按此PreferredGroupSize和 +/-1 为其余成员分组作为输出组合lastGroupSizes。对于 19 号，我需要people3 组 5 号尺寸和一组 4 号尺寸的所有组合。

使用一些模运算，我已经计算出了我需要的组数numGroups，以及有多少numNormalSizeGroups（即PreferredGroupSize组数）和多少numOddSizeGroups。

计算如下：

//if(mod > (PreferredGroupSize)/2.0f)) make small groups.
//else make large groups.

float val1 = N % PreferredGroupSize;
float val2 = PreferredGroupSize / 2.0f;
if (N % PreferredGroupSize == 0)
{
   lastGroupSizes = PreferredGroupSize;
   numOddSizeGroups = 0;
   numNormalSizeGroups = N / PreferredGroupSize;
}
else if (val1 > val2)
{
   lastGroupSizes = PreferredGroupSize - 1;
   numOddSizeGroups = PreferredGroupSize - N % PreferredGroupSize;
   numGroups = (int)MathF.Ceiling(((float)N) / PreferredGroupSize);
   numNormalSizeGroups = numGroups - numOddSizeGroups;
}
else
{
   lastGroupSizes = PreferredGroupSize + 1;
   numOddSizeGroups = N % PreferredGroupSize;
   numGroups = (int)MathF.Floor(N / PreferredGroupSize);
   numNormalSizeGroups = numGroups - numOddSizeGroups;
}

我遇到的问题是我不知道如何组合这些组以形成有效的组合。有效组合不应包含重复的成员，组数应为numGroups，成员总数应为N。

这些稍后将被添加到诸如Dictionary<List<Person>, float> Groups

因此，例如，这将是一个有效的组合：

[A B C D E], 0.55
[F G H I J], 0.72
[K L M N O], 0.74
[P Q R S], 0.75

每行都是一个List<Person>，后跟一个float Score代表该组兼容性的 。越高越好。浮标没那么重要。重要的是只应创建有效的组合。

由于重复的成员，这将是无效的组合：

[A B C D E], 0.55
[F B H I J], 0.77
[K L M N O], 0.74
[P Q R S], 0.75

由于组中的总人数错误，这将是无效的组合：

[A B C D], 0.63
[F G H I J], 0.72
[K L M N O], 0.74
[P Q R S], 0.75

如果违反任一条件，则不应将其添加到有效组列表中。

现在，我执行以下操作：

1. people产生 的所有尺寸组合PreferredGroupSize。nCr = 19 choose 5

2. people产生 的所有尺寸组合lastGroupSizes。nCr = 19 choose 4

3. 计算Score1 和 2 产生的所有组合的一个组，并将组合 和 添加Score到Groups字典中。

4. Groups产生 的所有尺寸组合numGroups。

   这就是主要复杂性发挥作用的地方，也是为什么我想避免产生无效组的原因：

   nCr = ((19 choose 5) + (19 choose 4)) choose numGroups

5. 使用循环迭代那些foreach，寻找有效的组，仅将有效的组添加到List<Person> ValidGroups.

6. M计算出给定组后跳出循环。我已按 排序Groups，Score以便更有可能首先找到得分较高的组。

7. 处理有效组。

如果为 0，则跳过步骤 1 numNormalSizeGroups；如果为 0，则跳过步骤 2 numOddSizeGroups。

通过这种方式创建了大量无效组，并且 nCr 非常大。我相信应该有更好的方法来做到这一点，但我还没有找到方法。也许分享如何创建组合可能有助于帮助：

        //make combinations of a certain length
        public static IEnumerable<IEnumerable<T>> GetCombinations<T>(IEnumerable<T> items, int count)
        {
            int i = 0;
            foreach (var item in items)
            {
                if (count == 1)
                    yield return new T[] { item };
                else
                {
                    foreach (var result in GetCombinations(items.Skip(i + 1), count - 1))
                        yield return new T[] { item }.Concat(result);
                }

                ++i;
            }
        }

我将此代码归因于此处：Unique Combinations of list

在源代码中，代码被列为创建排列而不是组合。我已经在很多列表上运行过这个，它会产生组合。

我还将使用代码运行一下当前算法的最小版本：

//1. Produce all combinations of people of size PreferredGroupSize.
//2. Produce all combinations of people of size lastGroupSizes.
//Skip Step 1 if numNormalSizeGroups is 0
//Skip Step 2 if numOddSizeGroups is 0
bool calculatedNormal = false;
bool calculatedOdd = false;
while(!calculatedNormal || !calculatedOdd)
{
   int gSize = 0;
   if(!calculatedNormal)
   {
      calculatedNormal = true;
      if(numNormalSizeGroups>0)
         gSize = PreferredGroupSize;
      else
         continue;
   }
   else if(!calculatedOdd)
   {
      calculatedOdd = true;
      if(numOddSizeGroups>0)
         gSize = lastGroupSizes;
      else
         break;
   }

   //Calculate a group Score for all combinations produced by 1 and 2.
   //Add the combinations and Score to the Groups Dictionary.
   var combos = GetCombinations(people, gSize);
   float groupScore = 0;
   List<Person> curGroup;

   //for purposes of this example, generate pseudorandom float:
   Random rand = new Random();

   foreach(var combo in combos)
   {
        //groupScore = CalculateGroupScore(combo);
        groupScore = (float)rand.NextDouble();

        curGroup = new List<Person>();
        foreach(Person person in combo)
            curGroup.Add(person);
        Groups.Add(curGroup, groupScore);
   }
}

//I have sorted Groups by the Score
//so that higher scoring groups are more 
//likely to be found first.
Groups = Groups.OrderByDescending(x => x.Value).ToDictionary(x => x.Key, x => x.Value);

//4. Produce all combinations of Groups of size numGroups.
var AllGroupCombos = GetCombinations(Groups, numGroups);

int M = 10000;
List<Person> gList = new List<Person>();
List<Person> ValidGroups = new List<Person>();
int curPeopleInGroup = 0;
bool addGroup = true;


//5. Iterate over those using a foreach loop
foreach(var combo in AllGroupCombos)
{
    curPeopleInGroup = 0;
    addGroup = true;
    gList.Clear();

    //Look for valid groups
    foreach(KeyValuePair<List<Person>, float> keyValuePair in combo)
    {
        foreach(Person person in keyValuePair.Key)
        {
            if(!gList.Contains(person)
            {
               gList.Add(person);
               ++curPeopleInGroup;
            }
            else
            {
               addGroup = false;
               break;
            }
        }
        if(!addGroup)
            break;
    }
    //Add only valid groups to a List<Person> ValidGroups.
    if(!addGroup || curPeopleInGroup != N)
        continue;
    var comboList = combo.ToList();
    ValidGroups.Add(comboList);
    
    //6. Break out of the loop after a given M 
    //groups have been calculated. 
    if(ValidGroups.Count() >= M)
       break;
}

我希望这对您有所帮助，并且希望有人能够提供帮助。:)

Answer 1

我建议你迭代小组作业的排列。以下是可以解决您的问题的步骤：

1. 创建一个与人员长度相同的列表，但为每个人分配组索引。从“初始”顺序开始 - 重复每个索引与给定组中的成员一样多的次数，考虑到某些组会更小。在您的情况下，您将有 5 个零、5 个一、5 个二和 4 个三：{0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3}。
2. 上面索引列表的每个排列都有一个唯一的有效组分配 - 将每个人分配给给定位置的组索引
3. 从第 1 点开始迭代列表的所有排列。您必须实现类似next_permutationc++ 的东西。这是另一个 SoF 用户在另一个问题中的示例实现。

执行这些步骤，您将能够迭代所有有效的组合。