c# - 如何在 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};

我被给定为输入 a 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。越高越好。花车不是那么重要。重要的是只应创建有效的组合。

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

[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. 计算Score由 1 和 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;
            }
        }

我将此代码归因于此处：列表的唯一组合

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

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

//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;
}

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

标签： c#algorithmlinqcombinations